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.

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 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 representing the decision — whether student is transferred from class to class . 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:

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:

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:

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:

Cost function

As a cost function we simply sum all variables:

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.

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:

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 . 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.

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.

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 variables representing the part for -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 variable and add the following constraint

for every student. This basically means, that 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: .

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 . We know that is not greater than any of the persons’ variables so in order to maximize we need to maximize all variables. This means that we cannot leave someone unassigned to wanted classes because then we wouldn’t be able to increase the 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.

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 , whose meaning we will consider shortly. Let us denote the team for course consisting of students by , defined as (the course and the set of students belonging to the team). Let us also define the function indicating the course, for which the team is created. We define the following variables:

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:

We now consider the meaning of . 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 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.

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:

When variable is equal to , student is assigned to some classes on day . 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:

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.

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

Last time we saw how to include preferences points in the cost function. Today we are going to implement yet another nice feature of our scheduling system — we are going to include continuous classes in the cost function.

Introduction

By including only preferences points we try to maximize the students happiness based on their choices. However, the solver doesn’t consider any other requirements which might be very helpful when a student does not get exactly what he or she wants. For instance, when someone is assigned to two classes with a gap between them, he or she needs to waste some time waiting for the second class. It is very annoying for people who are not able to return home in such a short period of time.

There is also another case for continuous classes. Some students do not care which classes they get and all they would like is to have a continuous schedule, which means that their classes occur one after another. It is so because students are working and they prefer to study in the evenings, or they live far away from the university and they need to travel by bus for a few hours every day. In this case having one class, then one hour break, and another class is inconvenient, because such a student cannot go home and rest or go to work.

Implementation

Let us assume that we have a list of pairs of co-occurring classes. By “co-occurring” we mean situation, when one class starts right after another one ends. For each pair of such classes and for each student we create a boolean variable indicating whether the student is assigned to both of the classes. We define the following variables:

When variable is equal to one, the student is assigned to two classes occurring one after another. We can now sum all these variables, multiply them by coefficient (whose meaning is analogous to the coefficient described in the previous section), and add to the cost function:

By changing the value of , we can change the behaviour of the solver — whether we prefer the more continuous schedules or schedules more going on with students’ preference points.

Summary

It is rather an easy task to include continuous classes in the cost function, however, it is very powerful. Next time we are going to do something similar: we are going to maximize the number of days off for students.

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

So far, we have defined constraints which make our final solution “feasible”. The students will likely not be very happy with their schedules, but they will at least be able to attend all the classes they want to. It is time to find a way to make them happy.

Introduction

There is a question — what does it mean to be “happy”? As we will shortly see, there are at least few ways to calculate the level of happiness and each of them gives different results. It is not easy to compare two solutions because we always need to remember that even an optimal solution does not mean that students are completely happy, because it depends on the method of calculating happiness.

Before we describe the methods of calculating happiness, we need to consider a few details of preference points. Every student can make his decision by distributing preference points for classes in the courses. We assume, that the student cannot have more than preferences points in a single course—which means, that . This also means that most of the students’ wishes will be equal to .

Sum of Preference Points

The simplest method of calculating happiness is by adding all the gained preference points. As we have defined in Section~??, when variable is equal to , we say that student gained points for his wish for class . We define our goal function as a sum of all these points:

By maximizing this function, we increase the total happiness of students, because the solver will try to assign them to classes they want to be assigned to. This is called the “Utilitarian Approach”.

Let us consider advantages and disadvantages of this approach. This formula is easy in implementation and can be calculated very quickly. Perhaps even more importantly, it is rather easy to answer the question how should students distribute their preference points”, because the total value of the cost function is simply the sum of students’ preferences. So when two students decide to give preference points for a particular class, we can suspect that the student who gave more preference points for that class will be assigned to it. This is an advantage and a disadvantage at the same time.

Let us consider two students, who are registered for calculus exercises. Imagine that student A gave 10 points for class C, and student B gave 5 points for that class. In an isolated case, when there is the last place left in class C, the solver should assign student A, because he gave 10 points, so he will increase the cost function by 10, whereas student B would increase it only by 5. Let us assume that student B gave no more than 5 points for any of the classes. In this distribution of points, he is in worse position (from the solver’s point of view), because he cannot increase the cost function by more than 5 points from one class, so in direct confrontation with student A he will always lose. However, placing student B in that class would mean giving him his most wanted class (because it is his highest preference points decision).

Whether this situation is advantageous or disadvantageous cannot be simply answered. It is a matter of choice or particular needs. Let us now consider different methods of calculating happiness, which do not suffer from this confrontation effect.

