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.; MAREČEK Jakub; PARKES Andrew J.; RUDOVÁ Hana
• Rok publikování: 2010
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Computers & Operations Research
• Fakulta / Pracoviště MU: Fakulta informatiky

www

• DOI
• URL

• Obor: Informatika
• Klíčová slova: Integer programming; Decomposition; Reformulation; Diving; Heuristic; Metaheuristic; University Course Timetabling; Soft Constraints
• Popis: 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.

Související projekty

• Vysoce paralelní a distribuované výpočetní systémy
• Dynamické aspekty rozvrhování