2010
Decomposition, reformulation, and diving in university course timetabling
BURKE, Edmund K., Jakub MAREČEK, Andrew J. PARKES a Hana RUDOVÁ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
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í
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
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 14. 5. 2010 13:07, doc. Mgr. Hana Rudová, Ph.D.
V originále
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.
Č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 |
| ||
| MSM0021622419, záměr |
|