this repo has no description
dekker.one
1%------------------------------------------------------------------------------%
2%% Generalised Balanced Academic Curriculum problem
3%%
4%% Problem 64 in CSPlib:
5%% http://www.csplib.org/Problems/prob064/
6%%
7%% See http://satt.diegm.uniud.it/projects/gbac/
8%% for a detailed explanation of the problem.
9%% Note that the distance from the ideal load,
10%% which is a part of the objective, is computed
11%% using the squared error. This is following
12%% http://dx.doi.org/10.1007/978-3-540-88439-2_11
13%% and allows the found objective value to be
14%% compared with found objectives reported on
15%% http://satt.diegm.uniud.it/projects/gbac/
16%%
17%
18%------------------------------------------------------------------------------%
19% Model by Jean-Noel Monette
20% Modified by Gustav Bjordal
21% with help by Fatima Zohra Lebbah, Justin Pearson, and Pierre Flener
22%
23%------------------------------------------------------------------------------%
24% Includes
25include "global_cardinality_low_up_closed.mzn";
26include "bin_packing_load.mzn";
27
28%------------------------------------------------------------------------------%
29% Parameters
30
31int: n_courses;
32set of int: courses = 1..n_courses;
33int: n_periods;
34set of int: periods = 1..n_periods;
35int: n_curricula;
36set of int: curricula = 1..n_curricula;
37array[curricula] of set of courses: courses_of;
38int: n_precedences;
39set of int: precedences = 1..n_precedences;
40array[precedences,1..2] of int: precedes;
41
42int: min_courses;
43int: max_courses;
44
45array[courses] of int: course_load;
46int: max_load = sum(c in courses)(course_load[c]);
47
48array [curricula] of int: total_load = [sum(i in courses_of[c])(course_load[i]) | c in curricula];
49array [curricula] of int: ideal_load_floor = [total_load[c] div n_periods | c in curricula];
50array [curricula] of int: ideal_load_ceil = [total_load[c] div n_periods + (if total_load[c] mod n_periods ==0 then 0 else 1 endif) | c in curricula];
51
52int: n_undesirables;
53set of int: undesirables = 1..n_undesirables;
54array [undesirables,1..2] of int: undesirable;
55
56%weight of the load balancing
57int: w1;
58%weight of the undesirable assignment violations
59int: w2;
60
61
62%------------------------------------------------------------------------------%
63% Variables
64
65%decision variable
66array [courses] of var periods: period_of;
67
68
69%------------------------------------------------------------------------------%
70% Constraints
71
72%course load of all periods for each curriculum
73constraint forall(c in curricula)(
74 global_cardinality_low_up_closed(
75 [period_of[i]|i in courses_of[c]],
76 [i|i in periods],
77 [min_courses |i in periods],
78 [max_courses |i in periods])
79);
80
81%prerequisites
82constraint forall(i in precedences)(
83 period_of[precedes[i,1]] < period_of[precedes[i,2]]
84);
85
86
87%period load
88constraint forall(c in curricula)(
89 bin_packing_load(
90 [load_of[c,p] |p in periods],
91 [period_of[i] |i in courses_of[c]],
92 [course_load[i] |i in courses_of[c]])
93);
94
95%violation
96var 0..n_undesirables: undesirable_violation = sum(i in undesirables)(
97 bool2int(period_of[undesirable[i,1]]==undesirable[i,2])
98);
99
100%load of periods
101array [curricula,periods] of var 0..max_load: load_of;
102
103%course balance delta
104array [curricula,periods] of var 0..max_load: delta;
105var int: norm = sum([delta[c,p]*delta[c,p]|c in curricula, p in periods]);
106
107%norm
108constraint forall(c in curricula, p in periods)(
109 delta[c,p] = max(load_of[c,p]-ideal_load_ceil[c],
110 ideal_load_floor[c]-load_of[c,p])
111);
112
113%objective
114var int: objective;
115constraint objective = w1 * norm + w2 * undesirable_violation;
116
117%------------------------------------------------------------------------------%
118% Output
119
120constraint trace("% init_area = \(ub(objective));\n", true);
121output
122 ["objective = ", show(objective)] ++[";\n"] ++
123 ["period_of = ", show(period_of)] ++ [";\n"];