GLPK/Knapsack Problem

The knapsack problem is a classical packing problem from combinatorial optimization. The knapsack problem can be defined as follows: given a set of items of size and profit , select a subset of those items which fit into capacity and which maximize the collective profit of the chosen items: maximize subject to The knapsack problem belongs to the class of NP-hard problems Kellerer Hans Pferschy Ulrich Pferschy David Knapsack Problems Springer-Verlag 2004 3-540-40286-1 Kel04. 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: 1 4 5 8 Because the problem has symmetry, the solution obtained might also be: 2 4 5 8. References