Decomposition, reformulation, and diving in university course timetabling
| Authors | |
|---|---|
| Year of publication | 2010 |
| Type | Article in Periodical |
| Magazine / Source | Computers & Operations Research |
| MU Faculty or unit | |
| 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: |