# 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=]
```use io;

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

if (inFileName == nil) throw usage;

}

/* Declare the optimization model */
function model() {
// Decision variables x[i]
x[i in 0...nbItems] <- bool();

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

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

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

/* Write 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 : x[i].value == 1]
solFile.print(i + " ");
solFile.println();
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python knapsack.py instances\kp_100_1.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python knapsack.py instances/kp_100_1.in
```import localsolver
import sys

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

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

with localsolver.LocalSolver() as ls:
#
#

# Number of items
nb_items = next(file_it)

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

# Knapsack bound
knapsack_bound = next(file_it)

#
# Declare 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()

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

ls.solve()

#
# Write 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\localsolver120.lib
knapsack instances\kp_100_1.in
Compilation / Execution (Linux)
g++ knapsack.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o knapsack
./knapsack instances/kp_100_1.in
```#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

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

// Items properties
vector<int> weights;
vector<int> values;

// Knapsack bound
int knapsackBound;

// LocalSolver
LocalSolver localsolver;

// Decision variables
vector<LSExpression> x;

// Objective
LSExpression knapsackValue;

ifstream infile;
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) {
// Declare 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];
}
model.constraint(knapsackWeight <= knapsackBound);

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

// Parametrize the solver
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

/* Write the solution in a file */
void writeSolution(const string& fileName) {
ofstream outfile;
outfile.open(fileName.c_str());

outfile << knapsackValue.getValue() << endl;
for (int i = 0; i < nbItems; ++i) {
if (x[i].getValue() == 1)
outfile << 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.solve(atoi(strTimeLimit));
if (solFile != NULL)
model.writeSolution(solFile);
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
```
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Knapsack.cs /reference:localsolvernet.dll
Knapsack instances\kp_100_1.in
```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;

// LocalSolver
LocalSolver localsolver;

// LS Program variables
LSExpression[] x;

// Objective
LSExpression knapsackValue;

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

{
{
weights = new int[nbItems];
values = new int[nbItems];

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

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

}
}

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

void Solve(int limit)
{
// Declare the optimization model
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)
model.Constraint(knapsackWeight <= knapsackBound);

// Maximize value
knapsackValue = model.Sum();
for (int i = 0; i < nbItems; ++i)

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

// Parametrize the solver
localsolver.GetParam().SetTimeLimit(limit);

localsolver.Solve();
}

/* Write the solution in a file */
void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine(knapsackValue.GetValue());
for (int i = 0; i < nbItems; ++i)
{
if (x[i].GetValue() == 1)
output.Write(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.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_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. Knapsack instances/kp_100_1.in
```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;

// LocalSolver
private final LocalSolver localsolver;

// LS Program variables
private LSExpression[] x;

// Objective
private LSExpression knapsackValue;

private Knapsack(LocalSolver localsolver) {
this.localsolver = localsolver;
}

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) {
// Declare the optimization model
LSModel model = localsolver.getModel();

// Decision 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]);
}
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]);
}

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

// Parametrize the solver
localsolver.getParam().setTimeLimit(limit);

localsolver.solve();
}

/* Write 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 < nbItems; ++i)
if (x[i].getValue() == 1)
output.print(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 (LocalSolver localsolver = new LocalSolver()) {
Knapsack model = new Knapsack(localsolver);