this repo has no description
dekker.one
1/***
2!Test
3expected:
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
39int: K;
40 % Width of the Bin
41int: W;
42 % Height of the Bin
43int: H;
44 % Number of items to be packed
45int: N;
46 % Widths of the items
47array[1..N] of int: ItemWidth;
48 % Heights of the items
49array[1..N] of int: ItemHeight;
50
51 % Variable indicating if bin k is used.
52array[1..K] of var 0..1: bin;
53
54 % Variable indicating if item i is in bin k.
55array[1..K, 1..N] of var 0..1: item;
56
57 % The total number of bins has to be minimized
58solve minimize
59 sum( k in 1..K ) ( bin[k] ) ;
60
61 % Each item has to be packed.
62constraint
63 forall( j in 1..N ) (
64 sum( k in 1..K ) ( item[k, j] ) = 1
65 );
66
67 % subproblem constraints
68constraint
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 %
83predicate 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
106var int: obj;
107constraint
108 obj = sum( k in 1..K )( bin[k] );
109
110output
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
122N = 4;
123W = 5;
124H = 10;
125K = 2;
126ItemWidth = [ 1, 1, 2, 3 ];
127ItemHeight = [ 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 ];