Memos Solvers: Timetabling

Decomposition, Reformulation, and Diving

a project of Jakub Marecek <jakub at marecek dot cz> (www)
supervised by Prof. Edmund K. Burke <ekb at cs dot nott dot ac dot uk> (www)
and Dr. Andrew J. Parkes <ajp at cs dot nott dot ac dot uk> (www)
and Dr. Hana Rudova <hanka at fi dot muni dot cz> (www).

An Overview

In many real-life optimisation problems, there are multiple interacting components in a solution. For example, different components might specify assignments to different kinds of resource. Often, each component is associated with different sets of soft constraints, and so with different measures of soft constraint violation. The goal is then to minimise a linear combination of such measures. In the multiphase exploitation of multiple objective-/value-restricted submodels (MEMOS) approach of Burke et al. (2009), only one computationally difficult component of a problem and the associated subset of objectives is considered at first. This produces partial solutions, which define interesting neighbourhoods in the search space of the complete problem. Often, it is possible to pick the initial component so that variable aggregation can be performed at the first stage, and the neighbourhoods to be explored next are guaranteed to contain feasible solutions. Using integer programming, it is then easy to implement heuristics producing solutions with bounds on their quality.

The sample solver is for university course timetabling problem used in the 2007 International Timetabling Competition, also known as the Udine Course Timetabling Problem. The goal is to find an assignment of events to periods and rooms, so that the assignment of events to periods is a feasible bounded colouring of an associated conflict graph and the linear combination of the numbers of violations of four soft constraints is minimised. In the proposed heuristic, an objective-restricted neighbourhood generator produces assignments of periods to events, with decreasing numbers of violations of two period-related soft constraints. Those are relaxed into assignments of events to days, which define neighbourhoods that are easier to search with respect to all four soft constraints. The freely available implementation features a number of subproblems and provides solutions with lower bounds (which often means guarantees of near-optimality) within reasonable time limits.

The use of advanced features of ILOG Concert and ILOG CPLEX could be of interest to C++ programmers. Hence, the source code is browsable on-line.



The sample solver is licenced under the GNU Public License (GPL) version 3. It would be greatly appreciated, however, if users would cite the following paper in any work that uses it:

The pre-print of the paper is then presented only to ensure timely dissemination of scholarly and technical work. Copyright is retained by the respective copyright holders.

Feeling bored? Go and explore Jakub's website! ;-)