Debian Codegraph @

tests/spec/examples/factory_planning_instance.mzn

raw
1 /***
2 !Test
3 check_against: []
4 expected:
5 - !Result
6 solution: !Solution
7 last_step: 5
8 extra_files: []
9 markers: []
10 options:
11 all_solutions: false
12 solvers:
13 - gecode
14 - cbc
15 - chuffed
16 type: solve
17
18 ***/
19
20 % A factory has three kinds of machines:
21 % - input machines, where products enter the factory;
22 % - output machines, where finished products leave the factory;
23 % - work machines, which can hold at most one product and which may
24 % add some attributes to that product.
25 %
26 % A product can move from one machine to another iff there is a direct
27 % connection between the two machines (we model staying at a particular
28 % machine by making the connection graph reflexive).
29 %
30 % In this model all actions are assumed to take the same amount of time.
31 %
32 % The goal is to complete a set of products in the shortest time.
33 % XXX Optimisation is currently very expensive; we settle instead
34 % for merely finding a consistent solution.
35
36 % These values must be supplied by a data file.
37 %
38 int: n_machines; % The number of machines.
39 int: n_products; % The number of products.
40 int: n_attributes; % The number of attributes.
41 int: n_steps; % The number of plan steps.
42
43 set of int: machines = 1..n_machines;
44 set of int: products = 1..n_products;
45 set of int: attributes = 1..n_attributes;
46 set of int: steps = 1..n_steps;
47
48 % These values must be supplied by a data file:
49 % - input_machines - the set of machines where products can start;
50 % - output_machines - the set of machines where products may finish;
51 % - connected - the (reflexive) graph of inter-machine connections;
52 % - can_add_attr - table of which machines can add which attributes;
53 % - prod_attr_goal - table of goal attributes for each product;
54 % - prod_start_mach - table of starting machines for each product.
55 %
56 set of machines: input_machines;
57 set of machines: output_machines;
58 array [machines, machines] of 0..1: connected;
59 array [machines, attributes] of 0..1: can_add_attr;
60 array [products, attributes] of 0..1: prod_attr_goal;
61 array [products] of input_machines: prod_start_mach;
62
63 % Decision variables:
64 % - step_prod_attr[s, p, a] - at step s, product p has attribute a;
65 % - step_prod_mach[s, p] = m - at step s, product p is at machine m;
66 % - last_step - the step at which the goal is achieved.
67 %
68 array [steps, products, attributes] of var 0..1: step_prod_attr;
69 array [steps, products] of var machines: step_prod_mach;
70 var steps: last_step;
71
72 % Work machines are those that are neither input machines or output machines.
73 %
74 set of machines: work_machines =
75 machines diff (input_machines union output_machines);
76
77 % Products start at particular machines.
78 %
79 constraint
80 forall (p in products) (
81 step_prod_mach[1, p] = prod_start_mach[p]
82 );
83
84 % Products start with no attributes.
85 %
86 constraint
87 forall (p in products, a in attributes) (
88 step_prod_attr[1, p, a] = 0
89 );
90
91 % The attributes of a product at step s are a subset of its
92 % attributes at step s+1.
93 %
94 constraint
95 forall (s in steps, p in products, a in attributes where s < n_steps) (
96 step_prod_attr[s, p, a] <= step_prod_attr[s + 1, p, a]
97 );
98
99 % No two products can occupy the same work machine at the same step.
100 %
101 constraint
102 forall (s in steps, p, q in products, m in work_machines where p < q) (
103 step_prod_mach[s, p] = m -> step_prod_mach[s, q] != m
104 );
105
106 % At t = last_step all goals should be achieved:
107 % - each product should have (precisely) its goal set of attributes;
108 % - each product should be in an output machine.
109 %
110 constraint
111 forall (p in products, a in attributes) (
112 step_prod_attr[last_step, p, a] = prod_attr_goal[p, a]
113 );
114
115 constraint
116 forall (p in products) (
117 step_prod_mach[last_step, p] in output_machines
118 );
119
120 % Products can only move between directly connected machines.
121 %
122 constraint
123 forall (s in steps, p in products where s < n_steps) (
124 connected[step_prod_mach[s, p], step_prod_mach[s + 1, p]] = 1
125 );
126
127 % A product can have an attribute added while at a particular machine.
128 %
129 constraint
130 forall (s in steps, p in products, a in attributes where s < n_steps) (
131 step_prod_attr[s + 1, p, a] <=
132 step_prod_attr[s, p, a]
133 + can_add_attr[step_prod_mach[s, p], a]
134 );
135
136 % XXX Trying to optimize for last_step currently takes forever, even for
137 % relatively simple problems.
138 %
139 % solve minimize last_step;
140 %
141 last_step = n_steps;
142 % solve satisfy;
143
144 % Instance data
145
146 n_machines = 5;
147 n_products = 2;
148 n_attributes = 3;
149 n_steps = 5;
150
151 input_machines = {1};
152
153 output_machines = {5};
154
155 % Connections:
156 %
157 % M1 --- M2 ----.
158 % | | |
159 % |----- M3 --- M5
160 % | | |
161 % '----- M4 ----'
162
163 connected =
164 [| 1, 1, 1, 1, 0,
165 | 1, 1, 1, 0, 1,
166 | 1, 1, 1, 1, 1,
167 | 1, 0, 1, 1, 1,
168 | 0, 1, 1, 1, 1
169 |];
170
171 can_add_attr =
172 [| 0, 0, 0
173 | 1, 0, 0
174 | 0, 1, 0
175 | 0, 0, 1
176 | 0, 0, 0
177 |];
178
179 prod_start_mach = [
180 1,
181 1
182 ];
183
184 prod_attr_goal =
185 [| 1, 1, 0
186 | 1, 0, 1
187 |];
188
189 solve satisfy;
190
191 output [
192 "factory planning instance\n",
193 "step | product | location | a1 a2 a3\n",
194 "-----+---------+----------+---------\n",
195 " 1 | 1 | ", show(step_prod_mach[1, 1]), " | ",
196 show(step_prod_attr[1, 1, 1]), " ",
197 show(step_prod_attr[1, 1, 2]), " ",
198 show(step_prod_attr[1, 1, 3]), "\n",
199 " | 2 | ", show(step_prod_mach[1, 2]), " | ",
200 show(step_prod_attr[1, 2, 1]), " ",
201 show(step_prod_attr[1, 2, 2]), " ",
202 show(step_prod_attr[1, 2, 3]), "\n",
203 "-----+---------+----------+---------\n",
204 " 2 | 1 | ", show(step_prod_mach[2, 1]), " | ",
205 show(step_prod_attr[2, 1, 1]), " ",
206 show(step_prod_attr[2, 1, 2]), " ",
207 show(step_prod_attr[2, 1, 3]), "\n",
208 " | 2 | ", show(step_prod_mach[2, 2]), " | ",
209 show(step_prod_attr[2, 2, 1]), " ",
210 show(step_prod_attr[2, 2, 2]), " ",
211 show(step_prod_attr[2, 2, 3]), "\n",
212 "-----+---------+----------+---------\n",
213 " 3 | 1 | ", show(step_prod_mach[3, 1]), " | ",
214 show(step_prod_attr[3, 1, 1]), " ",
215 show(step_prod_attr[3, 1, 2]), " ",
216 show(step_prod_attr[3, 1, 3]), "\n",
217 " | 2 | ", show(step_prod_mach[3, 2]), " | ",
218 show(step_prod_attr[3, 2, 1]), " ",
219 show(step_prod_attr[3, 2, 2]), " ",
220 show(step_prod_attr[3, 2, 3]), "\n",
221 "-----+---------+----------+---------\n",
222 " 4 | 1 | ", show(step_prod_mach[4, 1]), " | ",
223 show(step_prod_attr[4, 1, 1]), " ",
224 show(step_prod_attr[4, 1, 2]), " ",
225 show(step_prod_attr[4, 1, 3]), "\n",
226 " | 2 | ", show(step_prod_mach[4, 2]), " | ",
227 show(step_prod_attr[4, 2, 1]), " ",
228 show(step_prod_attr[4, 2, 2]), " ",
229 show(step_prod_attr[4, 2, 3]), "\n",
230 "-----+---------+----------+---------\n",
231 " 5 | 1 | ", show(step_prod_mach[5, 1]), " | ",
232 show(step_prod_attr[5, 1, 1]), " ",
233 show(step_prod_attr[5, 1, 2]), " ",
234 show(step_prod_attr[5, 1, 3]), "\n",
235 " | 2 | ", show(step_prod_mach[5, 2]), " | ",
236 show(step_prod_attr[5, 2, 1]), " ",
237 show(step_prod_attr[5, 2, 2]), " ",
238 show(step_prod_attr[5, 2, 3]), "\n",
239 "-----+---------+----------+---------\n"
240 ];