View all examples

Knapsack Problem

Problem

The Knapsack Problem is defined as follows. We consider a set of items, with different weights and values. We have to select a subset of items to place inside a bag of known capacity. The total weight of items in the bag must not exceed its capacity. The objective is to maximize the total value of the items inside the bag.

Principles learned

Data

We provide instances from the OR Library. The format of the datasets is as follows:

  • Number of items
  • For each item, its weight
  • For each item, its value
  • A known upper bound for this instance

Program

We model this 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 the bag’s capacity. Similarly, we define another intermediate expression, corresponding to the total value of selected items. Finally, we maximize this total value.

Download
Open in the studio
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);
        }
    }
}

Even though the Knapsack Problem is known to be NP-hard, instances involving millions of items can be tackled using Hexaly Optimizer.

Similar examples

Discover the ease of use and performance of Hexaly