I am trying to use MiniZinc to solve a scheduling problem. 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
- There is 4 time slots available in the timetable for all of these
Of course students cannot attend two topics at the same time, and there are also a minimal/maximal size for each topic (but there may be various classes of a same topic, or no class of another topic). This is the most important constraint and we could see that as a satisfiability problem, even though trying to maximize the hapinness of the students is a good bonus.
I tried the following approach, translating all my constraints:
int: n; % number of students
int: m; % number of topics
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: STUDENTS=1..n; % students
set of int: PREFERENCE=1..m; % possible preference rankings
set of int: TOPICS=1..m; % different topics
set of int: TIMESLOTS=1..timeslots;
array[STUDENTS,TOPICS] of PREFERENCE: preference; % ranking of topics by each student
array[STUDENTS,1..c] of var TOPICS: course; % topics assigned to each student
array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to topics
include "alldifferent.mzn";
constraint % students have different topics
forall(student in STUDENTS)(alldifferent([course[student,i] | i in 1..c]));
constraint % no student has two topics at the same time
forall(student in STUDENTS)(forall(i,j in 1..c where i<j)(schedule[course[student,i]] != schedule[course[student,j]]));
constraint % less students per topic than available seats (NOTE : groups can be duplicated)
forall(topic in TOPICS)(sum(student in STUDENTS where exists(i in 1..c)(course[student,i] = topic))(1) <= maxseats);
constraint % more students per topic than the minimum
forall(topic in TOPICS)(sum(student in STUDENTS where exists(i in 1..c)(course[student,i] = topic))(1) >= minseats);
var int: satisfaction = sum(student in STUDENTS)(sum(i in 1..c)(preference[student, course[student,i]]));
solve minimize satisfaction; The problem is that this works for few students, but it is far from working in a reasonable time for my list of students (I have about 100, which I though was not that many, but even 20 does not reach any conclusion in ten minutes).
Here is part of my data file (cutting some students for simlplicity, but it is already too long:
n = 10;
m = 7;
c = 3;
maxseats=18;
minseats=1;
timeslots=4;
preference =[|
1,2,5,3,7,4,6|
6,4,7,5,1,2,3|
1,2,6,4,5,7,3|
5,3,1,2,6,4,7|
5,2,1,6,3,7,4|
7,5,1,6,3,2,4|
1,7,6,4,5,3,2|
1,4,2,6,3,5,7|
4,6,1,5,2,3,7|
1,6,4,3,5,7,2|
|]; Are there any relevant constraints or structure I can add to help the solvers to do the job?
*** Edit. Here is a further attempt. I noticed another problem: basically, groups cannot be too large (less than maxseats), thus there will be various groups of each topic (with same teacher). Hence, not only cannot students have lectures at the same time, but various groups of the same topic also ought to be distinguished, with the constraint of not having lectures at the same time. This looks like a much larger combinatorial problem! Maybe there is a clever way to package it, but for now I essentially chose to duplicate the topics.
This is the model:
int: n; % number of students
int: m; % number of topics
int: c; % number of courses each student will take
int: g=5; % number of instances of each course
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: STUDENTS=1..n; % students
set of int: PREFERENCE=1..m; % possible preference rankings
set of int: TOPICS=1..g*m; % different topics
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 TOPICS: course; % topics assigned to each student
array[TOPICS] of var TIMESLOTS: schedule; % time slot assigned to 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;
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));
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)]));
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])]);
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 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])+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);
%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])+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)(schedule[t] <= t);
constraint forall(t in 1..m*g-1)(schedule[t+1] <= (max(x in TOPICS)(schedule[x])+1));
var int: satisfaction = sum(student in STUDENTS, i in 1..c)(courseRank[student,i]);
solve :: int_search(courseRank, smallest, indomain_min)
minimize satisfaction;
%solve minimize satisfaction;
output(["satisfaction Level: \(satisfaction)\n"]);
output(["student", "\t", "topic", "\t\t", "group", "\t\t", "courseRank", "\n"]);
output([show(student) ++ "\t" ++ show([topicToTopicFix(course[student,i]) | i in 1..c]) ++ "\t" ++
show([topicToGroupFix(course[student,i]) | i in 1..c]) ++ "\t" ++
show([courseRank[student,i] | i in 1..c]) ++ "\n" | student in STUDENTS]);
output(["studentsPerTopic: \(number)\n"]);
output(["schedule: \([schedule[x] | x in TOPICS])\n"]);The same data file can be used, but with 100 students, even c=1 (i.e. only one lecture to assign, which should be essentially trivial!) does not finish in hours and hours...
Is there anything I can do or is the problem really combinatorically too big for MiniZinc?