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 LocalSolver.

LSP
Python
C++
C#
Java

Execution:: localsolver knapsack.lsp inFileName=instances/kp_100_1.in [lsTimeLimit=] [solFileName=]

use io;

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

    if (inFileName == nil) throw usage;

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

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

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

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

/* Parametrize the solver */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 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-1 : x[i].value == 1]
        solFile.print(i + " ");
    solFile.println();
}

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

python knapsack.py instances\kp_100_1.in

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

python knapsack.py instances/kp_100_1.in

import localsolver
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 localsolver.LocalSolver() as ls:
    #
    # 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 = ls.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 solver
    if len(sys.argv) >= 4:
        ls.param.time_limit = int(sys.argv[3])
    else:
        ls.param.time_limit = 20

    ls.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%LS_HOME%\include /link %LS_HOME%\bin\localsolver115.lib

knapsack instances\kp_100_1.in

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

./knapsack instances/kp_100_1.in

#include "localsolver.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace localsolver;
using namespace std;

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

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

    // Knapsack bound
    int knapsackBound;

    // LocalSolver
    LocalSolver localsolver;

    // Decision variables
    vector<LSExpression> x;

    // Objective
    LSExpression 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
        LSModel model = localsolver.getModel();

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

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

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

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.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 %LS_HOME%\bin\localsolvernet.dll .

csc Knapsack.cs /reference:localsolvernet.dll

Knapsack instances\kp_100_1.in

using System;
using System.IO;
using System.Collections.Generic;
using localsolver;

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

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

    // Knapsack bound
    int knapsackBound;

    // LocalSolver
    LocalSolver localsolver;

    // LS Program variables
    LSExpression[] x;

    // Objective
    LSExpression knapsackValue;

    public Knapsack()
    {
        localsolver = new LocalSolver();
    }

    /* 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 (localsolver != null)
            localsolver.Dispose();
    }

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

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

        // Weight constraint
        LSExpression 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 solver
        localsolver.GetParam().SetTimeLimit(limit);

        localsolver.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 %LS_HOME%\bin\localsolver.jar

java -cp %LS_HOME%\bin\localsolver.jar;. Knapsack instances\kp_100_1.in

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

java -cp /opt/localsolver_11_5/bin/localsolver.jar:. Knapsack instances/kp_100_1.in

import java.util.*;
import java.io.*;
import localsolver.*;

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

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

    // Knapsack bound
    private int knapsackBound;

    // LocalSolver
    private final LocalSolver localsolver;

    // LS Program variables
    private LSExpression[] x;

    // Objective
    private LSExpression knapsackValue;

    private Knapsack(LocalSolver localsolver) {
        this.localsolver = localsolver;
    }

    /* 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
        LSModel model = localsolver.getModel();

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

        // Weight constraint
        LSExpression knapsackWeight = model.sum();
        for (int i = 0; i < nbItems; ++i) {
            LSExpression 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) {
            LSExpression itemValue = model.prod(x[i], values[i]);
            knapsackValue.addOperand(itemValue);
        }

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

        // Parametrize the solver
        localsolver.getParam().setTimeLimit(limit);

        localsolver.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 (LocalSolver localsolver = new LocalSolver()) {
            Knapsack model = new Knapsack(localsolver);
            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);
        }
    }
}