This is the twenty sixth 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 discuss the case of coefficients for cost function. Let’s begin.

What is important?

We already know how to maximize students’ happiness. We are able to consider preferences points, we can remove gaps between classes, we know how to increase the number of days off. However, we need to answer the question: what is important?

It looks pretty easy. For every class we increase our cost function by the amount of points which particular student assigned to the class. For every day off or removed gap between continuous classes we increase the cost function by the amount of selected coefficient. This means that we have a new problem: what should be the values of the coefficients? This means: what is more important — day off or removed gap? Or maybe a class with highest number of assigned points?

We cannot solve the problem of optimal cost function using the ILP solver because we would need to be able to measure and compare cost functions. Well, did you mean recursion? We need to make arbitrary decisions and choose whether one day off is worth two classes with maximum assigned points or more. Probably the best way to do that is to run solver multiple times using different cost functions and then compare them in other manner.

Actual implementation

I implemented all described cases and compared the actual implementation using different solvers and different data sets. The solvers I used were:

Gurobi 5.6 for Windows
SCIP 3.0.1 x64 for Windows
CPLEX 12.6 x64 for Windows

I used several data sets obtained from real-life situations. These data sets represent preferences created by the computer science students of AGH University of Science and Technology, throughout their registrations for courses in years 2013-2014. There were 10 data sets:

$\begin{gather*} \label{tab:sets} \begin{tabular}{|c|c|c|c|c|c|} \hline Id & Courses & Classes & Pairs of colliding classes & Students & Teams \\ \hline 1 & 8 & 55 & 79 & 103 & 99 \\ \hline 2 & 11 & 60 & 120 & 109 & 76 \\ \hline 3 & 10 & 77 & 122 & 135 & 61 \\ \hline 4 & 6 & 52 & 60 & 105 & 100 \\ \hline 5 & 7 & 56 & 108 & 127 & 62 \\ \hline 6 & 8 & 67 & 193 & 129 & 32 \\ \hline 7 & 6 & 15 & 10 & 179 & 0 \\ \hline 8 & 14 & 56 & 111 & 95 & 17 \\ \hline 9 & 11 & 98 & 350 & 142 & 61 \\ \hline 10 & 9 & 81 & 139 & 112 & 75 \\ \hline \end{tabular} \end{gather*}$

I performed a few types of tests to examine the behaviour of the developed system. Each test was performed on a machine with two virtual cores AMD Opteron Processor 4171 HE, 3.50 GB RAM and running Windows Server 2012 x64.

The most basic cost function included only preferences points. I was able to solve all data sets in less than two minutes. The most difficult cost function included all features (preferences points, teams, days off, continuous classes, most unlucky person) and coefficients were set to prefer days off over the preferences points (one day off was worth about five best classes). I was able to solve all data sets in less than 12 hours with solver’s gap set to $10^{-4}$ . This shows the impact of cost function on the solving time.

Summary

We have seen that the ILP approach is very efficient for solving students placement problem. I was using it for three years at my University and it did well. Even though the ILP does not gives you multiple options at first sight — you can only use “less or equal” constraints, addition, subtraction, and multiplication by constant — we are able to express lots of different problems and build more and more composed building blocks.