# Knapsack¶

## Principles learned¶

• Create a generic model that uses data
• Read an instance from a file
• Write the solution in a file

## Problem¶

The knapsack problem is defined as follows: given a set of items, each with a weight and a value, determine a subset of items in such a way that their total weight is less than a given bound and their total value is as large as possible. This problem is hard to solve in theory.

## Program¶

Note that the way to model is exactly the same than in integer programming: for each item, a 0-1 decision variable is defined which is equal to 1 if the item belongs to the knapsack and 0 otherwise.

Knapsack instances involving millions of objects can be tackled using LocalSolver.

Execution:
localsolver knapsack.lsp inFileName=instances/kp_100_1.in [lsTimeLimit=] [solFileName=]
```/********** knapsack.lsp **********/

use io;

/* Reads instance data. */
function input() {
local usage = "Usage: localsolver knapsack.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";

if (inFileName == nil) throw usage;

local inFile = io.openRead(inFileName);
nbItems = inFile.readInt();
weights[i in 0..nbItems-1] = inFile.readInt();
prices[i in 0..nbItems-1] = inFile.readInt();
knapsackBound = inFile.readInt();
}

/* Declares the optimization model. */
function model() {
// 0-1 decisions
x[i in 0..nbItems-1] <- bool();

// weight constraint
knapsackWeight <- sum[i in 0..nbItems-1](weights[i] * x[i]);
constraint knapsackWeight <= knapsackBound;

// maximize value
knapsackValue <- sum[i in 0..nbItems-1](prices[i] * x[i]);
maximize knapsackValue;
}

/* Parameterizes the solver. */
function param() {
if (lsTimeLimit == nil) lsTimeLimit = 20;
}

/* Writes the solution in a file */
function output() {
if(solFileName == nil) return;
local solFile = io.openWrite(solFileName);
solFile.println(knapsackValue.value);
for [i in 0..nbItems-1 : x[i].value == 1]
solFile.print(i + " ");
solFile.println();
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python27\
python knapsack.py instances\kp_100_1.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python knapsack.py instances/kp_100_1.in
```########## knapsack.py ##########

import localsolver
import sys

if len(sys.argv) < 2:
print ("Usage: python knapsack.py inputFile [outputFile] [timeLimit]")
sys.exit(1)

def read_integers(filename):
with open(filename) as f:
return [int(elem) for elem in f.read().split()]

with localsolver.LocalSolver() as ls:

#
# Reads instance data
#

file_it = iter(read_integers(sys.argv[1]))

# Number of items
nb_items = file_it.next()

# Items properties
weights = [file_it.next() for i in range(nb_items)]
values = [file_it.next() for i in range(nb_items)]

# Knapsack bound
knapsack_bound = file_it.next()

#
# Declares the optimization model
#
model = ls.model

# Decision variables x[i]
x = [model.bool() for i in range(nb_items)]

# Weight constraint
knapsack_weight = model.sum(x[i]*weights[i] for i in range(nb_items))
model.constraint(knapsack_weight <= knapsack_bound)

# Maximize value
knapsack_value = model.sum(x[i]*values[i] for i in range(nb_items))
model.maximize(knapsack_value)

model.close()

#
# Parameterizes the solver
#
if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
else: ls.create_phase().time_limit = 20

ls.solve()

#
# Writes the solution in a file
#
if len(sys.argv) >= 3:
with open(sys.argv[2], 'w') as f:
f.write("%d\n" % knapsack_value.value)
for i in range(nb_items):
if x[i].value != 1: continue
f.write("%d " % i)
f.write("\n")
```
Compilation / Execution (Windows)
cl /EHsc knapsack.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
knapsack instances\kp_100_1.in
Compilation / Execution (Linux)
g++ knapsack.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o knapsack
./knapsack instances/kp_100_1.in
```//********* knapsack.cpp *********

#include <iostream>
#include <fstream>
#include <vector>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