Sum of Preferences per Student

This method is very similar to the previous one. We once again sum all of the preference points, but before summing them, we divide them by the maximum amount of the preference points which students can gain.

To explain this, let us consider an example. Imagine that calculus course has two classes: class M (which happens on Monday) and class F (which happens on Friday). We have two students: student A gives 5 points for class M and 3 points for class F, student B gives 10 points for class M and 8 points for class F. We need to assign each of them to exactly one class of calculus per week, which means, that every student will be assigned to class M or to class F, and not to both of them. In this case, the total number of points which student A can gain is 5, because he can gain 5 points for class M or 3 points for class F, and he cannot gain more. Student B can gain at most 10 points for his wish for class M.

To calculate the cost function, we sum the students’ gained preference points, but we divide them by the total amount of points they can gain for all their courses. In our example, we divide student A’s points by 5, and student’s B points by 10. Let us denote the total possible amount of points which student can gain as , the general cost function formula is as follows:

With this approach we treat students’ preferences as their relative needs. points no longer means the most wanted class, student can indicate that, for instance, all of the classes are equally desired (by giving the same amount of points to all of them).

We can consider this approach even further, by dividing student’s points by the total possible amount of points which the student can gain in just one course. As with the previous method, this is a matter of particular needs.

Summary

Today we described a very simple method of calculating happiness. In next parts we will consider more requirements which will greatly enhance our cost function.

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

Last time we defined necessary constraints for students placement problem. Today we are going to implement something similar. We will still focus on defining requirements for schedule and ignoring the cost function, however, this time we will implement constraints not required for finding feasible solution yet very useful. Apart from the constraints, which are necessary for finding a schedule allowing the students to complete their studies, we can imagine many constraints, whose goal is to improve the quality of the schedule. Let us begin.

Lower Bound for Assigned People

Just like we added constraint for maximum number of students assigned to a single class, we can do the same for minimum number. This feature is very helpful for lecturers because it allows to create groups with almost the same number of students. In order to achieve this, we can use the following constraint:

Class Sizes Divisible by Team Sizes

From time to time lecturer wants to divide students into teams of equal size, for instance to let them work together on a single project. If we want to add this requirement, we can use the following formula:

for each class where students should create teams ( means the size of a team). is any integer.

Removing classes

So far, we assumed that we use all classes from the schedule provided by the authorities of university. However, we might imagine a different situation — for instance we might want to remove some classes. Let us say that we have 60 places for one course but only 30 registered people. We might want to remove some classes in order to have bigger groups and utilize lecturer’s time better. Of course we could just arbitrarily select classes to remove but it would be better if the solver would remove the least wanted ones.

In other words, we want to add constraints which will force the solver to remove the most unwanted classes from the solution. But we also need to remember that we added constraints for having minimum number of assigned students so we need to be careful.

