| 1 |
/*** |
| 2 |
!Test |
| 3 |
solvers: [gecode, chuffed] # Too slow on cbc |
| 4 |
expected: |
| 5 |
- !Result |
| 6 |
solution: !Solution |
| 7 |
x: [0, 70, 75, 0, 79, 50, 0, 50, 46, 27, 52, 35, 59, 35, 35, 50, 27, 52, 46, 75, 50] |
| 8 |
y: [0, 70, 33, 50, 0, 0, 85, 29, 88, 93, 70, 65, 54, 50, 82, 54, 85, 63, 82, 29, 63] |
| 9 |
***/ |
| 10 |
|
| 11 |
% TOO LONG mzn20_fd_linear |
| 12 |
% TOO LONG mzn20_mip |
| 13 |
%----------------------------------------------------------------------------- |
| 14 |
% Packing squares into a rectangle |
| 15 |
% |
| 16 |
% Guido Tack, [email protected] |
| 17 |
% 2007-02-22 |
| 18 |
% |
| 19 |
% Ported from the Gecode example |
| 20 |
% |
| 21 |
%----------------------------------------------------------------------------- |
| 22 |
|
| 23 |
%----------------------------------------------------------------------------- |
| 24 |
% Specification |
| 25 |
|
| 26 |
int: pack_x; |
| 27 |
int: pack_y; |
| 28 |
int: n; |
| 29 |
array[1..n] of int: pack_s; |
| 30 |
|
| 31 |
% Instance |
| 32 |
|
| 33 |
%pack_x = 4; |
| 34 |
%pack_y = 4; |
| 35 |
%n = 4; |
| 36 |
%pack_s = [2,2,2,2]; |
| 37 |
|
| 38 |
pack_x = 112; |
| 39 |
pack_y = 112; |
| 40 |
n = 21; |
| 41 |
pack_s = [50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2]; |
| 42 |
|
| 43 |
%----------------------------------------------------------------------------- |
| 44 |
% Model |
| 45 |
|
| 46 |
array[1..n] of var 0..pack_x-1: x; |
| 47 |
array[1..n] of var 0..pack_y-1: y; |
| 48 |
|
| 49 |
constraint |
| 50 |
forall (i in 1..n) ( |
| 51 |
x[i] <= pack_x - pack_s[i] /\ |
| 52 |
y[i] <= pack_y - pack_s[i] |
| 53 |
) |
| 54 |
/\ |
| 55 |
forall (i in 1..n, j in i+1..n) ( |
| 56 |
x[j] - x[i] >= pack_s[i] \/ |
| 57 |
x[i] - x[j] >= pack_s[j] \/ |
| 58 |
y[j] - y[i] >= pack_s[i] \/ |
| 59 |
y[i] - y[j] >= pack_s[j] |
| 60 |
); |
| 61 |
|
| 62 |
% Symmetry breaking |
| 63 |
|
| 64 |
constraint |
| 65 |
forall (i in 1..n-1) ( |
| 66 |
if pack_s[i]=pack_s[i+1] then |
| 67 |
x[i] <= x[i+1] |
| 68 |
else |
| 69 |
true |
| 70 |
endif |
| 71 |
); |
| 72 |
|
| 73 |
% Capacity constraints |
| 74 |
|
| 75 |
constraint |
| 76 |
forall (cx in 0..pack_x-1) ( |
| 77 |
sum (i in 1..n) (pack_s[i]*bool2int(x[i] in cx-pack_s[i]+1..cx)) = pack_x |
| 78 |
) |
| 79 |
/\ |
| 80 |
forall (cy in 0..pack_y-1) ( |
| 81 |
sum (i in 1..n) (pack_s[i]*bool2int(y[i] in cy-pack_s[i]+1..cy)) = pack_y |
| 82 |
); |
| 83 |
|
| 84 |
solve ::seq_search([int_search(x,smallest,indomain_min,complete), |
| 85 |
int_search(y,smallest,indomain_min,complete)]) |
| 86 |
satisfy; |
| 87 |
|
| 88 |
output [ |
| 89 |
"packing ",show(n)," squares into a ",show(pack_x),"x",show(pack_y), |
| 90 |
" rectangle:\n"] ++ |
| 91 |
[ "square "++show(i)++ |
| 92 |
", size "++show(pack_s[i])++"x"++show(pack_s[i])++ |
| 93 |
", at ("++show(x[i])++", "++show(y[i])++")\n" | i in 1..n]; |