class Knapsack {
public:
// Number of items.
int nbItems;

// Items properties.
vector<lsint> weights;
vector<lsint> values;

// Knapsack bound
lsint knapsackBound;

// LocalSolver.
LocalSolver localsolver;

// Decision variables.
vector<LSExpression> x;

// Objective.
LSExpression knapsackValue;

// Solution (items in the knapsack).
vector<int> solution;

// Reads instance data.
void readInstance(const string& fileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(fileName.c_str());

infile >> nbItems;

weights.resize(nbItems);
for (int i = 0; i < nbItems; i++)
infile >> weights[i];

values.resize(nbItems);
for (int i = 0; i < nbItems; i++)
infile >> values[i];

infile >> knapsackBound;
}

void solve(int limit) {
// Declares the optimization model.
LSModel model = localsolver.getModel();

// Decision variables x[i]
x.resize(nbItems);
for (int i = 0; i < nbItems; i++) {
x[i] = model.boolVar();
}

// Weight constraint
LSExpression knapsackWeight = model.sum();
for (int i = 0; i < nbItems; i++) {
LSExpression itemWeight = x[i]*weights[i];
knapsackWeight += itemWeight;
}
model.constraint(knapsackWeight <= knapsackBound);

// Maximize value
knapsackValue = model.sum();
for (int i = 0; i < nbItems; i++) {
LSExpression itemValue = x[i]*values[i];
knapsackValue += itemValue;
}
model.maximize(knapsackValue);
model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);
localsolver.solve();

solution.clear();
for (int i = 0; i < nbItems; ++i)
if (x[i].getValue() == 1)
solution.push_back(i);
}

// Writes the solution in a file
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());

outfile << knapsackValue.getValue() << endl;
for (unsigned int i = 0; i < solution.size(); ++i)
outfile << solution[i] << " ";
outfile << endl;
}
};

