J 2012

A Branch-and-cut Procedure for the Udine Course Timetabling Problem

BURKE, Edmund, Jakub MAREČEK, Andrew PARKES a Hana RUDOVÁ

Základní údaje

Originální název

A Branch-and-cut Procedure for the Udine Course Timetabling Problem

Autoři

BURKE, Edmund (826 Velká Británie a Severní Irsko), Jakub MAREČEK (203 Česká republika, domácí), Andrew PARKES (826 Velká Británie a Severní Irsko) a Hana RUDOVÁ (203 Česká republika, garant, domácí)

Vydání

Annals of Operations Research, Springer Science+Business Media, LLC, 2012, 0254-5330

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

Kód RIV

RIV/00216224:14330/12:00058937

Organizační jednotka

Fakulta informatiky

UT WoS

000300574500005

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: 11. 4. 2012 08:51, doc. Mgr. Hana Rudová, Ph.D.

Anotace

V originále

Abstract A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem. A number of further classes of cuts are also introduced, arising from: enumeration of event/free-period patterns; bounds on the numbers of days of instruction; the desire to exploit integrality of the objective function value; the graph colouring component; and also from various implied bounds. An implementation of the corresponding branch-and-cut procedure is evaluated on the instances from Track 3 of the International Timetabling Competition 2007.

Návaznosti

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