| 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 ]; |