Description

Basic form of the knapsack problem: Given a set of potential items i
to put into a knapsack of weight capacity c. Each item has a profit p
and a weight w. The task is to select a subset of the items which
maximizes the total utility of the selection while not exceeding
the weight limit c of the knapsack.

Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack Problems.
Springer-Verlag Berlin Heidelberg 2004. Page 3.

Keywords: mixed integer linear programming, combinatorial optimization

Small Model of Type : MIP

Category : GAMS Model library

Main file : knapsack.gms

$title Binary knapsack problem (KNAPSACK,SEQ=436)

$onText
Basic form of the knapsack problem: Given a set of potential items i
to put into a knapsack of weight capacity c. Each item has a profit p
and a weight w. The task is to select a subset of the items which
maximizes the total utility of the selection while not exceeding
the weight limit c of the knapsack.

Hans Kellerer, Ulrich Pferschy, David Pisinger. Knapsack Problems.
Springer-Verlag Berlin Heidelberg 2004. Page 3.

Keywords: mixed integer linear programming, combinatorial optimization
$offText

set i 'items';
parameters
    p(i) 'profits'
    w(i) 'weights'
    c 'capacity';

free variable z 'objective';
binary variable x 'choice';

equations cap_restr, utility;
cap_restr .. sum(i, w(i)*x(i)) =l= c;
utility .. z =e= sum(i, p(i)*x(i));

z.lo = 0;

model knapsack /all/;

* Example instance
set i /i1*i10/;
c = 269;

table data
    p  w
i1  55 95
i2  10  4
i3  47 60
i4   5 32
i5   4 23
i6  50 72
i7   8 80
i8  61 62
i9  85 65
i10 87 46;

p(i) = data(i,'p');
w(i) = data(i,'w');

solve knapsack using mip max z;