Obligatory Assignment 2

Deadline: June 20, 2023, at 18:00

The goal of this assignment is to implement a MILP model for the problem of scheduling course classes at the Faculty of Science of SDU. A starting package containing data and code is available from the directory CTT of the repository Material in github.

The goals of the assignment are to:

• model the problem in MILP terms
• implement the model in Python
• experiment with the data made available and determine whether the model is computationally practicable
• repeat the previous steps improving the computational aspects of the model using some of the techniques saw during the course
• describe the models and the implementations in a written report
• report the computational results in the report.

The project has to be carried out individually. The deliverables, to be collected in a tar gzip archive and submitted via ITSLearning, are:

• the report (max 10 pages)
• the source code of the implementation.

You do not need to hand in the input data and you should remove large files generated by your code, eg, .lp files. The source code must be organized as in the CTT repository made available. The report must be placed in a directory called doc inside CTT. Archive and compress everything with tar czvf and submit via ITSLearning. ITSLearning will rename the archive file that you submit with your name.

Problem description

Given:

• A set of hourly timeslots (aka, time periods) $P=\{(h,d,w) \mid h\in \mbox{Hours}, d\in \mbox{Days}, w\in \mbox{Weeks}\}$, that is, 12 slots of one hour per day $\times$ 5 days $\times$ 17 weeks. [File: timeslots.json.] The file also contains a set of forbidden (banned) slots.

• A set of events (aka, classes) $E$. Events are derived from courses, weeks, sessions and sections. Each event has an identifier, a duration $\ell(e)$, $e \in E$, a week where it has to take place and possibly a list of events that must be scheduled at the same time (paired, for courses that are co-taught). [File: events.json.]

• A set of rooms $R$. Each room has a set of timeslots where it is busy (Rooms should also have a capacity that makes them suitable or not for a course. This important detail will be ignored in this assignment.) [File: rooms.json.]

• A precedence digraph $D=(E,A)$ where each arc $uv \in A$ for $u,v \in E$ represents a precedence constraint that $u$ must be scheduled before $v$.[File: events.json, the digraph is given as a list of event identifiers associated to every event, denoting the incoming arcs, that is, the events that must be scheduled before the current one.]

• Two sets of people: a set of students $S$, a set of teachers $T$, together with:

  • a collection of enrollments ${\cal Q}=\{E_s \subset E \mid s \in S\}$ that are events a student has to attend for each week. [File: students.json.]

  • a collection of teaching duties ${\cal D}=\{D_t \subset E \mid t \in T\}$. [File: teachers.json.]

  • teacher unavailabilites ${\cal U}=\{U_t \subset P \mid t \in T\}$. Not available for this assignment.

Task:

A timetable is a schedule of events in timeslots and rooms throughout the semester.

A conflict arises if a resource (room, teacher, student) is used by more than one event at a time.

A timetable is feasible if it satisfies all (hard) constraints given below.

The task of the assignment is to find a timetable that is feasible and good with respect to the desirability criteria given below.

Constraints (hard constraints):

• all events are scheduled
• forbidden slots are not used
• resource room: there are no room conflicts
• resource teacher: there are no teacher conflicts. Note: some event does not have a teacher (they should be attended by instructors which are not included in this assignment).
• resource course:
  • the precendences within the weeks are met
  • paired courses are sychronized
  • there is at most one event per course per day for each student

Desirability criteria (soft constraints):

• resource student: student conflicts are minimized
• resource course: weekly stability is promoted
• resource teacher: the number of events per day per teacher is minimized
• bad slots are avoided in a way proportional to their degree of discomfort (in the figure below, darker shades of green indicate higher undesirability/discomfort).

The formalization of the criteria and the way to handle the multi-criteria aspect is left open.

Output

Use at most twenty minutes of computation time for any of your models.

You should report in the final document the computational results of the models you developed. This includes evidence that the solution is correct, for example by assessing a posteriori that the constraints are satisfied or reporting statistics on the degree of dissatisfaction of those that are not satisfied (for example, the soft constraints).

Report also statistics about the solution process: number of variables and constraints before preprocessing and after preprocessing, whether the final solution was optimal, what was the dual bound given by the linear relaxation and the initial optimality gap, eventually the development of primal and dual bound through the solution process, and the number of nodes in the examined in the branch and bound tree.

Remarks

• To meet the minimum requirements for acceptance your work should at least:

  • set up the model correctly for the most important constraints (the first four)

  • present the model in an understandable and structured way, including introduction of the mathematical symbols, mathematical expressions, and explanation of the expressions.

  • contain an implementation of the model in one of the solvers available and an assessment of the computational results. If the implementation does not work there must be an explanation about where the problem is.

• An excellent performance includes besides the minimum requirements for acceptance also a correct modeling of all constraints and a correct implementation together with an attempt to solve the largest instance by means of some of the advanced methods saw in class. It can still contain issues related to implementation details or small mathematical imperfections.