this repo has no description
dekker.one
1/***
2!Test
3solvers: [gecode, chuffed] # Too slow on cbc
4expected:
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, tack@gecode.org
17% 2007-02-22
18%
19% Ported from the Gecode example
20%
21%-----------------------------------------------------------------------------
22
23%-----------------------------------------------------------------------------
24% Specification
25
26int: pack_x;
27int: pack_y;
28int: n;
29array[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
38pack_x = 112;
39pack_y = 112;
40n = 21;
41pack_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
46array[1..n] of var 0..pack_x-1: x;
47array[1..n] of var 0..pack_y-1: y;
48
49constraint
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
64constraint
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
75constraint
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
84solve ::seq_search([int_search(x,smallest,indomain_min,complete),
85 int_search(y,smallest,indomain_min,complete)])
86 satisfy;
87
88output [
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];