Debian Codegraph @

tests/spec/examples/2DPacking.mzn

raw
1 /***
2 !Test
3 expected:
4 - !Result
5 solution: !Solution
6 bin: [0, 1]
7 item:
8 - [0, 0, 0, 0]
9 - [1, 1, 1, 1]
10 obj: 1
11 objective: 1
12 - !Result
13 solution: !Solution
14 bin:
15 - 1
16 - 0
17 item:
18 - [1, 1, 1, 1]
19 - [0, 0, 0, 0]
20 obj: 1
21 objective: 1
22 ***/
23
24 %------------------------------------------------------------------------------%
25 % 2DPacking.mzn
26 % Jakob Puchinger
27 % October 29 2007
28 % vim: ft=zinc ts=4 sw=4 et tw=0
29 %------------------------------------------------------------------------------%
30 % Two-dimensional Bin Packing
31 %
32 % n rectangular items with given height and width have to be packed into
33 % rectangular bins of size W x H
34 % It is assumed that the items are sorted according to non-increasing height.
35 %
36 %------------------------------------------------------------------------------%
37
38 % Upper Bound on the number of Bins used
39 int: K;
40 % Width of the Bin
41 int: W;
42 % Height of the Bin
43 int: H;
44 % Number of items to be packed
45 int: N;
46 % Widths of the items
47 array[1..N] of int: ItemWidth;
48 % Heights of the items
49 array[1..N] of int: ItemHeight;
50
51 % Variable indicating if bin k is used.
52 array[1..K] of var 0..1: bin;
53
54 % Variable indicating if item i is in bin k.
55 array[1..K, 1..N] of var 0..1: item;
56
57 % The total number of bins has to be minimized
58 solve minimize
59 sum( k in 1..K ) ( bin[k] ) ;
60
61 % Each item has to be packed.
62 constraint
63 forall( j in 1..N ) (
64 sum( k in 1..K ) ( item[k, j] ) = 1
65 );
66
67 % subproblem constraints
68 constraint
69 forall( k in 1..K ) (
70 is_feasible_packing(bin[k], [ item[k, j] | j in 1..N ])
71 );
72
73 % This predicate defines a feasible packing
74 % as a 2-stage guillotine pattern (level pattern).
75 % A Bin consists of one or several levels
76 % and each level consist of one or several items.
77 % The height of a level is given by its highest (first) item.
78 % Variable x[i, j] indicates if item i is put in level j
79 % x[j, j] also indicate that level j is used.
80 %
81 % Note, k is locally fixed, so this is the pattern for the k'th bin.
82 %
83 predicate is_feasible_packing(var 0..1: s_bin,
84 array[1..N] of var 0..1: s_item) = (
85 let {array[1..N, 1..N] of var 0..1: x} in (
86 forall ( i in 1..N ) (
87 % Width of items on level can not exceed W
88 sum( j in i..N ) ( ItemWidth[j] * x[i, j] ) <= W * x[i, i]
89 /\
90 % first item in level is highest
91 % XXX do not need to generate those variables (use default)
92 forall( j in 1..i-1 ) ( x[i, j] = 0 )
93 )
94 /\
95 % Height of levels on bin can not exceed H
96 sum( i in 1..N ) ( ItemHeight[i] * x[i, i] ) <= s_bin * H
97 /\
98 % for all items associate item on bin with item on level.
99 forall(j in 1..N) (
100 s_item[j] = sum( i in 1..j ) ( x[i, j] )
101 )
102 )
103 );
104
105 % required for showing the objective function
106 var int: obj;
107 constraint
108 obj = sum( k in 1..K )( bin[k] );
109
110 output
111 [ "Number of used bins = ", show( obj ), "\n"] ++
112 [ "Items in bins = \n\t"] ++
113 [ show(item[k, j]) ++ if j = N then "\n\t" else " " endif |
114 k in 1..K, j in 1..N ] ++
115 [ "\n" ];
116
117 %------------------------------------------------------------------------------%
118 %
119 % Test data (Not in separate file, so that mzn2lp can handle it).
120 %
121
122 N = 4;
123 W = 5;
124 H = 10;
125 K = 2;
126 ItemWidth = [ 1, 1, 2, 3 ];
127 ItemHeight = [ 4, 4, 4, 3 ];
128
129 %N = 6;
130 %W = 5;
131 %H = 10;
132 %K = N;
133 %ItemWidth = [ 4, 4, 1, 1, 2, 3 ];
134 %ItemHeight = [ 6, 5, 4, 4, 4, 3 ];