Decomposition, reformulation, and diving in university course timetabling

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BURKE Edmund K. MAREČEK Jakub PARKES Andrew J. RUDOVÁ Hana

Year of publication 2010
Type Article in Periodical
Magazine / Source Computers & Operations Research
MU Faculty or unit

Faculty of Informatics

Citation
Web
Field Informatics
Keywords Integer programming; Decomposition; Reformulation; Diving; Heuristic; Metaheuristic; University Course Timetabling; Soft Constraints
Description In many real-life optimisation problems, there are multiple interacting components in a solution. This paper studies an approach to such problems, which can be thought of as multiphase exploitation of multiple objective-/value-restricted submodels. In this approach, 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. Our study is performed on a university course timetabling problem used in the 2007 International Timetabling Competition, also known as the Udine Course Timetabling Problem. Integer programming formulations for all subproblems are given and evaluated using ILOG CPLEX 11.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.