Hacking on GraphHopper - a Java road routing engine. Peter has posted 62 posts at DZone. You can read more from them at their website. View Full User Profile

Assignment Algorithms to improve Perfomance of Automated Timetabling

01.29.2012
| 5255 views |
  • submit to reddit

Over the last two days I’ve read the old Java code of a board game. Although the game still compiles and works (it even works on a Zaurus device) the code itself is horrible: no unit tests, thread issues, a lot of static usages and mixed responsibilities. But then I ‘rediscovered’ my old TimeFinder project, which is a lot better – at least it has several unit tests! Then I saw that I even wanted to publish a paper regarding a nice finding I made 3 years ago. But I never published it as the results were too disappointing to me at that time.

Nevertheless I think the idea is still worth to be spread around (you are free to avoid usage ;) ). BTW: now you know why my blog starts with “Find Time …” and why my twitter nick name is called timetabling – its all about history.

My Draft of a paper

So here is my “paper” ‘Optimizing Educational Schedules Using Hungarian Algorithm and Iterated Local Search‘ with the following main result:

The algorithm is bad when it comes to softconstraint optimizations (it wasn’t designed for this though) but it really shines to reduce hard constraints of timetabling problems. E.g. it was an order of magnitude faster than the 5th place (Mueller with UniTime) of the International Timetabling Competition 2007. Of course, I didn’t compare the latest version of UniTtime with TimeFinder yet.

Let me know what you think!

Now I would like to talk a bit about how one could in general use assigment algorithms in timetabling.

Using Assignment Algorithms in Timetabling

In this paper a technic is shown how assignment algorithms could be applied in timetabling. Only a few papers are known to us which uses assignment algorithms based on graph theory [Kin05, Bah04, MD77, TM02].
An assignment algorithm can be used as a subprocedure of a heuristic as it is done in the open source timetabling application called TimeFinder [Kar08]. TimeFinder uses an Hungarian algorithm only to assign a location to an event, where the solution itself is improved with a heuristic based on iterated local search [SLM03], we called this heuristic NoCollisionPrinciple.
Another possibility is to use an assignment algorithms as the ’backbone’ of a heuristic as it is done in [Bah04], where the Hungarian Algorithm is modified to act as a timetabling optimization algorithm.A third approach is to use an assignment algorithm as a pre-solver of another algorithm. This is planed for the TimeFinder project: before using the constraint based algorithm of UniTime an assignment algorithm will be used to give a good and fast starting point where all hard constraints are valid.

In all cases the good performance and optimal results of a mathmatically founded technic are the reason they are choosen and promise a good performing algorithm.

The heuristic tries to add and remove events to specific timeslots very often. So, the check if there is a room available for event E1 in a timeslot has to be very fast. But if there are already a lot of rooms and events in this timeslot it is difficult to test with a simple method if a valid room for E1 exists. Here the assignment algorithms came to my rescue. Other algorithms like the auction algorithm could solve the assignment problem, too, but are not discussed here.

An example for one cost matrix, where we want to calculate the minimal weighted matching (“best assignment”) later, could be the following:

Rooms \ Events | E1    E2
------------------------
R1             | 12    10
R2             | 16    3

The entries of the matrix are the difference of the seats to the visitors. E.g. (E2,R2)=3 means there will be 3 free seats which is better than (E2,R1)=10 free seats.

To optimize room-to-event-assignments it is necessary that the assigned room has nearly the same or slightly more seats as event E1 has visitors. The difference shouldn’t be too large, so that no seats will be ‘wasted’ (and an event with more visitors could be assigned later)

Of course, it could be that an entry is not valid (e.g. too many visitors) then the value in the matrix is +infinity.

The best solution (minimal sum) here would be E1,R1 and E2, R2 with a total sum of 15.

Some informations about the words in graph theory: this cost matrix is equivalent to a weighted, undirected, bi-partitioned, complete graph G. Weighted means with numbers instead of booleans; undirected means the same value for (Ex,Ry) and (Ry,Ex); bi-partitioned means the graph can be divided in two sets A and B where “A and B = empty” and “A or B = G”; complete means the cost matrix has the same number of rows and columns, you can always force this with +infinity values.

Assignment Algorithms

The easiest way to solve an assignment problem correctly is a brute force algorithm, which is very slow for big n: O(n!).
(Okay, it is even slow for small n=10: 10!=3628800)
Where n is in my case the number of rooms available in one timeslot. But this algorithm is always correct, because it tries all combinations of assignments and picks the the one with the minimal total sum. I used this algorithm to check the correctness of other assignment algorithms I implemented later.

