This is the thirty first 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 once again take a look at Students Placement Problem. We already know how to define it, add constraints, maximize students happiness, and what we can do with coefficients. However, this time we will try to fix the plan by hand.

Table of Contents

Introduction

Let’s assume that we solved the problem and came up with any solution fulfilling all requirements. We know give the solution to students and they begin to complain. Since we were unable to make everyone totally happy, there will be someone not so satisfied with our solution. All these sad people have two options: accept the destiny (and blame us) or try to fix the plan by exchanging their assignments on the free market. And this is the part we will try to solve today: make exchanges automatically.

Problem definition

Imagine that we have description of all exchanges students want to perform. Every exchange specifies originating class (e.g., Calculus on Tuesday at 12:50-14:20) and a list of acceptable destinations (e.g., Calculus on Thursday at 15:00). We assume that before any exchange takes place students are assigned properly (they have no collisions, they are assigned to all types of classes they should be etc.). All we want to do is to take described exchanges and try to accept as many of them as it is possible. However, we need to remember about the following constraints:

We cannot make any collision – student should not be assigned to colliding terms
We cannot change number of students assigned to class — if there were ten people assigned to Calculus on Thursday at 9:30, after all exchanges are done there should be exactly ten (possibly different) people assigned to that class

Our goal is to maximize number of finished exchanges. We define exchange to be a triplet of (source class, destination class, student).

Variables

For every term we define a variable $t_{i}$ which represents the total number of added or removed student to that term. We will use these variables to make sure that we don’t change number of people assigned to classes.
For every student’s exchange we define a binary variable $e_{s, d, p}$ representing the decision — whether student $p$ is transferred from class $s$ to class $d$ . Using these variables we will make sure that we make no collisions.

Constraints

Let’s now add constraints to the model.

Exactly one change for single source

We start with constraint that for a particular exchange option only one destination is selected. This means that from every acceptable destination we pick only one:

$\begin{gather*} \displaystyle\mathop{\forall}_{ p, s } \displaystyle\mathop{\sum}_{d} e_{s, d, p} \le 1 \end{gather*}$

We simply sum all variables for a particular person and for a particular source, and we specify that this sum should not exceed one — we either move person somewhere else or don’t touch it.

Do not modify number of assigned students

Next, we need to make sure that we don’t modify number of assigned people. For every exchange we need to add person to destination class and remove it from source:

$\begin{gather*} \displaystyle\mathop{\forall}_{ i } t_{i} = \displaystyle\mathop{\sum}_{s, p} e_{s, i, p} - \displaystyle\mathop{\sum}_{d, p} e_{i, d, p} = 0 \end{gather*}$

For every term we first add all “incoming” variables for and next subtract all “outgoing” variables. Finally, we make sure that this value is equal to zero so the total number of assigned people is not changed.

Do not make collisions

Now, we need to make sure, that we do not make collisions. We simply get variables for all terms and make sure that for a single term at most one variable is non-zero:

$\begin{gather*} \displaystyle\mathop{\forall}_{ i, p } \displaystyle\mathop{\sum}_{d} e_{i, d, p} \le 1 \end{gather*}$

Move person to other term only when the person is not there yet

Finally, we need to make sure that we do not move person to some class if the person has already other class at the same time:

$\begin{gather*} \displaystyle\mathop{\forall}_{ p } \displaystyle\mathop{\forall}_{ i \text{ person } p \text{ is assigned to} } \displaystyle\mathop{\sum}_{s} e_{s, i, p} \le \displaystyle\mathop{\sum}_{d} e_{i, d, p} \end{gather*}$

Cost function

As a cost function we simply sum all variables:

$\begin{gather*} c= \displaystyle\mathop{\sum}_{s, d, p} e_{s, d, p} \end{gather*}$

Summary

We are now able to exchange students automatically so they do not need to fish for acceptable solutions. Of course, our current approach is as simple as possible, we neither bother to maximize average happiness nor try to make one exchange more valuable than another. But this is probably not needed at this time. Of course, this approach has one important drawback: students are not able to offer payment for their proposals.