Decomposition, Reformulation, and Diving in University Course Timetabling - Computer Science > Data Structures and AlgorithmsReport as inadecuate




Decomposition, Reformulation, and Diving in University Course Timetabling - Computer Science > Data Structures and Algorithms - Download this document for free, or read online. Document in PDF available to download.

Abstract: In many real-life optimisation problems, there are multiple interactingcomponents in a solution. For example, different components might specifyassignments to different kinds of resource. Often, each component is associatedwith different sets of soft constraints, and so with different measures of softconstraint violation. The goal is then to minimise a linear combination of suchmeasures. This paper studies an approach to such problems, which can be thoughtof as multiphase exploitation of multiple objective-value-restrictedsubmodels. In this approach, only one computationally difficult component of aproblem and the associated subset of objectives is considered at first. Thisproduces partial solutions, which define interesting neighbourhoods in thesearch space of the complete problem. Often, it is possible to pick the initialcomponent so that variable aggregation can be performed at the first stage, andthe neighbourhoods to be explored next are guaranteed to contain feasiblesolutions. Using integer programming, it is then easy to implement heuristicsproducing solutions with bounds on their quality.Our study is performed on a university course timetabling problem used in the2007 International Timetabling Competition, also known as the Udine CourseTimetabling Problem. In the proposed heuristic, an objective-restrictedneighbourhood generator produces assignments of periods to events, withdecreasing numbers of violations of two period-related soft constraints. Thoseare relaxed into assignments of events to days, which define neighbourhoodsthat are easier to search with respect to all four soft constraints. Integerprogramming formulations for all subproblems are given and evaluated using ILOGCPLEX 11. The wider applicability of this approach is analysed and discussed.



Author: Edmund K. Burke, Jakub Marecek, Andrew J. Parkes, Hana Rudova

Source: https://arxiv.org/







Related documents