this repo has no description
dekker.one
1/***
2!Test
3solvers: [gecode, chuffed] # Too slow on cbc
4expected:
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
35S = 9;
36t = 2;
37n = 7;
38d = [250, 255, 260, 500, 500, 800, 1100];
39
40%-----------------------------------------------------------------------------%
41
42include "globals.mzn";
43
44int: S; % Number of slots per template.
45int: t; % Number of templates.
46int: n; % Number of variations.
47array[1..n] of int: d; % How much of each variation we must print?
48
49% Lower and upper bounds for the total production.
50%
51int: llower = ceil(sum(i in 1..n)(int2float(d[i]))/int2float(S));
52int: 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%
56array[1..n,1..t] of var 0..S: p;
57
58% # Pressings of template j.
59%
60array[1..t] of var 1..lupper: R;
61
62var llower..lupper: Production; % Sum of all Rj.
63var 0..lupper-llower: Surplus; % Production x S - sum(d[i])
64
65% First, set up Production to be the sum of the Rj
66constraint
67 Production = sum(i in 1..t)(R[i]);
68
69% the limits on production
70constraint
71 Production >= llower /\ Production <= lupper;
72
73% The number of slots occupied in each template is S.
74constraint
75 forall(j in 1..t)
76 (sum(i in 1..n)(p[i,j]) = S);
77
78% Enough of each variation is printed.
79constraint
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.
85constraint
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
96constraint
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.
113constraint
114 Surplus = Production*S - sum(i in 1..n)(d[i]);
115
116% The surplus of each variation is also limited by the surplus.
117constraint
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.
122constraint
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.
127constraint
128 if t=2 then (
129 R[1] <= Production div 2
130 /\ R[2] >= Production div 2
131 ) else true endif;
132
133constraint
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.
141solve :: int_search(array1d(1..n*t,p) ++ R, input_order, indomain_min, complete)
142 minimize Production;
143
144output [
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%-----------------------------------------------------------------------------%