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 example

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.

LSP
Python
C++
Java
C#

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

Execution (Windows): set PYTHONPATH=%LS_HOME%\bin\python27\

python toy.py

Execution (Linux): export PYTHONPATH=/opt/localsolver_XXX/bin/python27/

python toy.py

########## toy.py ##########

import localsolver
import sys

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.create_phase().time_limit = 1

    ls.solve()

Compilation / Execution (Windows): cl /EHsc toy.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib

toy

Compilation / Execution (Linux): g++ toy.cpp -I/opt/localsolver_XXX/include -llocalsolver -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[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. */
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(1);
        localsolver.solve();

    } catch (const LSException& e) {
        cout << "LSException occurred:" << e.getMessage() << endl;
    }
    
    return 0;
}

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_XXX/bin/localsolver.jar

java -cp /opt/localsolver_XXX/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. */
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(1);
        localsolver.solve();
    }
}

Compilation/Execution (Windows): copy %LS_HOME%\bin\*net.dll .

csc Toy.cs /reference:localsolvernet.dll

Toy

/********** Toy.cs **********/

using System;
using localsolver;

public class Toy
{
    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. */
            LSPhase phase = localsolver.CreatePhase();
            phase.SetTimeLimit(1);
            localsolver.Solve();
        }
    }
}