Now it is great to know that there is another very fast and correct algorithm which is called Kuhn-Munkres [1] or Hungarian algorithm. The running time is O(n³) (10³=1000) and the ideas used in this algorithm are based on graph theory. Another optimization which one could use only in special cases is the incremental assignment algorithm with O(n²) (E.g. for “add one assignment” or “remove one assignment”)

And there are even faster algorithms such as the algorithm from Edmons and Carp [2]. For bi-partite graphs it runs in O(m n log n).

An interesting approach are the approximation assignment algorithms which can be a lot faster: O(n²) with a small constant. But the resulting assignments are not the best in every case.
A well known and easy to implemented algorithm the path growing algorithm from Drake and Hougardy [3] which works as follows:

currentMatching = matching0 = empty
matching1 = empty
while edges are not empty
   choose a node x from all nodes which has at least one neighbor
   while x has a neighbor
       find the heaviest edge e={x,y} incident to x
       add it to the currentMatching
       if(currentMatching == matching1) currentMatching = matching0
       else currentMatching = matching1
       remove x from the graph
       x:=y
   end
end

The good thing of this algorithm is that you can say sth. about the resulting assignment: the total sum is maximal twice times higher then the sum gained with an optimal algorithm. There are even better guarantees e.g. the one of Pettie and Sanders (~ maximal 3/2 times higher):

matching is empty
repeat k times
  choose a node x from all nodes at random
  matching := matching (+) aug(x)
end
return matching
Resources

You can grab the source of TimeFinder (Apache2 licensed) via svn:

svn checkout https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk timefinder

Then look in the package

timefinder-core/src/main/java/de/timefinder/core/algo/

To build it you have to use maven.

And finally here is the paper where the idea of a maximum network flow was already presented:
John van den Broek, Cor A. J. Hurkens, and Gerhard J. Woeginger. Timetabling problems at the TU Eindhoven. Electronic Notes in Discrete Mathematics, 25:27–28, 2006.

References

[1] Kuhn Munkres, “Algorithms for the Assignment and Transportation Problems”
[2] Edmonds and Karp, “Theoretical improvements in algorithmic efficiency for network flow problems“.
[3] Drake and Hougardy, A Simple Approximation Algorithm for the Weighted Matching Problem, 2002
[4] Pettie and Sanders, A Simpler Linear Time 2/3 – epsilon Approximation for Maximum Weight Matching, Inf. Process. Lett. Vol 91, No. 6, 2004

 

From http://karussell.wordpress.com/2012/01/22/assignment-algorithms-automated-timetabling/

Published at DZone with permission of its author, Peter Karussell.

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Geoffrey De Smet replied on Sun, 2012/01/29 - 5:55am

Hi Peter, it's been a while. Intresting article :)

Might you have any benchmark metrics that compare the results of the different algorithms, preferably as a graph? With Drools Planner, I am running benchmarks of a multiple construction heuristics and metaheuristics over several use cases (including exam scheduling and course scheduling) over multiple data sets. The results are intresting: for one use case, some algorithms are consistently better then other algorithms, but the winning algorithm differs per use case. In fact, the only way to determine the best algorithm for 1 use case is to try all of them (which is easy).

I haven't implemented the hungarian method yet, but I wonder how it compares against the construction heuristics such as First Fit, First Fit Decreasing, Best Fit, Best Fit Decreasing, Cheapest Insertion and Nearest Neighbour. Here's a graph comparing some of those construction heuristics.

As for the Local Search metaheuristics (which come after the construction heuristics): in my experience, Tabu Search and Simulated Annealing work best for me, but I haven't tried another Iterated Local Search yet. The link to the description of your Iterated Local Search doesn't work for me. Is it a Random Restart Local Search or a different form?

Peter Karussell replied on Sat, 2012/02/04 - 2:48pm

Hi Geoffrey,

yeah its been a while :) nice to hear from you!

The comparison was only was at that time in the draft I mentioned in the article - is that link not working for you?

http://karussell.files.wordpress.com/2012/01/patat10-pkarich-timefinder.pdf

And you can see that the algorithm is really good in reducing hard constraint resolution and really bad when it comes to soft constraints. But I'm still very happy with it because the core of the algorithm was coded 3 months before the deadline :) and I only wanted to reduce the HC to 0 for all known instances as fast as possible as this was the main competition criteria.

The problem now is that I cannot say if my heuristic or the assignment algorithm or both are the important parts which makes hard constraint reduction so fast.

BTW1: I'm still not sure if one can call this method an iteratered local search - let me know what you think :)

"the algorithm will unassign some events randomly and start over inserting in the last step"

BTW2: If you also wonder why I chose weighted and not the unweighted assigment algorithm - I did today :) but the answer is that the weighted assigment algorithm works better if the durations of the events are different and greater 0. I can explain further if you like.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.