Decomposition, reformulation, and diving in university course timetabling

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

Základní údaje

• Originální název: Decomposition, reformulation, and diving in university course timetabling
• Název česky: Dekompozice, reformulace a hloubkové prohledávání v univerzitním rozvrhování
• Autoři: BURKE, Edmund K. (826 Velká Británie a Severní Irsko), Jakub MAREČEK (203 Česká republika, garant), Andrew J. PARKES (826 Velká Británie a Severní Irsko) a Hana RUDOVÁ (203 Česká republika).
• Vydání: Computers & Operations Research, Amsterdam, Elsevier, 2010, 0305-0548.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10201 Computer sciences, information science, bioinformatics
• Stát vydavatele: Nizozemské království
• Utajení: není předmětem státního či obchodního tajemství
• WWW: DOI URL
• Impakt faktor: Impact factor: 1.769
• Kód RIV: RIV/00216224:14330/10:00042430
• Organizační jednotka: Fakulta informatiky
• UT WoS: 000271369400016
• Klíčová slova anglicky: Integer programming; Decomposition; Reformulation; Diving; Heuristic; Metaheuristic; University Course Timetabling; Soft Constraints
• Štítky: decomposition, diving, Heuristic, integer programming, Metaheuristic, Reformulation, soft constraints, university course timetabling
• Příznaky: Mezinárodní význam, Recenzováno

Anotace

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.

Anotace česky

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.

Návaznosti

• GA201/07/0205, projekt VaV: Název: Dynamické aspekty rozvrhování

Investor: Grantová agentura ČR, Dynamické aspekty rozvrhování

• MSM0021622419, záměr: Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy