Knapsack¶

Principles learned¶

Create a generic model that uses data
Read an instance from a file

Write the solution in a file

Problem¶

The knapsack problem is defined as follows: given a set of items, each with a weight and a value, determine a subset of items in such a way that their total weight is less than a given bound and their total value is as large as possible. This problem is hard to solve in theory.

Download the example

Program¶

Note that the way to model is exactly the same than 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.

Knapsack instances involving millions of objects can be tackled using Hexaly Optimizer .

Hexaly Modeler
Python
C++
C#
Java

Execution:: hexaly knapsack.hxm inFileName=instances/kp_100_1.in [hxTimeLimit=] [solFileName=]

use io;

/* Read instance data */
function input() {
    local usage = "Usage: hexaly knapsack.hxm "
            + "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;

    local inFile = io.openRead(inFileName);
    nbItems = inFile.readInt();
    weights[i in 0...nbItems] = inFile.readInt();
    prices[i in 0...nbItems] = inFile.readInt();
    knapsackBound = inFile.readInt();
}

/* Declare the optimization model */
function model() {
    // Decision variables x[i]
    x[i in 0...nbItems] <- bool();

    // Weight constraint
    knapsackWeight <- sum[i in 0...nbItems](weights[i] * x[i]);
    constraint knapsackWeight <= knapsackBound;

    // Maximize value
    knapsackValue <- sum[i in 0...nbItems](prices[i] * x[i]);
    maximize knapsackValue;
}

/* Parametrize the solver */
function param() {
    if (hxTimeLimit == nil) hxTimeLimit = 20; 
}

/* Write the solution in a file */
function output() {
    if (solFileName == nil) return;
    local solFile = io.openWrite(solFileName);
    solFile.println(knapsackValue.value);
    for [i in 0...nbItems : x[i].value == 1]
        solFile.print(i + " ");
    solFile.println();
}

Execution (Windows): set PYTHONPATH=%HX_HOME%\bin\python

python knapsack.py instances\kp_100_1.in

Execution (Linux): export PYTHONPATH=/opt/hexaly_13_0/bin/python

python knapsack.py instances/kp_100_1.in

import hexaly.optimizer
import sys

if len(sys.argv) < 2:
    print("Usage: python knapsack.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)


def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]


with hexaly.optimizer.HexalyOptimizer() as optimizer:
    #
    # Read instance data
    #
    file_it = iter(read_integers(sys.argv[1]))

    # Number of items
    nb_items = next(file_it)

    # Items properties
    weights = [next(file_it) for i in range(nb_items)]
    values = [next(file_it) for i in range(nb_items)]

    # Knapsack bound
    knapsack_bound = next(file_it)

    #
    # Declare the optimization model
    #
    model = optimizer.model

    # Decision variables x[i]
    x = [model.bool() for i in range(nb_items)]

    # Weight constraint
    knapsack_weight = model.sum(x[i] * weights[i] for i in range(nb_items))
    model.constraint(knapsack_weight <= knapsack_bound)

    # Maximize value
    knapsack_value = model.sum(x[i] * values[i] for i in range(nb_items))
    model.maximize(knapsack_value)

    model.close()

    # Parameterize the optimizer
    if len(sys.argv) >= 4:
        optimizer.param.time_limit = int(sys.argv[3])
    else:
        optimizer.param.time_limit = 20

    optimizer.solve()

    #
    # Write the solution in a file
    #
    if len(sys.argv) >= 3:
        with open(sys.argv[2], 'w') as f:
            f.write("%d\n" % knapsack_value.value)
            for i in range(nb_items):
                if x[i].value != 1:
                    continue
                f.write("%d " % i)
            f.write("\n")

Compilation / Execution (Windows): cl /EHsc knapsack.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly130.lib

knapsack instances\kp_100_1.in

Compilation / Execution (Linux): g++ knapsack.cpp -I/opt/hexaly_13_0/include -lhexaly130 -lpthread -o knapsack

./knapsack instances/kp_100_1.in

#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace hexaly;
using namespace std;

class Knapsack {
public:
    // Number of items
    int nbItems;

    // Items properties
    vector<int> weights;
    vector<int> values;

    // Knapsack bound
    int knapsackBound;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    vector<HxExpression> x;

    // Objective
    HxExpression knapsackValue;

    /* Read instance data */
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> nbItems;

        weights.resize(nbItems);
        for (int i = 0; i < nbItems; ++i)
            infile >> weights[i];

        values.resize(nbItems);
        for (int i = 0; i < nbItems; ++i)
            infile >> values[i];

