2008
A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
BURKE, Edmund K., Jakub MAREČEK, Andrew J. PARKES a Hana RUDOVÁZákladní údaje
Originální název
A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
Název česky
Metoda větví a řezů pro rozvrhovací problém z Udine
Autoři
BURKE, Edmund K. (826 Velká Británie a Severní Irsko), Jakub MAREČEK (203 Česká republika, garant, domácí), Andrew J. PARKES (826 Velká Británie a Severní Irsko) a Hana RUDOVÁ (203 Česká republika, domácí)
Vydání
Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling, 2008
Další údaje
Jazyk
angličtina
Typ výsledku
Prezentace na konferencích
Obor
10201 Computer sciences, information science, bioinformatics
Stát vydavatele
Kanada
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Kód RIV
RIV/00216224:14330/08:00041927
Organizační jednotka
Fakulta informatiky
Klíčová slova anglicky
integer programming; branch-and-cut; cutting planes; soft constraints; educational timetabling; university course timetabling
Štítky
Příznaky
Mezinárodní význam, Recenzováno
Změněno: 2. 5. 2011 08:33, doc. Mgr. Hana Rudová, Ph.D.
V originále
This paper describes a branch-and-cut procedure for a curriculum-based university course timetabling. First, we present an alternative integer programming formulation for this problem, which uses a lower than usual number of variables and a number of constraints exponential in the number of periods per day necessary to reach optimality. Second, we present a branch-and-cut procedure, where constraints from enumeration of event/free-period patterns, necessary to reaching optimality, are added only when they are violated. We also describe further problem-specific cuts from bounds implied by the soft constraints, cuts from patterns given by days of instruction and free days, and all related separation routines. We also discuss applicability of standard cuts for the graph colouring and weighted matching. The results of our preliminary experimentation with an implementation using ILOG Concert and CPLEX 10 are provided.
Česky
Práce popisuje řešení rozvrhovacího problému z univerzity v Udine metodou větví a mezí se za běhu generovanými řeznými rovinami (branch-and-cut).
Návaznosti
| GA201/07/0205, projekt VaV |
| ||
| MSM0021622419, záměr |
|