lemon-project-template-glpk
view deps/glpk/examples/bpp.mod @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* BPP, Bin Packing Problem */
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
5 /* Given a set of items I = {1,...,m} with weight w[i] > 0, the Bin
6 Packing Problem (BPP) is to pack the items into bins of capacity c
7 in such a way that the number of bins used is minimal. */
9 param m, integer, > 0;
10 /* number of items */
12 set I := 1..m;
13 /* set of items */
15 param w{i in 1..m}, > 0;
16 /* w[i] is weight of item i */
18 param c, > 0;
19 /* bin capacity */
21 /* We need to estimate an upper bound of the number of bins sufficient
22 to contain all items. The number of items m can be used, however, it
23 is not a good idea. To obtain a more suitable estimation an easy
24 heuristic is used: we put items into a bin while it is possible, and
25 if the bin is full, we use another bin. The number of bins used in
26 this way gives us a more appropriate estimation. */
28 param z{i in I, j in 1..m} :=
29 /* z[i,j] = 1 if item i is in bin j, otherwise z[i,j] = 0 */
31 if i = 1 and j = 1 then 1
32 /* put item 1 into bin 1 */
34 else if exists{jj in 1..j-1} z[i,jj] then 0
35 /* if item i is already in some bin, do not put it into bin j */
37 else if sum{ii in 1..i-1} w[ii] * z[ii,j] + w[i] > c then 0
38 /* if item i does not fit into bin j, do not put it into bin j */
40 else 1;
41 /* otherwise put item i into bin j */
43 check{i in I}: sum{j in 1..m} z[i,j] = 1;
44 /* each item must be exactly in one bin */
46 check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= c;
47 /* no bin must be overflowed */
49 param n := sum{j in 1..m} if exists{i in I} z[i,j] then 1;
50 /* determine the number of bins used by the heuristic; obviously it is
51 an upper bound of the optimal solution */
53 display n;
55 set J := 1..n;
56 /* set of bins */
58 var x{i in I, j in J}, binary;
59 /* x[i,j] = 1 means item i is in bin j */
61 var used{j in J}, binary;
62 /* used[j] = 1 means bin j contains at least one item */
64 s.t. one{i in I}: sum{j in J} x[i,j] = 1;
65 /* each item must be exactly in one bin */
67 s.t. lim{j in J}: sum{i in I} w[i] * x[i,j] <= c * used[j];
68 /* if bin j is used, it must not be overflowed */
70 minimize obj: sum{j in J} used[j];
71 /* objective is to minimize the number of bins used */
73 data;
75 /* The optimal solution is 3 bins */
77 param m := 6;
79 param w := 1 50, 2 60, 3 30, 4 70, 5 50, 6 40;
81 param c := 100;
83 end;