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