        infile >> knapsackBound;
    }

    void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Decision variables x[i]
        x.resize(nbItems);
        for (int i = 0; i < nbItems; ++i) {
            x[i] = model.boolVar();
        }

        // Weight constraint
        HxExpression knapsackWeight = model.sum();
        for (int i = 0; i < nbItems; ++i) {
            HxExpression itemWeight = x[i] * weights[i];
            knapsackWeight.addOperand(itemWeight);
        }
        model.constraint(knapsackWeight <= knapsackBound);

        // Maximize value
        knapsackValue = model.sum();
        for (int i = 0; i < nbItems; ++i) {
            HxExpression itemValue = x[i] * values[i];
            knapsackValue.addOperand(itemValue);
        }
        model.maximize(knapsackValue);
        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.solve();
    }

    /* Write the solution in a file */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << knapsackValue.getValue() << endl;
        for (int i = 0; i < nbItems; ++i) {
            if (x[i].getValue() == 1)
                outfile << i << " ";
        }
        outfile << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: knapsack inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "20";

    try {
        Knapsack model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}

Compilation / Execution (Windows): copy %HX_HOME%\bin\Hexaly.NET.dll .

csc Knapsack.cs /reference:Hexaly.NET.dll

Knapsack instances\kp_100_1.in

using System;
using System.IO;
using System.Collections.Generic;
using Hexaly.Optimizer;

public class Knapsack : IDisposable
{
    // Number of items
    int nbItems;

    // Items properties
    int[] weights;
    int[] values;

    // Knapsack bound
    int knapsackBound;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Hexaly Program variables
    HxExpression[] x;

    // Objective
    HxExpression knapsackValue;

    public Knapsack()
    {
        optimizer = new HexalyOptimizer();
    }

    /* Read instance data */
    void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            nbItems = int.Parse(input.ReadLine());
            weights = new int[nbItems];
            values = new int[nbItems];

            string[] splittedWeights = input.ReadLine().Split(' ');
            for (int i = 0; i < nbItems; ++i)
                weights[i] = int.Parse(splittedWeights[i]);

            string[] splittedValues = input.ReadLine().Split(' ');
            for (int i = 0; i < nbItems; ++i)
                values[i] = int.Parse(splittedValues[i]);

            knapsackBound = int.Parse(input.ReadLine());
        }
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

    void Solve(int limit)
    {
        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        // Decision variables x[i]
        x = new HxExpression[nbItems];
        for (int i = 0; i < nbItems; ++i)
            x[i] = model.Bool();

        // Weight constraint
        HxExpression knapsackWeight = model.Sum();
        for (int i = 0; i < nbItems; ++i)
            knapsackWeight.AddOperand(x[i] * weights[i]);
        model.Constraint(knapsackWeight <= knapsackBound);

        // Maximize value
        knapsackValue = model.Sum();
        for (int i = 0; i < nbItems; ++i)
            knapsackValue.AddOperand(x[i] * values[i]);

        model.Maximize(knapsackValue);
        model.Close();

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.Solve();
    }

    /* Write the solution in a file */
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(knapsackValue.GetValue());
            for (int i = 0; i < nbItems; ++i)
            {
                if (x[i].GetValue() == 1)
                    output.Write(i + " ");
            }
            output.WriteLine();
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Knapsack inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "20";

        using (Knapsack model = new Knapsack())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

Compilation / Execution (Windows): javac Knapsack.java -cp %HX_HOME%\bin\hexaly.jar

java -cp %HX_HOME%\bin\hexaly.jar;. Knapsack instances\kp_100_1.in

Compilation / Execution (Linux): javac Knapsack.java -cp /opt/hexaly_13_0/bin/hexaly.jar

java -cp /opt/hexaly_13_0/bin/hexaly.jar:. Knapsack instances/kp_100_1.in

import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class Knapsack {
    // Number of items
    private int nbItems;

    // Items properties
    private int[] weights;
    private int[] values;

    // Knapsack bound
    private int knapsackBound;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Hexaly Program variables
    private HxExpression[] x;

    // Objective
    private HxExpression knapsackValue;

    private Knapsack(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            nbItems = input.nextInt();

            weights = new int[nbItems];
            for (int i = 0; i < nbItems; ++i) {
                weights[i] = input.nextInt();
            }

            values = new int[nbItems];
            for (int i = 0; i < nbItems; ++i) {
                values[i] = input.nextInt();
            }

            knapsackBound = input.nextInt();
        }
    }

    private void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Decision variables x[i]
        x = new HxExpression[nbItems];
        for (int i = 0; i < nbItems; ++i) {
            x[i] = model.boolVar();
        }

        // Weight constraint
        HxExpression knapsackWeight = model.sum();
        for (int i = 0; i < nbItems; ++i) {
            HxExpression itemWeight = model.prod(x[i], weights[i]);
            knapsackWeight.addOperand(itemWeight);
        }
        model.constraint(model.leq(knapsackWeight, knapsackBound));

        // Maximize value
        knapsackValue = model.sum();
        for (int i = 0; i < nbItems; ++i) {
            HxExpression itemValue = model.prod(x[i], values[i]);
            knapsackValue.addOperand(itemValue);
        }

        model.maximize(knapsackValue);
        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        optimizer.solve();
    }

    /* Write the solution in a file */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println(knapsackValue.getValue());
            for (int i = 0; i < nbItems; ++i)
                if (x[i].getValue() == 1)
                    output.print(i + " ");
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java Knapsack inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "20";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            Knapsack model = new Knapsack(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}