Debian Codegraph @

tests/spec/examples/template_design.mzn

raw
1 /***
2 !Test
3 solvers: [gecode, chuffed] # Too slow on cbc
4 expected:
5 - !Result
6 solution: !Solution
7 Production: 442
8 R:
9 - 167
10 - 275
11 Surplus: 313
12 objective: 442
13 p:
14 - [0, 1]
15 - [2, 0]
16 - [1, 1]
17 - [3, 0]
18 - [3, 0]
19 - [0, 3]
20 - [0, 4]
21 ***/
22
23 %-----------------------------------------------------------------------------%
24 % Template design
25 % Problem 002 in CSPLib
26 %-----------------------------------------------------------------------------%
27 % Based on "ILP and Constraint Programming Approaches to a Template
28 % Design Problem", Les Proll and Barbara Smith, School of Computing
29 % Research Report 97.16, University of Leeds, May 1997.
30 %-----------------------------------------------------------------------------%
31
32 %-----------------------------------------------------------------------------%
33 % Instance
34
35 S = 9;
36 t = 2;
37 n = 7;
38 d = [250, 255, 260, 500, 500, 800, 1100];
39
40 %-----------------------------------------------------------------------------%
41
42 include "globals.mzn";
43
44 int: S; % Number of slots per template.
45 int: t; % Number of templates.
46 int: n; % Number of variations.
47 array[1..n] of int: d; % How much of each variation we must print?
48
49 % Lower and upper bounds for the total production.
50 %
51 int: llower = ceil(sum(i in 1..n)(int2float(d[i]))/int2float(S));
52 int: lupper = 2*llower; % If t>1, this should be the optimal Production_{t-1}-1.
53
54 % # Slots allocated to variation i in template j.
55 %
56 array[1..n,1..t] of var 0..S: p;
57
58 % # Pressings of template j.
59 %
60 array[1..t] of var 1..lupper: R;
61
62 var llower..lupper: Production; % Sum of all Rj.
63 var 0..lupper-llower: Surplus; % Production x S - sum(d[i])
64
65 % First, set up Production to be the sum of the Rj
66 constraint
67 Production = sum(i in 1..t)(R[i]);
68
69 % the limits on production
70 constraint
71 Production >= llower /\ Production <= lupper;
72
73 % The number of slots occupied in each template is S.
74 constraint
75 forall(j in 1..t)
76 (sum(i in 1..n)(p[i,j]) = S);
77
78 % Enough of each variation is printed.
79 constraint
80 forall(i in 1..n)
81 (sum(j in 1..t)(p[i,j]*R[j]) >= d[i]);
82
83 % Symmetry constraints.
84 % Variations with the same demand are symmetric.
85 constraint
86 forall (i in 1..n-1) (
87 if d[i] == d[i+1] then
88 lex_lesseq([p[i, j] | j in 1..t],
89 [p[i+1,j] | j in 1..t])
90 else
91 true
92 endif
93 );
94
95 % pseudo symmetry
96 constraint
97 forall(i in 1..n-1) (
98 if d[i] < d[i+1] then
99 sum (j in 1..t) (p[i,j]*R[j])
100 < sum (j in 1..t) (p[i+1,j]*R[j])
101 else
102 true
103 endif
104 );
105
106 % implied constraints on the surplus
107
108 % These are presented in the paper as necessary to get good
109 % performance for this model, but I think bounds consistency on the
110 % sum(R[i]) constraint would produce the same amount of propagation
111
112 % Set up surplus, which is bounded as production is bounded.
113 constraint
114 Surplus = Production*S - sum(i in 1..n)(d[i]);
115
116 % The surplus of each variation is also limited by the surplus.
117 constraint
118 forall(k in 1..n)
119 (sum(j in 1..t)(p[k,j]*R[j]-d[k]) <= Surplus);
120
121 % The surplus of the first k variations is limited by the surplus.
122 constraint
123 forall(k in 2..n-1)
124 (sum(j in 1..t, m in 1..k)( p[m,j]*R[j]-d[m] ) <= Surplus);
125
126 % Implied constraints on the run length.
127 constraint
128 if t=2 then (
129 R[1] <= Production div 2
130 /\ R[2] >= Production div 2
131 ) else true endif;
132
133 constraint
134 if t=3 then (
135 R[1] <= Production div 3
136 /\ R[2] <= Production div 2
137 /\ R[3] >= Production div 3
138 ) else true endif;
139
140 % Minimize the production.
141 solve :: int_search(array1d(1..n*t,p) ++ R, input_order, indomain_min, complete)
142 minimize Production;
143
144 output [
145 if v = 1 then "template #" ++ show(i) ++ ": [" else "" endif ++
146 show(p[v, i]) ++
147 if v = n then "], pressings: " ++ show(R[i]) ++ "\n" else ", " endif
148 | i in 1..t, v in 1..n]
149 ++ ["Total pressings: ", show(Production), "\n"];
150
151 %-----------------------------------------------------------------------------%
152 %-----------------------------------------------------------------------------%