k 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

Příznaky

Mezinárodní význam, Recenzováno
Změněno: 2. 5. 2011 08:33, doc. Mgr. Hana Rudová, Ph.D.

Anotace

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
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