# GLPK/Knapsack Problem

Jump to navigation Jump to search

The knapsack problem is a classical packing problem from combinatorial optimization.

The knapsack problem can be defined as follows: given a set of ${\displaystyle N}$ items of size ${\displaystyle s_{i}}$ and profit ${\displaystyle p_{i}}$, select a subset of those items which fit into capacity ${\displaystyle c}$ and which maximize the collective profit of the chosen items:

 maximize ${\displaystyle \sum _{N}p_{i}x_{i}\quad x_{i}\in \{0,1\}}$ subject to ${\displaystyle \sum _{N}s_{i}x_{i}\leq c}$

The knapsack problem belongs to the class of NP-hard problems [1].

A usual way to solve knapsack problems is through dynamic programming (DP). The example below shows how to formulate the knapsack problem as a mixed-integer program (MIP) implemented in GMPL (MathProg).

# en.wikipedia.org offers the following definition:
# The knapsack problem or rucksack problem is a problem in combinatorial optimization:
# Given a set of items, each with a weight and a value, determine the number of each
# item to include in a collection so that the total weight is less than a given limit
# and the total value is as large as possible.
#
# This file shows how to model a knapsack problem in GMPL.

# Size of knapsack
param c;

# Items: index, size, profit
set I, dimen 3;

# Indices
set J := setof{(i,s,p) in I} i;

# Assignment
var a{J}, binary;

maximize obj :
sum{(i,s,p) in I} p*a[i];

s.t. size :
sum{(i,s,p) in I} s*a[i] <= c;

solve;

printf "The knapsack contains:\n";
printf {(i,s,p) in I: a[i] == 1} " %i", i;
printf "\n";

data;

# Size of the knapsack
param c := 100;

# Items: index, size, profit
set I :=
1 10 10
2 10 10
3 15 15
4 20 20
5 20 20
6 24 24
7 24 24
8 50 50;

end;


Now save and run this model using GLPSOL (1 second on an Intel Core i5 processor).

\$ glpsol --math knapsack.mod


To yield:

The knapsack contains:
2 4 5 8


## References

1. Kellerer, Hans; Pferschy, Ulrich; Pferschy, David (2004). Knapsack Problems. Springer-Verlag. ISBN 3-540-40286-1.