# 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
/********** toy.lsp **********/

/* Declares 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;
}

/* Parameterizes the solver. */
function param() {
lsTimeLimit = 10;
}

Execution (Windows)
set PYTHONPATH=%LS_HOME%\bin\python
python toy.py
Execution (Linux)
export PYTHONPATH=/opt/localsolver_10_5/bin/python
python toy.py
########## 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

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

# 0-1 decisions
x = [model.bool() for i 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()

#
# Parameterizes the solver
#
ls.param.time_limit = 10

ls.solve()


Compilation / Execution (Windows)
cl /EHsc toy.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver105.lib
toy
Compilation / Execution (Linux)
g++ toy.cpp -I/opt/localsolver_10_5/include -llocalsolver105 -lpthread -o toy
toy
//********* toy.cpp *********

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

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;

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

// 0-1 decisions
LSExpression x;
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 <= knapsackBound;
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, then solve
model.close();

// Parameterizes 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
/********** Toy.cs **********/

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

// 0-1 decisions
LSExpression[] x = new LSExpression;
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();

// Parameterizes 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_10_5/bin/localsolver.jar
java -cp /opt/localsolver_10_5/bin/localsolver.jar:. Toy
/********** Toy.java **********/

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};

// Declares the optimization model.
final LocalSolver localsolver = new LocalSolver();
LSModel model = localsolver.getModel();

// 0-1 decisions
LSExpression[] x = new LSExpression;
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, then solve
model.close();

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