Knapsack

Principles learned

  • Create a generic model that uses data
  • Read an instance from a file
  • Write the solution in a file

Problem

../_images/knapsack.png

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.

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

use io;

/* Reads 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();
}

/* Declares the optimization model. */
function model() {
    // 0-1 decisions
    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;
}

/* Parameterizes the solver. */
function param() {
    if (lsTimeLimit == nil) lsTimeLimit = 20; 
}

/* Writes 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\python27\
python knapsack.py instances\kp_100_1.in
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python knapsack.py instances/kp_100_1.in
########## knapsack.py ##########

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:

    #
    # Reads instance data
    #

    file_it = iter(read_integers(sys.argv[1]))

    # Number of items
    nb_items = file_it.next()

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


    # Knapsack bound
    knapsack_bound = file_it.next()
    
    #
    # Declares 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()

    #
    # Parameterizes the solver
    #
    if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
    else: ls.create_phase().time_limit = 20

    ls.solve()

    #
    # Writes 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\localsolver.dll.lib
knapsack instances\kp_100_1.in
Compilation / Execution (Linux)
g++ knapsack.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o knapsack
./knapsack instances/kp_100_1.in
//********* knapsack.cpp *********

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

using namespace localsolver;
using namespace std;

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

    // Items properties. 
    vector<lsint> weights;
    vector<lsint> values;

    // Knapsack bound 
    lsint knapsackBound;
    
    // LocalSolver. 
    LocalSolver localsolver;

    // Decision variables. 
    vector<LSExpression> x;

    // Objective. 
    LSExpression knapsackValue;

    // Solution (items in the knapsack). 
    vector<int> solution;

    // Reads 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) {
        // Declares 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 += itemWeight;
        }
        model.constraint(knapsackWeight <= knapsackBound);
    
        // Maximize value
        knapsackValue = model.sum();
        for (int i = 0; i < nbItems; i++) {
            LSExpression itemValue = x[i]*values[i];
            knapsackValue += itemValue;
        }
        model.maximize(knapsackValue);
        model.close();

        // Parameterizes the solver. 
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);
        localsolver.solve();

        solution.clear();
        for (int i = 0; i < nbItems; ++i)
            if (x[i].getValue() == 1) 
                solution.push_back(i);
    }

    // Writes 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 (unsigned int i = 0; i < solution.size(); ++i)
            outfile << solution[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 << "Error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc Knapsack.cs /reference:localsolvernet.dll
Knapsack instances\kp_100_1.in
/********** Knapsack.cs **********/

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;

    // Solver. 
    LocalSolver localsolver;

    // LS Program variables. 
    LSExpression[] x;

    // Objective.
    LSExpression knapsackValue;

    // Solutions    (items in the knapsack). 
    List<int> solutions;

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

    // Reads 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(' ');
            if (splittedWeights.Length < nbItems)
                throw new Exception("Wrong number of item weights");

            for (int i = 0; i < nbItems; i++)
                weights[i] = int.Parse(splittedWeights[i]);

            string[] splittedValues = input.ReadLine().Split(' ');
            if (splittedValues.Length < nbItems)
                throw new Exception("Wrong number of item values");

            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)
    {
        // Declares the optimization model.
        localsolver = new LocalSolver();
        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();

        // Parameterizes the solver.
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);

        localsolver.Solve();

        solutions = new List<int>();
        for (int i = 0; i < nbItems; ++i)
        {
            if (x[i].GetValue() == 1) solutions.Add(i);
        }
    }

    // Writes the solution in a file
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(knapsackValue.GetValue());
            for (int i = 0; i < solutions.Count; ++i)
                output.Write(solutions[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_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Knapsack instances/kp_100_1.in
/********** Knapsack.java **********/

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;

    // Solver. 
    private LocalSolver localsolver;

    // LS Program variables. 
    private LSExpression[] x;

    // Objective. 
    private LSExpression knapsackValue;
    
    // Solutions (classes at each position). 
    private List<Integer> solutions;

    // Reads 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) {
        // Declares the optimization model. 
        localsolver = new LocalSolver();
        LSModel model = localsolver.getModel();

        // boolean 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();

        // Parameterizes the solver. 
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);

        localsolver.solve();

        solutions = new ArrayList<Integer>();
        for (int i = 0; i < nbItems; i++) 
            if (x[i].getValue() == 1) 
        solutions.add(i);         
    }

    // Writes 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 < solutions.size(); ++i) 
                output.print(solutions.get(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 {
            Knapsack model = new Knapsack();
            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);
        }
    }
}