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