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

Hello. Today we are going to handle teams in our cost function. We already implemented teams as constraints, however, this time we are going to express the happiness of creating teams when in fact no teams are required.

Introduction

Sometimes students need to work in teams during the classes. We would like to allow students to express their preferences as to what teams they would like to have — we can ask them to prepare a list of groups they would like to belong to, and then use it to create the schedule in which the students from the same teams are assigned to the same classes.

We need to add constraints which in some way tell the solver that it should try to keep students from the same team together. On the other hand, we cannot add this requirement as a simple constraint, because than we could end up with constraints that cannot be fulfilled (for instance imagine two classes with 7 places and 5 places respectively, and two teams, each consisting of 6 people). Our only way to express something which “we highly would like to occur” and at the same time “we do not require” is to add it to the cost function.

To sum up, we would like to be able to tell the solver that some groups of students should be assigned together, if it is possible. We would also prefer to keep as many students together as possible, when it is not possible to preserve the whole team together, so we prefer when solver assigns together 5 out of 6 students and there is one student assigned to a different class, rather than assigning them as if there was no team, when solver decides that it is not possible to preserve the team.

Implementation

To achieve the described feature, for each class of each course and for each pair of students from the same team we create a boolean variable saying whether these two students are assigned to the same class or not. Next, we simply sum all of these variables and multiply them by some coefficient $\ilpTeamCoefficient$ , whose meaning we will consider shortly. Let us denote the team for course $\ilpCourse{j}$ consisting of $\ilpTeamStudentsCount{i}$ students by $\ilpTeam{i}$ , defined as $\left\{ \ilpCourse{j}, \left\{ \ilpStudent{1}, \ilpStudent{2}, \ldots, \ilpStudent{\ilpTeamStudentsCount{i}}\right\}\right\}$ (the course and the set of students belonging to the team). Let us also define the function $\ilpTeamsCourse{i}$ indicating the course, for which the team $\ilpTeam{i}$ is created. We define the following variables:

$\begin{gather*} \displaystyle\mathop{\forall}_{ \substack{ t = 1, \ldots, \ilpTeamsCount \\ j = 1, \ldots, \ilpTeamStudentsCount{t} \\ k = 1, \ldots, \ilpTeamStudentsCount{t} \\ j \ne k}} \displaystyle\mathop{\forall}_{ \substack{ l = 1, \ldots, \ilpCourseClassesCount{\ilpTeamsCourse{t}}}} \ilpTeamVariable{j}{k}{\ilpTeamsCourse{t}}{l} = \ilpStudentVariable{j}{\ilpTeamsCourse{t}}{l} \wedge \ilpStudentVariable{k}{\ilpTeamsCourse{t}}{l} \end{gather*}$

Every such variable is equal to one only when both of the students are assigned to the same class. We can now add these variables to the cost function with the following formula:

$\begin{gather*} \ilpCost = \sum_{ \substack{ t = 1, \ldots, \ilpTeamsCount \\ j = 1, \ldots, \ilpTeamStudentsCount{t} \\ k = 1, \ldots, \ilpTeamStudentsCount{t} \\ j \ne k \\ l = 1, \ldots, \ilpCourseClassesCount{\ilpTeamsCourse{t}}}} \ilpTeamVariable{j}{k}{\ilpTeamsCourse{t}}{l} \cdot \ilpTeamCoefficient \end{gather*}$

We now consider the meaning of $\ilpTeamCoefficient$ . We cannot simply add the described variables to the cost function, because their total value is relatively small. Thus, we need to multiply them by some constant value, which we will call the “team coefficient”. The value of $\ilpTeamCoefficient$ can be chosen arbitrarily, the greater it is, the more valuable the teams are, so we can control the solver decisions (whether to preserve the teams or not) by changing the value of the coefficient. Of course, we need to decide whether we prefer to have the most suitable placement of students (according to their wishes) or to keep as many teams as possible, probably with lower total happiness, as defined in the previous section.

Summary

Our cost function handles most of the simple happiness factors: assigning students to preferred classes, removing gaps, maximizing days off, handling teams. In the next part we are going to consider last thing: maximize the happiness of most unlucky person.