COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/examples/bpp.mod @ 11:4fc6ad2fb8a6

subpack-glpk
Last change on this file since 11:4fc6ad2fb8a6 was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 2.2 KB
Line 
1/* BPP, Bin Packing Problem */
2
3/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
4
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. */
8
9param m, integer, > 0;
10/* number of items */
11
12set I := 1..m;
13/* set of items */
14
15param w{i in 1..m}, > 0;
16/* w[i] is weight of item i */
17
18param c, > 0;
19/* bin capacity */
20
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. */
27
28param 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 */
30
31   if i = 1 and j = 1 then 1
32   /* put item 1 into bin 1 */
33
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 */
36
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 */
39
40   else 1;
41   /* otherwise put item i into bin j */
42
43check{i in I}: sum{j in 1..m} z[i,j] = 1;
44/* each item must be exactly in one bin */
45
46check{j in 1..m}: sum{i in I} w[i] * z[i,j] <= c;
47/* no bin must be overflowed */
48
49param 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 */
52
53display n;
54
55set J := 1..n;
56/* set of bins */
57
58var x{i in I, j in J}, binary;
59/* x[i,j] = 1 means item i is in bin j */
60
61var used{j in J}, binary;
62/* used[j] = 1 means bin j contains at least one item */
63
64s.t. one{i in I}: sum{j in J} x[i,j] = 1;
65/* each item must be exactly in one bin */
66
67s.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 */
69
70minimize obj: sum{j in J} used[j];
71/* objective is to minimize the number of bins used */
72
73data;
74
75/* The optimal solution is 3 bins */
76
77param m := 6;
78
79param w := 1 50, 2 60, 3 30, 4 70, 5 50, 6 40;
80
81param c := 100;
82
83end;
Note: See TracBrowser for help on using the repository browser.