A set of benchmarks to compare a new prototype MiniZinc implementation
dekker.one
1% NOTE: the formulation of this problem that was used in the 2009
2% MiniZinc challenge is in the file roster_model.old. (That formulation
3% is not compatible with MiniZinc 1.1 and above.)
4
5%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6% FIT3022
7% Assignment 1
8% Rostering Problem
9% Example Solution
10% 6th May 2008
11%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12
13% This model should be paired with a data file, viz.
14% mzn_run(chicroster,data_A, fzn_ic)
15
16% An example data file data_A is as follows:
17 % reqt = [3,2,1,0,1,1,5,
18 % 1,0,1,0,1,2,0,
19 % 1,2,0,1,1,1,0,
20 % 0,1,2,2,2,1,0,
21 % 0,0,1,2,0,0,0] ;
22 %
23 % weeks = 5 ;
24
25
26%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
27% Model
28%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
29
30% Import predicates 'exactly', at_most', 'at_least'
31include "exactly.mzn";
32include "at_most.mzn";
33include "at_least.mzn";
34
35%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36% Parameters
37%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
38
39% "weeks" and "reqt" are imported from the data file.
40% "flatsize" is a constant computed from the parameter "weeks", which is used
41% in the model.
42%
43int: weeks ;
44int: flatsize = 7 * weeks ;
45array [1..5,1..7] of int: reqt ;
46int: minobj;
47
48% The following parameters aid readability of the model.
49%
50int:Rest=1;
51int:Morn=2;
52int:Day=3;
53int:Eve=4;
54int:Joker=5;
55
56% The following two variables will hold the costs due to violated soft
57% constraints.
58%
59var 0..flatsize: evemorn ;
60var 0..flatsize: isolated ;
61
62var minobj..2*flatsize: objective = evemorn + isolated;
63
64% The roster is an array of decision variables: each variable has domain 1..5
65% representing possible shifts Rest,Morn,Day,Eve or Joker roster is a
66% two-dimensional array with a row for each week
67array [1..weeks,1..7] of var 1..5: roster;
68
69% flatroster is a one-dimensional array, which will contain exactly the same set of variables
70array [1..flatsize] of var 1..5: flatroster ;
71array [1..flatsize+6] of var 1..5: longflatroster ;
72
73%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
74% Constraints
75%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
76
77constraint
78 forall (d in 1..6) (longflatroster[flatsize+d] = flatroster[d]);
79
80%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
81% Hard Constraints
82%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
83
84%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
85%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
86% Roster Flat-Roster constraint
87%
88% Description:
89% This constraint ensures that roster and flatroster contain the same set of
90% variables. The first seven variables in flatroster correspond to the first
91% row (week) in roster. The 8th to the 14th variables in flatroster correspond
92% to the second row in roster, etc. The total number of variables is the
93% number of weeks times 7.
94%
95% Example violation:
96% This constraint is violated if a variable in flatroster is different from the corresponding
97% variable in roster, e.g.
98%
99% flatroster = [1,2,2,2,2,2,2,2,2,2,2,2,2,2]
100% roster = [2,2,2,2,2,2,2,
101% 2,2,2,2,2,2,2]
102%
103% The first day of week one is different in flatroster and roster
104%
105%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
106
107constraint
108 forall (w in 1..weeks, d in 1..7) (flatroster[7*(w-1)+d] = roster[w,d]) ; %:: defines_var(roster) ;
109
110%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
111%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
112% Requirement Constraint
113%
114% Description:
115% The roster shifts must meet the requirement specified in the data
116% Each day of the week, the sum of the sifts of each type must match the
117% required number for the given shift type on the given day of the week
118%
119% Example violation:
120%
121% % M T W T F S S
122 % reqt = [0,0,0,0,0,2,2,
123 % 1,1,0,1,1,0,0,
124 % 1,1,0,1,1,0,0,
125 % 0,0,2,0,0,0,0,
126 % 0,0,0,0,0,0,0] ;
127 %
128 % weeks = 2 ;
129%
130%
131%
132% roster = [3,2,4,2,2,1,1,
133% 3,3,4,3,3,1,1]
134% This solution does not match the requirement for Monday
135% (two Day shifts instead of a Morning and a Day shift).
136%
137%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
138
139constraint
140 forall (shift in 1..5)
141 (forall (day in 1..7)
142 (exactly(reqt[shift,day],[roster[week,day] | week in 1..weeks],shift))
143 );
144
145%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
146%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
147% Enough Rest Constraint
148%
149% Description:
150% Ensure that in any sequence of 7 days, at least one of them is a Rest day.
151%
152% Example violation:
153% roster = [1,2,4,2,2,2,2,
154% 3,3,4,3,3,1,1]
155% This solution has 11 working days in a row, starting on Tuesday in week 1
156% and ending on Saturday in week 2
157%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
158
159constraint
160 forall (d in 1..flatsize)
161 (at_least(1,[longflatroster[d2]|d2 in d..d+6],Rest)) ;
162
163%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
164% Too Much Rest Constraint
165%
166% Description:
167% Ensure that there is no sequence of three Rest days in a row
168%
169% Example violation:
170% roster = [1,2,4,2,2,2,2,
171% 3,3,4,3,3,1,1]
172% This solution has three Rest days in a row, starting on the Saturday of
173% week 2 and ending on the Monday of week 1
174%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
175
176constraint
177 forall (d in 1..flatsize)
178 (at_most(3,[longflatroster[d2]|d2 in d..d+3],Rest)) ;
179
180%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
181% Soft Constraints
182%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
183
184
185%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
186% Not Evening before Morning Constraint
187%
188% Description:
189% For every occurrence in the roster of an Eve shift (4) followed by a Morn
190% shift (2) incur a cost of 1. Sum up these costs over the whole roster
191%
192% Example Violation:
193% roster = [1,2,4,2,2,2,2,
194% 3,3,4,3,3,1,1]
195%
196% On Tuesday of week 1 there is an Eve shift followed by a Morn shift on
197% Wednesday.
198%
199%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
200
201% The proposition condition
202% flatroster[d]=Eve /\ flatroster[(d mod flatsize)+1] = Morn
203% is true whenever an Eve is followed by a Morn.
204% bool2int converts true to a cost of 1. If the proposition is false
205% (i.e. the constraint is not violated), then bool2int returns 0.
206% The sum over all sequences is therefore the number of violations
207constraint
208 evemorn = sum(d in 1..flatsize)
209 (bool2int(flatroster[d]=Eve /\
210 longflatroster[d+1] = Morn )
211 );
212
213%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
214%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
215% No Isolated Rest Day Constraint
216%
217% Description:
218% An isolated Rest day is a Rest day with a non-Rest-day on the day before and
219% on the day after. Each such isolated Rest day incurs a cost of 1, and the
220% costs are summed up over the whole roster.
221%
222% Example Violation:
223% roster = [1,2,4,2,2,2,2,
224% 1,3,4,3,3,1,1]
225% The Monday of week 2 is preceded by a Morn shift and followed by a Day shift.
226%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
227
228% Using the syntax != for 'not-equals', the propositional formula
229% flatroster[d-1] != Rest /\ flatroster[d] = Rest /\ flatroster[d+1] != Rest
230% holds if and only if d is an isolated Rest day.
231
232constraint
233 isolated = sum(d in 1..flatsize)
234 (bool2int( (longflatroster[d+1] = Rest /\
235 not(flatroster[d] = Rest \/ longflatroster[d+2] = Rest)))
236 ) ;
237
238%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
239
240%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
241% Solve Item
242%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
243% A solution with minimal cost (evemorn+isolated) due to violations is sought.
244% There may be different solutions with the same, minimal, cost.
245% Only one solution is found by this model
246
247% Unfortunately the facilities for controlling search, which are necessary for
248% getting good solving performance on most problems, have not been covered in FIT3022
249% This model works well on all the data instances provided, but unfortunately
250% small changes to the model can unpredictably, and dramatically, impact performance.
251
252solve
253 :: int_search(flatroster, first_fail, indomain_min, complete)
254 minimize objective;
255
256%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
257% Output of the solution
258%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
259% The roster is displayed as numbers - not unfortunately shift type names - with
260% one row for each week.
261% The number of isolated rests and morning after evening violations is also shown.
262
263output [
264 "roster = array2d(1..\(weeks), 1..7, \(roster));\n",
265 "evemorn = \(evemorn);\n",
266 "isolated = \(isolated);\n",
267 "objective = \(objective);\n"
268] ++ [
269 "% Roster: \n",
270 "% Week: M T W T F S S\n"
271] ++ [
272 if j = 1 then "% \(i): " else "" endif ++
273 "\(roster[i,j])" ++
274 if j = 7 then "\n" else " " endif
275| i in 1..weeks, j in 1..7
276];
277