Toy

Problem

We describe a toy instance of the Knapsack Problem. We consider 8 items, with weights 10, 60, 30, 40, 30, 20, 20, 2, and values 1, 10, 15, 40, 60, 90, 100, 15 respectively. The goal is to determine a subset of items such that the total weight is less than 102 and the total value is as large as possible.

Principles learned

Learn about Hexaly Optimizer’s modeling style: distinguish decision variables from intermediate expressions

Program

We model this toy problem as an Integer Program. For each item, we define a Boolean decision variable equal to 1 if the item is selected and 0 otherwise. We compute the total weight of selected items using the ‘sum’ operator. Note that we deduce this value from those of the decisions: the total weight is an intermediate expression, not a decision. After defining it, we can constrain the total weight to be lower than 102. Similarly, we define another intermediate expression, corresponding to the total value of selected items. Finally, we maximize this total value.

Hexaly Modeler
Python
C++
C#
Java

Download

Open in the studio

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

Problem

Principles learned

Program

Similar examples