int main(int argc, char** argv) {
if (argc < 2) {
cerr << "Usage: knapsack inputFile [outputFile] [timeLimit]" << endl;
return 1;
}

const char* instanceFile = argv[1];
const char* solFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "20";

try {
Knapsack model;
model.readInstance(instanceFile);
model.solve(atoi(strTimeLimit));
if(solFile != NULL) model.writeSolution(solFile);
return 0;
} catch (const exception& e){
cerr << "Error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc Knapsack.cs /reference:localsolvernet.dll
Knapsack instances\kp_100_1.in
```/********** Knapsack.cs **********/

using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

public class Knapsack : IDisposable
{
// Number of items
int nbItems;

// Items properties.
int[] weights;
int[] values;

// Knapsack bound.
int knapsackBound;

// Solver.
LocalSolver localsolver;

// LS Program variables.
LSExpression[] x;

// Objective.
LSExpression knapsackValue;

// Solutions    (items in the knapsack).
List<int> solutions;

public Knapsack()
{
localsolver = new LocalSolver();
}

// Reads instance data.
void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
nbItems = int.Parse(input.ReadLine());
weights = new int[nbItems];
values = new int[nbItems];

string[] splittedWeights = input.ReadLine().Split(' ');
if (splittedWeights.Length < nbItems)
throw new Exception("Wrong number of item weights");

for (int i = 0; i < nbItems; i++)
weights[i] = int.Parse(splittedWeights[i]);

string[] splittedValues = input.ReadLine().Split(' ');
if (splittedValues.Length < nbItems)
throw new Exception("Wrong number of item values");

for (int i = 0; i < nbItems; i++)
values[i] = int.Parse(splittedValues[i]);

knapsackBound = int.Parse(input.ReadLine());
}
}

public void Dispose()
{
if (localsolver != null)
localsolver.Dispose();
}

void Solve(int limit)
{
// Declares the optimization model.
localsolver = new LocalSolver();
LSModel model = localsolver.GetModel();

// Decision variables x[i]
x = new LSExpression[nbItems];
for (int i = 0; i < nbItems; i++)
{
x[i] = model.Bool();
}

// weight constraint
LSExpression knapsackWeight = model.Sum();
for (int i = 0; i < nbItems; i++)
{
knapsackWeight.AddOperand(x[i] * weights[i]);
}
model.Constraint(knapsackWeight <= knapsackBound);

// maximize value
knapsackValue = model.Sum();
for (int i = 0; i < nbItems; i++)
{
knapsackValue.AddOperand(x[i] * values[i]);
}

model.Maximize(knapsackValue);
model.Close();

// Parameterizes the solver.
LSPhase phase = localsolver.CreatePhase();
phase.SetTimeLimit(limit);

localsolver.Solve();

solutions = new List<int>();
for (int i = 0; i < nbItems; ++i)
{
if (x[i].GetValue() == 1) solutions.Add(i);
}
}

// Writes the solution in a file
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(knapsackValue.GetValue());
for (int i = 0; i < solutions.Count; ++i)
output.Write(solutions[i] + " ");
output.WriteLine();
}
}

public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: Knapsack inputFile [solFile] [timeLimit]");
Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "20";

using (Knapsack model = new Knapsack())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null)
model.WriteSolution(outputFile);
}
}
}
```
Compilation / Execution (Windows)
javac Knapsack.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Knapsack instances\kp_100_1.in
Compilation/Execution (Linux)
javac Knapsack.java -cp /opt/localsolver_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Knapsack instances/kp_100_1.in
```/********** Knapsack.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class Knapsack {
// Number of items.
private int nbItems;

// Items properties.
private int[] weights;
private int[] values;

// Knapsack bound
private int knapsackBound;

// Solver.
private LocalSolver localsolver;

// LS Program variables.
private LSExpression[] x;

// Objective.
private LSExpression knapsackValue;

// Solutions (classes at each position).
private List<Integer> solutions;

// Reads instance data.
private void readInstance(String fileName) throws IOException {
try(Scanner input = new Scanner(new File(fileName))) {
nbItems = input.nextInt();

weights = new int[nbItems];
for (int i = 0; i < nbItems; i++) {
weights[i] = input.nextInt();
}

values = new int[nbItems];
for (int i = 0; i < nbItems; i++) {
values[i] = input.nextInt();
}

knapsackBound = input.nextInt();
}
}

private void solve(int limit) {
// Declares the optimization model.
localsolver = new LocalSolver();
LSModel model = localsolver.getModel();

// boolean variables x[i]
x = new LSExpression[nbItems];
for (int i = 0; i < nbItems; i++) {
x[i] = model.boolVar();
}

// weight constraint
LSExpression knapsackWeight = model.sum();
for (int i = 0; i < nbItems; i++) {
LSExpression itemWeight = model.prod(x[i],weights[i]);
knapsackWeight.addOperand(itemWeight);
}
model.constraint(model.leq(knapsackWeight,knapsackBound));

// maximize value
knapsackValue = model.sum();
for (int i = 0; i < nbItems; i++) {
LSExpression itemValue = model.prod(x[i],values[i]);
knapsackValue.addOperand(itemValue);
}

model.maximize(knapsackValue);
model.close();

// Parameterizes the solver.
LSPhase phase = localsolver.createPhase();
phase.setTimeLimit(limit);

localsolver.solve();

solutions = new ArrayList<Integer>();
for (int i = 0; i < nbItems; i++)
if (x[i].getValue() == 1)
solutions.add(i);
}

// Writes the solution in a file
private void writeSolution(String fileName) throws IOException {
try(PrintWriter output = new PrintWriter(fileName)) {
output.println(knapsackValue.getValue());
for (int i = 0; i < solutions.size(); ++i)
output.print(solutions.get(i) + " ");
output.println();
}
}

public static void main(String[] args) {
if (args.length < 1) {
System.err.println("Usage: java Knapsack inputFile [outputFile] [timeLimit]");
System.exit(1);
}

String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "20";

try {
Knapsack model = new Knapsack();
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if(outputFile != null) {
model.writeSolution(outputFile);
}
} catch(Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}
```