Decomposition, reformulation, and diving in university course timetabling

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
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

Citace
www
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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.