Obligatory Assignment 2

• Deadline: Wednesday, June 28, 2024, at noon

• The case proposed is examination timetabling. The case is left quite open for different approaches. It is also possible to work on a case of own choice but this has to be agreed with the teacher in due time.

• Changes made to this document after May 31 will be shown in a different color.

Exam Timetabling

You have to use Mathematical Programming to schedule the exams at the Faculty of Science at SDU.

A starting package for the implementation is available in the course git repository [GIT]. The description of the instances is available there in the README.md file of the data/ directory.

Let $E$ be the set of course exams that need to be scheduled, that is, have a date and room assigned. Let $D$ be the set of days and $R$ the set of rooms that are available for scheduling exams. Each exam $i$ from $E$ has a set of enrolled students $S_i$ and requires a number of days depending on whether the exam is written or oral.

Exams that for some reason cannot have overlapping schedules are called conflicting exams. In particular, exams with the same teacher or censor and exams that belong to the same study program are considered conflicting. For an exam $i$ from $E$ the set of conflicting exams is denoted $C_i$.

Exams may share students. The number of students each pair of courses share is denoted by $s_{ij}$ in $\mathbb{Z}_0^+$ for $i,j$ in $E$.

Further, exams may be $joined$, that is, they need to have the same starting date. For an exam $i$ from $E$, the set of exams that must be “joined” with it is denoted $J_i$.

An exam schedule is an assignment of exams to days and rooms, that is, it is a function $\sigma : E \to 2^{D\times R}$. For example, an exam $i$ scheduled in days $1$ and $2$ in rooms $a$ and $b$, respectively, can be represented by $\sigma: i \mapsto \{(1,a),(2,b)\}$. An exam schedule is feasible if it satisfies the following constraints:

1. Each exam in input is scheduled to start and finish in the days available.

2. Each exam is assigned a number of days equal to the number of required days to carry out the exam.

3. Exams with exam duration more than one day receive consecutive days. No holes due to weekend or holidays are allowed within an exam schedule.

4. Exams with preassigned dates and rooms must respect those preassignments and need not necessarily to satisfy the previous three constraints. If present, preassignments are specified in the field `schedule` of each exam.

5. Exams that are joined must have schedules starting on the same day. (The duration for both should be the sum of the duration of the two exams but you can ignore this).

6. Exams that are conflicting must be scheduled in sets of days with empty intersection.

7. Written exams (type=='s') must be scheduled in rooms with enough capacity (seats) to accommodate all the students registered to the exams (ideally, there should be a capacity reduction factor to ensure enough distance between students but we will ignore this here, or assume the reduction has already been done).

8. Oral exams (type=='m') must be scheduled in rooms with capacity less than 10.

9. Optional: Room stability. Exams with duration longer than one day, e.g. oral exams, are scheduled all days in the same room.

If a schedule that satisfies all the above constraints is found, then one must maximize the distance between the starting times of exams that share students ($s_{ij}>0$) (weekends should be counted in the distance as working days). This optimization task can be achieved in different ways and it is up to you modeling this aspect. It is also desirable finding solutions that address some definition of fairness.

Your Task (Deterministic Case)

Formulate the problem in MILP terms, implement the model and solve the instances of the problems made available for E23.

Stochastic elements

During the scheduling process rooms can change their status, from available to unavailable. Hence, the availability of a room is a stochastic variable. If an exam is scheduled in a room that becomes unavailable one of two repair actions must be undertaken: i) moving the exam to another room with enough capacity without changing the days; ii) rescheduling the exam to different day(s) and room(s). We can assume that action i) has no cost. Action ii) has instead a cost and we would like to minimize it. The presence of the optional constraint about room stability may increase the need for actions ii). It is up to you whether to include or not this optional but realistic constraint.

Rather than through a theoretical expression, we approximate the description of the random variables for the room availability through a finite number of future scenarios of room availability, each scenario occurring with equal probability.

Your Task (Stochastic Case)

Formulate the problem as a stochastic programming problem using one of the techniques seen in class, implement the model and solve the instances of the problems made available for E23.

Remarks

• There is no predefined time limit for your experiments. You can choose to run your experiments with the time limit that best fits with your computational resources (eg, time left from deadline, number of cores and machines, etc). Performance can be assessed in several ways (max size of the instances solved, computation time, solution quality, etc.) It is up to you to identify meaningful measures and comment on the performance.

Input Data

In your git repository you will find input instances for E23. You should start experimenting with the smallest instances and grow to the largest.

In the following table for each instance it is given in the order: the number of exams, the number of exam days to allocatex and the number of students.

|         | exams | exam days | students |
|---------+-------+-----------+----------|
| sund    |     9 |        17 |      285 |
| biologi |    14 |        17 |      210 |
| bmb     |    21 |        22 |      592 |
| samf    |    24 |        33 |      581 |
| fkf     |    51 |        59 |      692 |
| imada   |    60 |       101 |      861 |
| all     |   179 |       249 |     2428 |

The starting package implements the reading of the instances and generation of scenarios for the stochastic case. Some preprocessing occurs during reading. For example, in the data files there are also exams without students or with types “o” or “u”. These exams are removed while reading the instances, hence you do not have to worry about them.

To execute the starting package run:

python3 src/main.py data/E23/biologi.json -o output_dir

In the package there is also a verifier for the constraints of the problem.

python ../src/verifier.py -a F23/solution.json F23/all.json -o .

At the time of writing the verifier must be updated to handle also rooms.

Important: there might come updates to the files of the starting package, hence you should not modify them. Importing them in your code should be safe.

Output Format

The output file contains a solution in json format as shown below:

{
    "N100008102": [
        (170,"room.U25A")
    ],
    "N100037102": [
        (160, "room.U148") 
    ],
    "N100038102": [
        (163,"room.U141"),
        (164,"room.U141"),
        (165,"room.U141"),
        (166,"room.U141")
    ],
    "N100040102": [
        (173, "room.U148") 
    ],
    "N100042102": [
        (170, "room.U148") 
    ],
    "N110028102": [
        (163, "room.U148"), 
        (164, "room.U25A") 
    ],
...
}

The json object is a dictionary with keys the STADS code of the exam and value an array with the days and rooms in which the exam has been scheduled. Days are indicated by number corresponding to the day number from the start of the year. For example day 01/01/2022 is day 1. This is consistent with the imported instance.

In Python the json file can be easily obtained with the following lines of code:

json.dump(dates, fp=filehandle, sort_keys=False, ignore_nan=True,
                  indent=4, separators=(',', ': '),  ensure_ascii=False)

where dates is a dictionary with exam STADS code as key and the list of days as values.

Questions & Answers

• Should the “forbidden” and “available” information that is given at some of the exams be used when scheduling them?

  That would be nice, yes. They give days where the exam cannot be planned or the only days where it can be planned.