Assignment to groups and scheduling: how to improve constraints?

[Didier Lesesvre]

Hi everyone,

I got into MiniZinc some weeks ago and am super fond of it. My main purpose was to solve a pretty annoying scheduling problem my department faces each year, spending weeks to solve it (partially). I tride to solve this in MiniZinc, but run into some complexity (?) issues.

Here is the main setting:

- I have a certain number of students

- They rank 7 topics in order of preference

- They will be assigned 4 of such topics

- The groups have a minimal/maximal size (but there may be various groups on the same topic)

- There is 4 time slots available in the timetable for all of these

I need to... get something workable out of it. The most obvious constraints are:

- students cannot attend two topics at the same time

- various topics groups cannot be at the same time (only one teacher)

- we would like to maximize the satisfaction of the problem (but in fact, it would be already pretty good to have just a possible situation)

After many trials and errors, and some insights from colleagues of the Coursera course on MiniZinc, I ended up having a (barely working) model to assign each student to a topic, but of course this neglects the true scheduling problem (compatibility for both students and teachers, even though it would work with enough teachers).

I would like to know if I am missing obivous extra structures or constraints I may add to speed it up enough to get an answer.

Here is the current model:

==============

% PARAMETERS

int: n; % number of students

set of int: STUDENTS=1..n;

int: m; % number of topics

int: g=5; % number of instances of each course

set of int: PREFERENCE=1..m;

set of int: TOPICS=1..g*m; % different topics (with instances)

int: c; % number of courses each student will take

int: maxseats; % number of seats available per course max

int: minseats; % number of seats minimum per course

int: timeslots; % possible time slots for the courses 

set of int: TIMESLOTS=0..timeslots; 

array[STUDENTS,1..m] of PREFERENCE: preference; % ranking of topics by each student

array[STUDENTS, PREFERENCE] of TOPICS: prefRank = array2d(STUDENTS, PREFERENCE, [rank | student in STUDENTS, p in 1..m, rank in 1..m where preference[student, rank] == p]);

array[STUDENTS,1..c] of var PREFERENCE: courseRank;
constraint % channeling constraint to obtain topic ranking

forall(student in STUDENTS, i in 1..c)(courseRank[student, i] = prefRank[student, topicToTopic(course[student, i])]);

% VARIABLES

array[STUDENTS,1..c] of var TOPICS: course; % topics assigned to each student

array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to topics 

array[TOPICS] of var 0..maxseats: number; % number of people taking each course

constraint forall (topic in TOPICS)(number[topic] = sum(student in STUDENTS, i in 1..c)(course[student,i] == topic));

% FUNCTIONS (to navigate between istances and topics)

function int: topicToGroupFix(var int: t) = fix(((t-1) mod g) + 1);

function var int: topicToTopic(var int: t) = ((t-1) div g) + 1;

function int: topicToTopicFix(var int: t) = fix(((t-1) div g) + 1); 

function int: topicGroupToTopic(int: t, int: gg) = ((t-1) * g) + gg;

% CONSTRAINTS

include "globals.mzn"; 

constraint % before using another topic group make sure the previous one has students in it

forall(t in 1..m, gg in 1..g-1)( number[topicGroupToTopic(t,gg+1)] > 0 -> number[topicGroupToTopic(t,gg)] >= minseats); 

constraint % if students are assigned to a topic group it must have enough

forall(t in TOPICS)( number[t] > 0 -> number[t] >= minseats ); 

constraint % make sure topics are slotted at different times

forall(t in 1..m)( alldifferent_except_0([schedule[x] | x in topicGroupToTopic(t,1)..topicGroupToTopic(t,g)])); 

constraint % no student has two topics at the same time

forall(student in STUDENTS)(alldifferent([schedule[course[student,i]] | i in 1..c])); 

constraint % students have different topics (and break symmetries)

forall(student in STUDENTS)(strictly_increasing([courseRank[student, i] | i in 1..c]));

constraint % students have different topics

forall(student in STUDENTS)

(alldifferent([topicToTopic(course[student, i]) | i in 1..c])); 

constraint % fairness - don't want any one student to get a bad schedule relative to others

forall(student in STUDENTS)(sum([courseRank[student,i] | i in 1..c]) <= min([sum([courseRank[s,i] | i in 1..c]) | s in STUDENTS where s != student])+1);

constraint % fairness - don't a student get a much worse choice than others

forall(student in STUDENTS)(courseRank[student,c] <= min([courseRank[s,c] | s in STUDENTS where s != student])+1);

% break symmetries on the schedule

constraint

forall(t in TOPICS)(if number[t] == 0 then schedule[t] == 0 else schedule[t] >= 1 /\ schedule[t] <= t endif);

constraint

forall(t in 1..m*g-1)(schedule[t+1] <= (max(x in TOPICS)(schedule[x])+1))

solve satisfy; (or maximize a certain satisfaction)

==============

The datafile is attached, it is far too slow (even hours aren't enough) even for c=2 (i.e. assigning two topics per student), so c=4 will be a nightmare.

I am modelling the different instances of the same topic as different topics essentially (with an extra alldifferent constraint, since there is only one teacher per topic). I am not fond of this solution and maybe there is a more clever way to handle it.

I also tried with some boolean variables instead, and mainly the solvers gecode, chuffed and coin-bc. I wonder if there is a more elegant way of defining these variables (declaring them as equivalent/inverse to some others, even if it is only an injective map).

Do you have a more clever approach to it? Any help would be very welcome!

Best wishes,
Didier