This is the twenty third part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi all! Last time we saw how to handle continuous classes for students. Today we are going to consider students who prefer to have as many days off as possible. They prefer to have classes from morning to evening on one day of a week, provided that on all the other days of the week they will not need to attend the university.

Formulas

We can express the idea of days off using the same reasoning as in the previous post — we create variables indicating whether each student is assigned to classes occurring on the particular day, and then we add these variables to the cost function. We also need to multiply the result by some factor in order to make it significant. Since we have only five days in a week, increasing the cost function by five would not make big difference for the solver and it would simply ignore this input. We need to make sure that one day off is worth a bit more than other things (like classes with 10 points). What does “a bit more” exactly mean we will see in one of the next posts.

We define the following variables:

$\begin{gather*} \displaystyle\mathop{\forall}_{ \substack{ d = \{ \text{monday}, \text{tuesday}, \text{wednesday}, \text{thursday}, \text{friday} \} } } \displaystyle\mathop{\forall}_{i = 1, \ldots, \ilpStudentsCount} \ilpFreeDayVariable{i}{d} = \displaystyle\mathop{\vee}_{\substack{j = 1, \ldots, \ilpCourseCount \\ k = 1, \ldots, \ilpCourseClassesCount{j} \\ \ilpClass{j}{k} \text{ happens on day }d}} \ilpStudentVariable{i}{j}{k} \end{gather*}$

When variable $\ilpFreeDayVariable{i}{d}$ is equal to $1$ , student $\ilpStudent{i}$ is assigned to some classes on day $d$ . To tell the solver that we want to have as many days off as possible, we need to negate this variable and add it to the cost function:

$\begin{gather*} \ilpCost = \displaystyle\mathop{\forall}_{ \substack{ d = \{ \text{monday}, \text{tuesday}, \text{wednesday}, \text{thursday}, \text{friday} \} } } \displaystyle\mathop{\sum}_{i = 1, \ldots, \ilpStudentsCount} \ilpFreeDayVariable{i}{d} \cdot \ilpFreeDayCoefficient \end{gather*}$

$\ilpFreeDayCoefficient$ is the coefficient indicating how much we prefer to end up with a schedule with many days off, or with the schedule with classes assigned as much according to the students’ other preferences as possible.

Impact on solving time

Let us stop for a moment and see what we did exactly. These formulas might look easy to fulfill but in fact they are very heavy for a solver. In order to give particular student a day off we need to assign him or her for classes on other days. The more classes we have on a particular day the more work work we need to do in order to fulfill all the other constraints. In fact, finding days off is the most demanding part of the cost function and it is able to bump up the solving time up to hours (from seconds) so be careful with that.

Summary

As for now we focused only on improvements for one student at a time. In the next part we are going to handle teams in cost function. See you soon.