This project concerns assigning students to groups given various constraints and preferences. It has been directly inspired by the system working at the AGH University (Faculty of Computer Science, Electronics and Telecommunications).
Check out the 🥊 the competition scoreboard on wiki. 🥊
- Fork this project into a private group:
- Add @bobot-is-a-bot as the new project's member (role:
maintainer) - Read this Readme till the end for the instructions.
- Solve the problem!
- Automated tests will be run periodically to check quality of your model. The results will be available in the
GRADE.md - If done before the deadline, contact teacher via Teams, so he can check it earlier.
- To take part in the competition create file
competition.solcontaining solution for thecompetition.dzninstance.
Imagine working in the faculty administration at the AGH UST in Krakow. Every year the same story: first you have to prepare the schedule for the whole year, later you have to assign students to the available groups. Recently your faculty started to notice the obnoxious difficulty of those tasks and tried to introduce some automation. Unfortunately it doesn't work as well as you hoped. Therefore you are going to the matter into your own hands. To be realistic, you will focus on the group assignment as it's less disruptive than the whole schedule. After spending some time under the shower and having several eureka moments, you came with the following definition of the problem.
So, first, the input has to contain the current schedule of all the involved groups1 over the set of days2. Only then we will focus on the students3 and their preferences. Finally we will combine them to obtain an objective function and print the output.
Each group belongs to a class45 (e.g. Constraint Programming: Lab) with a specified duration6 in a well defined time unit7. We also have to know which day8 and at what hour9 the groups start their activities. This way we can guarantee that student doesn't attend two different groups at the same time. We shouldn't forget about the space restrictions, each class has an upper limit for the number of students in the single group10.
Other important factor is that we have to know in what building1112 the group occupies the classroom, so later we can calculate the time required to move between the groups13. We have to guarantee that student is able to transport between the buildings. There is defined hard limit for being late14 and it should never be breached.
Finally the schedule can change during the semester, there can be alternative weeks, some courses may to end in the middle of the semester; it's almost impossible to handle all the irregularities. Therefore we will also define what groups do not conflict each other even if they are happening at the same time according to our simplified schedule15.
Given the schedule, we can focus on the students3 and their preferences. Each student should belong to exactly one group1 per class4, but there are exceptions — more about them later...
First, we have to acknowledge an amazing fact that some students can ignore physical limits and magically teleport between locations16. They do not care whether they have to run from one end of campus to another. Other, mundane studentshave to walk and therefore can be late to the classes.
Being late is not ok 👎.
Secondly, some students live at the campus and they do not care, whether they have breaks between the classes17. On the other hand, other would prefer to not sit at the university without any purpose.
Wasting time on long boring breaks is not ok 👎.
Finally, students assign preferences1819 to the available groups; higher the preference is, more they would like to attend the group. The preference = -1 means that this group is excluded for the given student. If all the groups of a given class are excluded for the student, it means that they do not attend this class — the exception foretold in the first paragraph of this section.
Being assigned to groups one does prefer is not ok 👎.
Given the schedule and student preferences we have to define what assignments are better than others. Obviously, every student (with already mentioned exceptions) has to be assigned to a single group of each class. Also the assignment has to be feasible (no bilocation allowed), but what makes the assignment better than others?
- Students should not be late to their classes — they shouldn't have to run! So we have to count all the time each student is forced to be late/run and we call this total a late disappointment. Obviously, teleporting students16 don't care.
- Students should not waste their time on long boring breaks. For each student and each day we calculate the time they have to spend at the university ("end of the last group" - "start of the of the first group") and how much they spend on learning (sum all the classes' durations this day). Difference between those number is the time they have wasted. The wasted time is summed for each student and we will call this value break disappointment.
- Students should not attend groups they hate. For each student and each class we calculate difference between their favorite group and the one they have been assigned. We sum those values for each student and will call this value preference disappointment.
Next for each student we calculate the following total disappointment:
total disappointment[student] = late disappointment[student] × late_to_disappointment_multiplier20
+ break disappointment[student] × break_to_disappointment_multiplier21
+ preference disappointment[student]
Finally, our objective is to ❗minimize sum o squared total disappointments❗
An example output is presented below:
assignment = [{3, 4},{1, 6},{3, 5},{2, 4},{1}];
total_late_disappointment = 3;
total_break_disappointment = 0;
total_preference_disappointment = 2;
objective = 18;
where:
assignment =array of sets containing groups assigned to the students, e.g.assignment[0] = {3,4}means that the student with index0has been assigned to groups3and4— notice that the last student in the example attends only a single class.total_late_disappointment =sum of late disappointment[student] (before multiplying by the corresponding weight);total_break_disappointment =sum of break disappointment[student] (before multiplying by the corresponding weight);total_preference disappointment =sum of preference disappointment[student];objective =objective value.
The last four lines (objective components) will be useful for the grader script to check if your model calculates them correctly.
Our solution to group-enroll problem is mainly based on MiniZinc models. You can get more info about MiniZinc language here. MiniZinc solver chosen by us to solve the problem is Gurobi. We also use python minizinc library for starting and reruning models to get better solution. You can get some more info abut it here.
To install python minizinc library just enter pip install minizinc[dzn] in the console
Problem is solved in two steps. First much faster one is looking for any solution fullfiling constraints stated by the problem. For it to be done we made enroll_satisfy model. Getting competition.dzn or any other dzn file with appropriate data it returns first solution meeting constraints. Second more time consuming step is improving the solution using Large Neighborhood Search. It is done in python relaxModel. What it does is basicly chose certain days, students and classes which are given to model as variables. Those days, students and classes which haven't been chosen are given to model as constants. This way you can decide when to stop calculating and be sure that you have a solution.
Footnotes
-
Groupis a set containing unique identifiers of groups. ↩ ↩2 ↩3 ↩4 -
Studentis a set containing unique identifiers of students. ↩ ↩2 ↩3 -
Classis a set containing unique identifiers of classes. ↩ ↩2 ↩3 -
group_classarray maps groups to the corresponding classes4. ↩ -
class_durationarray contains classes' durations in the instance specific time unit7. ↩ -
Timeset contains available time indexes, e.g.0is the beginning of the day and the biggest value is the end of the day. ↩ ↩2 ↩3 ↩4 -
group_startarray defines at what hour (in the instance specific time unit7) the groups start. ↩ -
class_sizearray contains how many students can attend a single group of this class. ↩ -
Locationis a set containing unique identifiers of locations. ↩ ↩2 -
travel_durationmatrix contains info, how long (in the instance specific time unit7) it takes to move between locations (indices of thelocation_name[^location_name]). ↩ -
being_late_tresholddefines what is the university policy on being late. Student has to appear at the class without exceeding this time. ↩ -
group_cohabitatsarray contains sets of groups1 can coexist at the same time. ↩ -
student_can_teleportarray tells whether student cares about the distance between the building at the university. ↩ ↩2 -
student_loves_breaksarray tells whether student accepts long break between the groups. ↩ -
Preferenceis a set of possible preferences over the groups, the-1means that the student is not allowed to be assigned to the given group. ↩ ↩2 -
student_prefersmatrix contains prefences18 student3 assigns to various groups1. If all the groups of the given class have assigned the lowest preference it means that student doesn't attend this class. ↩ -
late_to_disappointment_multiplieris a weight associated with the "being late" objective component. ↩ -
break_to_disappointment_multiplieris a weight associated with the "long breaks" objective component. ↩