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