Toy

Principles learned

  • Create a basic model

  • Add boolean decision variables

  • Create expressions

  • Add an objective

  • Add a constraint

Problem

../_images/toy.svg

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.

Execution:
hexaly toy.hxm
/* 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() {
    hxTimeLimit = 10;
}
Execution (Windows)
set PYTHONPATH=%HX_HOME%\bin\python
python toy.py
Execution (Linux)
export PYTHONPATH=/opt/hexaly_13_0/bin/python
python toy.py
import hexaly.optimizer

with hexaly.optimizer.HexalyOptimizer() as optimizer:
    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 = optimizer.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 optimizer
    optimizer.param.time_limit = 10

    optimizer.solve()
Compilation / Execution (Windows)
cl /EHsc toy.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly130.lib
toy
Compilation / Execution (Linux)
g++ toy.cpp -I/opt/hexaly_13_0/include -lhexaly130 -lpthread -o toy
toy
#include "optimizer/hexalyoptimizer.h"
#include <iostream>

using namespace hexaly;
using namespace std;

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

        // Declare the optimization model
        HexalyOptimizer optimizer;
        HxModel model = optimizer.getModel();

        // 0-1 decisions
        HxExpression 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;
        HxExpression knapsackWeight = model.sum();
        for (int i = 0; i < 8; ++i)
            knapsackWeight.addOperand(weights[i] * x[i]);

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

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

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

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

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(10);
        optimizer.solve();

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

    return 0;
}
Compilation / Execution (Windows)
copy %HX_HOME%\bin\Hexaly.NET.dll .
csc Toy.cs /reference:Hexaly.NET.dll
Toy
using Hexaly.Optimizer;

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 (HexalyOptimizer optimizer = new HexalyOptimizer())
        {
            // Declare the optimization model
            HxModel model = optimizer.GetModel();

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

            // Parametrize the optimizer
            optimizer.GetParam().SetTimeLimit(10);
            optimizer.Solve();
        }
    }
}
Compilation / Execution (Windows)
javac Toy.java -cp %HX_HOME%\bin\hexaly.jar
java -cp %HX_HOME%\bin\hexaly.jar;. Toy
Compilation / Execution (Linux)
javac Toy.java -cp /opt/hexaly_13_0/bin/hexaly.jar
java -cp /opt/hexaly_13_0/bin/hexaly.jar:. Toy
import com.hexaly.optimizer.*;

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 (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            HxModel model = optimizer.getModel();

            // 0-1 decisions
            HxExpression[] x = new HxExpression[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;
            HxExpression 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;
            HxExpression 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 before solving it
            model.close();

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