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

Hello! This time we implement another part of our cost function, the happiness of most unlucky person. Let’s go.

Table of Contents

Happiness of collective

Throughout previous parts we added multiple parts of cost function in order to maximize happiness of students. However, all these formulas were working for a single student at a time (except for teams) and did not consider the students as a whole. This might end up with a situation where there are students with maximum possible happiness (e.g., which are assigned exactly to the classes they wanted) and, at the same time, very unhappy students. The solver is not able to solve this situation because it is not aware of it — the math is very cruel and one completely happy student plus one completely unhappy student situation is equal to situation with two students moderately happy. Today we will try to distinguish these two situations and make sure that everyone gets something.

Happiness of most unlucky student

We are going to maximize the happiness of most unlucky student. We are already able to calculate happiness of every student (by considering their preferences points, teams, days off, and continuous classes). Let’s assume that our cost function consists of $n$ variables $l_i_$ representing the part for $i$ -th person. We could try to find minimum within these values and try to maximize it, however, it would be very inefficient.

In order to maximize the happiness of most unlucky student, we are going to maximize the lower bound of persons’ happiness. We introduce the $L$ variable and add the following constraint

$\begin{gather*} L \le l_i \end{gather*}$

for every student. This basically means, that $L$ is not greater than any of the variables representing the happiness of any person. We now modify our cost function to maximize only this one variable. So our cost function is: $c = L$ .

Can you see how it works? If not, then continue reading.

Why does it work?

We try to maximize cost function with only one variable $L$ . We know that $L$ is not greater than any of the persons’ variables so in order to maximize $L$ we need to maximize all $l_i$ variables. This means that we cannot leave someone unassigned to wanted classes because then we wouldn’t be able to increase the $L$ variable. What’s more, this is very fast: we are not trying to find the minimum of the happiness variables which would be much slower (even few hundred times slower).

Summary

In the next part we are going to discuss some final thoughts regarding the coefficients and analyze real implementation of the students placement problem.