This page is for an old version of Hexaly Optimizer.
We recommend that you update your version and read the documentation for the
latest stable release.
Toy¶
Principles learned¶
- Create a basic model
- Add boolean decision variables
- Create expressions
- Add an objective
- Add a constraint
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.
Download the exampleProgram¶
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 toy.py
- Execution (Linux)
- export PYTHONPATH=/opt/localsolver_9_5/bin/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\localsolver95.libtoy
- Compilation / Execution (Linux)
- g++ toy.cpp -I/opt/localsolver_9_5/include -llocalsolver95 -lpthread -o toytoy
//********* 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[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 += weights[i]*x[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++)
knapsackValue += values[i]*x[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 << "Error occurred:" << e.what() << endl;
return 1;
}
return 0;
}
- Compilation / Execution (Windows)
- copy %LS_HOME%\bin\localsolvernet.dll .csc Toy.cs /reference:localsolvernet.dllToy
/********** 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[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.AddOperand(weights[i] * x[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++)
knapsackValue.AddOperand(values[i] * x[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.jarjava -cp %LS_HOME%\bin\localsolver.jar;. Toy
- Compilation / Execution (Linux)
- javac Toy.java -cp /opt/localsolver_9_5/bin/localsolver.jarjava -cp /opt/localsolver_9_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.
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.addOperand(model.prod(weights[i], x[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++) {
knapsackValue.addOperand(model.prod(values[i], x[i]));
}
// maximize knapsackValue;
model.maximize(knapsackValue);
// close model, then solve
model.close();
// Parameterizes the solver.
localsolver.getParam().setTimeLimit(10);
localsolver.solve();
}
}