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