First, we need to add a boolean variable meaning that class is removed. Let us assume that denotes the total number of classes in course which need to be removed (of course . The constraint to remove classes is:

This formula says that the sum of variables representing classes’ removal must be equal to the total number of classes which should be removed. Now we need to change our constraint for lower bound on the number of people assigned to a class to the following:

We can do this, because is a constant value, so we can multiply it easily by variable .

So how does it work? When is (which means that class is removed), lower bound on the number of people count assigned to that class cannot be less than , so it can by any non-negative integer. On the other hand, when is equal to , it works just like before.

Now we can remove a class and not bother with its participation lower bound. But we still can assign students to removed classes. We need to change our formula for room capacity, but we can do it in the same way:

Summary

Most of the defined requirements are rather straightforward and yet very powerful. If we would solve the problem right now, the solution would represent very handy assignment, however, students still would not be satisfied. Next time we are going to implement basic cost function to improve their happiness.

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

In previous part we introduced Students Placement Problem. Today we start implementing it using ILP. We will define the variables and consider constraints which are required. We need to fulfill them so the students will be able to finish their courses (so they will be physically able to attend classes and pass exams), however, we don’t care about happiness for now.

Variables

Students Placement Problem is another example of problem easily represented using 0-1 linear programming. For every student, every course, and every class we need to answer simple question: “is student assigned to this class?” This means that we can use binary variables to represent allocations. We define the following:

In the solution, value one of means that the student is assigned to class . Value zero means the opposite.

Having these variables we are now able to consider constraints. We assume that every course lasts for some weeks and every week is a single unit. So student registered for such a course should attend exactly one class of that course every week. We also require that there is enough room for every assigned student. Students are allowed to mark some classes as impossible and we require they are not assigned to them. Finally, student cannot be assigned to two classes happening at the same time — we don’t want the student to learn bi-locating.

These requirements guarantees that every assigned student is physically able to finish his or her studies. The student probably will not be happy with the outcome, however, it is not our goal for now. We will take care of that later.

Enough Classes for each Student

We require that the student is assigned to one and only one class for every course. In order to do that, we need the following constraints:

For every student and for every course we sum the student’s variables for all classes of that course. We then set this sum to be equal to one which means that the student will be allocated to exactly one class within the course.

Collisions

We do not want students to be assigned to two classes at the same time. In order to do that, for each pair of classes happening at the same moment we need to add the following constraints:

You might wonder why instead of . However, the latter would require the student to be assigned to at least one of the colliding classes but this is not what we want.

Upper Bound for Assigned People

Every room has its capacity. We cannot assign more students that the room can accept because some of the students would not have a place to seat or computer to work on. So we need to add the following:

In this formula means the upper bound for number of assigned students for class

Impossibility

Finally, every student is allowed to mark a class as impossible. We need to make sure that the student is not assigned to that class and we can achieve this by simply setting variable to zero:

Summary

We might now try to solve the problem and we should get correct assignment for students. In next parts we will try to make sure that they get classes which they prefer. See you soon.

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

Hi! In this part of ILP series we start another series — Students Placement Problem. Today we will see the description of the problem and will try to introduce few definitions. In next parts we will formulate the problem using ILP and try to solve it.

Students Placement Problem — Introduction

Imagine a university and students who want to enroll for oncoming courses. Usually the authorities of the university creates the timetable and give it to students, so they are assigned to fixed groups and (usually) cannot easily change their schedule. However, some universities approach the problem in different way — they only create basic schedule of lectures and classes. It is up to students how they create groups and choose classes which they prefer most. This approach is very flexible for students because they are able to easily attend classes and leisure time duties, however, it might be difficult for students to create groups in a way that everyone is happy. We call this problem of creating groups a “Students Placement Problem”.

University Timetable

At the beginning of each semester, the authorities of the university prepare a timetable of lectures, classes, and all other students’ activities. The timetable contains their starting and ending times (e.g., Algebra Class begins at 8:00 AM on Monday and ends at 10:00 AM the same day). Since there are many students and they are not able to attend the same class at once (e.g., because the room can be occupied by at most 20 students), the timetable consists of many instances of the same activity. For instance, Algebra Class might happen on Monday, Tuesday, and Thursday, so at most 60 students are able to attend the classes. Students can choose class which suits them most.

By a “course” we understand a course at university, e.g., Algebra, Calculus etc. By a “class” we understand single instance of class within the course. For instance, Algebra course might have three classes: on Monday, Tuesday, and on Thursday. Every “class” has assigned begin time, end time, upper limit for number of attending students, lecturer, room, and all other things which are required by the class.

Having such a timetable, our goal is to calculate the placement of students in a way that they are “happy”. We will define happiness in one of the next parts. We need to consider some formal requirements — e.g., maximum number of students which can fit the room — but the final assignment is up to us. The authorities of the university do not impose any restrictions on the form of final students’ schedules. For instance, students are not bound to attend the university every day or start classes at 8:00 AM.

To sum up. We are given a general timetable of classes and calculate the allocation of students to make everyone happy. This is our goal. And, one more thing, we are going to use ILP.

Some definitions

We introduce the following definitions:

1. — total number of courses
2. — general schedule consisting courses
3. Every course has classes
4. Every course is defined as a set of classes:
5. — number of students
6. — set of students
7. Every student is defined as a — a set of preferences for student for classes in courses

For the sake of brevity we assume that every student is registered for every course. It is just an implementation detail.

Preferences

We need to define one more thing. Since we want to maximize happiness of students, we need to have some metric to be able to represent their happiness using numbers. We do it in the following way: for every class we ask every student to give a number from zero to ten representing his or her preference to be assigned to this class. Value of ten means that the student would love to be assigned to this particular class, value zero means the opposite — student really doesn’t want to be assigned to this instance. We also give students possibility to mark some classes as impossible for them. This means that the student ins physically unable to attend the class (e.g., because of other duties).

Having this preferences, our goal is to make students as happy as possible. As we will see soon, we can calculate the happiness in many different ways. For now you can intuitively assume that we want to give students classes with higher preferences points.

Summary

In the next part we are going to define part of necessary constraints and variables to represent the problem using ILP. See you soon.