# Toy¶

## Principles learned¶

• Create a basic model

• Create expressions

## Problem¶

A toy instance of the knapsack problem: given 8 items with weights 10, 60, 30, 40, 30, 20, 20, 2 and values 1, 10, 15, 40, 60, 90, 100, 15 respectively, determine a subset of those items in such a way that their total weight is less than 102 and their total value is as large as possible.

## Program¶

The way to model is exactly the same as 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.

Execution:
localsolver toy.lsp
```/* Declare the optimization model */
function model() {

// 0-1 decisions
x_0 <- bool(); x_1 <- bool(); x_2 <- bool(); x_3 <- bool();
x_4 <- bool(); x_5 <- bool(); x_6 <- bool(); x_7 <- bool();

// Weight constraint
knapsackWeight <- 10 * x_0 + 60 * x_1 + 30 * x_2 + 40 * x_3 + 30 * x_4 + 20 * x_5 + 20 * x_6 + 2 * x_7;
constraint knapsackWeight <= 102;

// Maximize value
knapsackValue <- 1 * x_0 + 10 * x_1 + 15 * x_2 + 40 * x_3 + 60 * x_4 + 90 * x_5 + 100 * x_6 + 15 * x_7;
maximize knapsackValue;
}

/* Parametrize the solver */
function param() {
lsTimeLimit = 10;
}
```
Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python toy.py
Execution (Linux)
export PYTHONPATH=/opt/localsolver_12_0/bin/python
python toy.py
```import localsolver

with localsolver.LocalSolver() as ls:
weights = [10, 60, 30, 40, 30, 20, 20, 2]
values = [1, 10, 15, 40, 60, 90, 100, 15]
knapsack_bound = 102

#
# Declare the optimization model
#
model = ls.model

# 0-1 decisions
x = [model.bool() for _ in range(8)]

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

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

model.close()

# Parameterize the solver
ls.param.time_limit = 10

ls.solve()
```
Compilation / Execution (Windows)
cl /EHsc toy.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver120.lib
toy
Compilation / Execution (Linux)
g++ toy.cpp -I/opt/localsolver_12_0/include -llocalsolver120 -lpthread -o toy
toy
```#include "localsolver.h"
#include <iostream>

using namespace localsolver;
using namespace std;

int main() {
try {
lsint weights[] = {10, 60, 30, 40, 30, 20, 20, 2};
lsint values[] = {1, 10, 15, 40, 60, 90, 100, 15};
lsint knapsackBound = 102;

// Declare the optimization model
LocalSolver localsolver;
LSModel model = localsolver.getModel();

// 0-1 decisions
LSExpression x[8];
for (int i = 0; i < 8; ++i)
x[i] = model.boolVar();

// knapsackWeight <- 10*x0 + 60*x1 + 30*x2 + 40*x3 + 30*x4 + 20*x5 + 20*x6 + 2*x7;
LSExpression knapsackWeight = model.sum();
for (int i = 0; i < 8; ++i)

// knapsackWeight <= 102;
model.constraint(knapsackWeight <= knapsackBound);

// knapsackValue <- 1*x0 + 10*x1 + 15*x2 + 40*x3 + 60*x4 + 90*x5 + 100*x6 + 15*x7;
LSExpression knapsackValue = model.sum();
for (int i = 0; i < 8; ++i)

// maximize knapsackValue;
model.maximize(knapsackValue);

// Close model before solving it
model.close();

// Parametrize the solver
localsolver.getParam().setTimeLimit(10);
localsolver.solve();

} catch (const exception& e) {
cerr << "An error occurred:" << e.what() << endl;
return 1;
}

return 0;
}
```
Compilation / Execution (Windows)
copy %LS_HOME%\bin\localsolvernet.dll .
csc Toy.cs /reference:localsolvernet.dll
Toy
```using localsolver;

public class Toy
{
public static void Main()
{
int[] weights = { 10, 60, 30, 40, 30, 20, 20, 2 };
int[] values = { 1, 10, 15, 40, 60, 90, 100, 15 };

using (LocalSolver localsolver = new LocalSolver())
{
// Declare the optimization model
LSModel model = localsolver.GetModel();

// 0-1 decisions
LSExpression[] x = new LSExpression[8];
for (int i = 0; i < 8; ++i)
x[i] = model.Bool();

// knapsackWeight <- 10*x0 + 60*x1 + 30*x2 + 40*x3 + 30*x4 + 20*x5 + 20*x6 + 2*x7;
LSExpression knapsackWeight = model.Sum();
for (int i = 0; i < 8; ++i)

// knapsackWeight <= 102;
model.Constraint(knapsackWeight <= 102);

// knapsackValue <- 1*x0 + 10*x1 + 15*x2 + 40*x3 + 60*x4 + 90*x5 + 100*x6 + 15*x7;
LSExpression knapsackValue = model.Sum();
for (int i = 0; i < 8; ++i)

// maximize knapsackValue;
model.Maximize(knapsackValue);

// Close the model before solving it
model.Close();

// Parametrize the solver
localsolver.GetParam().SetTimeLimit(10);
localsolver.Solve();
}
}
}
```
Compilation / Execution (Windows)
javac Toy.java -cp %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Toy
Compilation / Execution (Linux)
javac Toy.java -cp /opt/localsolver_12_0/bin/localsolver.jar
java -cp /opt/localsolver_12_0/bin/localsolver.jar:. Toy
```import localsolver.*;

public class Toy {

public static void main(String[] args) {
int[] weights = { 10, 60, 30, 40, 30, 20, 20, 2 };
int[] values = { 1, 10, 15, 40, 60, 90, 100, 15 };

// Declare the optimization model
try (LocalSolver localsolver = new LocalSolver()) {
LSModel model = localsolver.getModel();

// 0-1 decisions
LSExpression[] x = new LSExpression[8];
for (int i = 0; i < 8; ++i) {
x[i] = model.boolVar();
}

// knapsackWeight <- 10*x0 + 60*x1 + 30*x2 + 40*x3 + 30*x4 + 20*x5 + 20*x6 + 2*x7;
LSExpression knapsackWeight = model.sum();
for (int i = 0; i < 8; ++i) {
}

// knapsackWeight <= 102;
model.constraint(model.leq(knapsackWeight, 102));

// knapsackValue <- 1*x0 + 10*x1 + 15*x2 + 40*x3 + 60*x4 + 90*x5 + 100*x6 + 15*x7;
LSExpression knapsackValue = model.sum();
for (int i = 0; i < 8; ++i) {
}

// maximize knapsackValue;
model.maximize(knapsackValue);

// Close model before solving it
model.close();

// Parametrize the solver
localsolver.getParam().setTimeLimit(10);
localsolver.solve();
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}
```