Conference Scheduler

In [1,2] a Python-based conference scheduler is presented. The problem is as follows:

• There are events (i.e. talks) denoted by \(i\) and slots denoted by \(j\)
• Some restrictions include:
• Do not schedule talks by the same speaker at the same slot
• Assign events to slots such that one of the following objectives is optimized:
• Minimize total room overflow (that is: demand exceeds capacity)
• Minimize maximum room overflow
• Minimize changes from previous schedule

In [2] the model is stated as follows:

\[\bbox[lightcyan,10px,border:3px solid darkblue]{ \begin{align} \min\>&\sum_{i,j} (d_i-c_j) x_{i,j}&&\text{Sum of room overflow}\\           &\sum_j x_{i,j} =1\>\forall i \\           &\sum_i x_{i,j} \le 1\>\forall j \\           &x_{i,j} = 0\> \forall i,j \in C_S && \text{Unavailability} \\           &x_{i,j} + x_{i’,j’} \le 1\> \forall i,j,i’,j’ \in C_E &&\text{Not at same day}\\           &x_{i,j} \in \{0,1\} \end{align}}\]

You can choose any single one from the objectives:

\[\begin{align} 1.&\sum_{i,j} (d_i-c_j) x_{i,j}&&\text{Sum of room overflow}\\ 2.&\max_{i,j} (d_i-c_j) x_{i,j}&&\text{Max of room overflow}\\ 3.&\sum_{i,j} \left[(1-x^0_{i,j})x_{i,j}+x^0_{i,j}(1-x_{i,j})\right]&&\text{Difference from a previous solution $x^0$} \end{align}\]

The model can be solved with a MIP solver (via the PULP Python package) or using a simulated annealing code.

This is a nice, clean model. Of course there are always things I probably would do differently, largely based on taste.

1. When I did something like this I used a variable \(x_{e,r,t}\) with \(r,t\) indicating the room and the time period. In this package \(j\) captures both \((r,t)\). As the package supports events and slots of different length (e.g. 30, 60, 90 minutes) that makes sense.
2. Objective 1 seems to prefer assignments with \(d_i \ll c_j\). This can be fixed by using: \(\sum_{i,j} \max(d_i-c_j,0) x_{i,j}\). Of course we can do even better by also penalizing assignments of small events to big rooms, as shown in the rightmost picture:
   
   
3. It is not always easy to choose between the sum vs the max (objectives 1 and 2). Actually often a combination works very well.
4. Similar for the last objective. In general I combine this with the other objectives, so that we can deviate from an existing schedule if it pays off for another objective.
5. Instead of fixing variables \(x\) to zero if assignments are forbidden (and leave it to the presolver to get rid of these variables) I like to not even generate these variables. I guess I am old-fashioned.
6. I probably would make the model very elastic: make sure we can always produce a feasible schedule (at the cost of renting very expensive “emergency” rooms). This way we can at least see a solution instead of just a message “infeasible”.
7. The input data in the tutorial seems to repeat much data. E.g. the room capacity is entered for each time slot. It is usually a good idea to “normalize” data: enter the “elementary” data only once.
8. I often prefer to present results in spreadsheet tables, in hopefully a meaningful layout. That seems to work better as a communication tool than a text file:
    

OK, enough of the nitpicking.  In any case, interesting stuff.

References

1. A Python tool to assist the task of scheduling a conference, https://github.com/PyconUK/ConferenceScheduler
2. Documentation, http://conference-scheduler.readthedocs.io/en/latest/index.html