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