Decomposition, reformulation, and diving in university course timetabling

BURKE, Edmund K., Jakub MAREČEK, Andrew J. PARKES and Hana RUDOVÁ. Decomposition, reformulation, and diving in university course timetabling. Computers & Operations Research. Amsterdam: Elsevier, 2010, vol. 37, No 3, p. 582-597. ISSN 0305-0548.

Basic information

• Original name: Decomposition, reformulation, and diving in university course timetabling
• Name in Czech: Dekompozice, reformulace a hloubkové prohledávání v univerzitním rozvrhování
• Authors: BURKE, Edmund K. (826 United Kingdom of Great Britain and Northern Ireland), Jakub MAREČEK (203 Czech Republic, guarantor), Andrew J. PARKES (826 United Kingdom of Great Britain and Northern Ireland) and Hana RUDOVÁ (203 Czech Republic).
• Edition: Computers & Operations Research, Amsterdam, Elsevier, 2010, 0305-0548.

Other information

• Original language: English
• Type of outcome: Article in a journal
• Field of Study: 10201 Computer sciences, information science, bioinformatics
• Country of publisher: Netherlands
• Confidentiality degree: is not subject to a state or trade secret
• WWW: DOI URL
• Impact factor: Impact factor: 1.769
• RIV identification code: RIV/00216224:14330/10:00042430
• Organization unit: Faculty of Informatics
• UT WoS: 000271369400016
• Keywords in English: Integer programming; Decomposition; Reformulation; Diving; Heuristic; Metaheuristic; University Course Timetabling; Soft Constraints
• Tags: decomposition, diving, Heuristic, integer programming, Metaheuristic, Reformulation, soft constraints, university course timetabling
• Tags: International impact, Reviewed

Abstract

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.

Abstract (in Czech)

V mnoha optimizačních problémech je několik provázaných částí řešení. Tyto části mohou odpovídat například přiřazení určitým druhům zdrojů. Částem mohou odpovídat soubory měkkých podmínek, resp. měřítka porušení odpovídajících měkkých podmínek. Cílem potom je minimalizovat lineární kombinaci těchto měřítek. Tento článek studuje přístup k takovým problémům, založený na postupném řešení podproblémů vzniklých omezením hodnot nebo účelové funkce. V první fázi je uvažována jenom jedna část řešení a příslušné měkké podmínky. Tak vznikají částečná řešení, která omezují hodnoty uvažované v dalších fázích. Často je možné v první fázi pracovat s podstatně menším prostorem řešení, a přesto zaručit že v následujících fázích bude možné najít přípustná řešení celého problému. Při použití celočíselného programování alespoň v první fázi je tak možné vyvíjet heuristiky, které poskytují i informace o horních i spodních mezích hodnoty účelové funkce pro danou instanci. Studie pracuje s příkladem problému použitého v International Timetabling Competition v roce 2007, známého též jako Udine Course Timetabling Problem. Formulace problému i jednotlivých subproblémů v celočíselném programování jsou popsány a je vyhodnoceno jejich chování v řešiči ILOG CPLEX 11. Širší použitelnost tohoto přístupu je též analyzována a diskutována.

Links

• GA201/07/0205, research and development project: Name: Dynamické aspekty rozvrhování

Investor: Czech Science Foundation, Dynamic Aspects of Scheduling

• MSM0021622419, plan (intention): Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems