| 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 |
%-----------------------------------------------------------------------------% |