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

J 2012

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

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

Basic information

Original name

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

Authors

BURKE, Edmund (826 United Kingdom of Great Britain and Northern Ireland), Jakub MAREČEK (203 Czech Republic, belonging to the institution), Andrew PARKES (826 United Kingdom of Great Britain and Northern Ireland) and Hana RUDOVÁ (203 Czech Republic, guarantor, belonging to the institution)

Edition

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

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 1.029

RIV identification code

RIV/00216224:14330/12:00058937

Organization unit

Faculty of Informatics

DOI

http://dx.doi.org/10.1007/s10479-010-0828-5

UT WoS

000300574500005

Keywords in English

Integer programming; Branch-and-cut; Cutting planes; Soft constraints; Educational timetabling; University course timetabling

Abstract

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.

Links

MSM0021622419, plan (intention)

Name: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems

Citovat

BURKE, Edmund, Jakub MAREČEK, Andrew PARKES and Hana RUDOVÁ. A Branch-and-cut Procedure for the Udine Course Timetabling Problem. Annals of Operations Research. Springer Science+Business Media, LLC, 2012, vol. 194, No 1, p. 71-87. ISSN 0254-5330. Available from: https://dx.doi.org/10.1007/s10479-010-0828-5.

@article{917475,
   author = {Burke, Edmund and Mareček, Jakub and Parkes, Andrew and Rudová, Hana},
   article_number = {1},
   doi = {http://dx.doi.org/10.1007/s10479-010-0828-5},
   keywords = {Integer programming; Branch-and-cut; Cutting planes; Soft constraints; Educational timetabling; University course timetabling},
   language = {eng},
   issn = {0254-5330},
   journal = {Annals of Operations Research},
   title = {A Branch-and-cut Procedure for the Udine Course Timetabling Problem},
   volume = {194},
   year = {2012}
}

TY  - JOUR
ID  - 917475
AU  - Burke, Edmund - Mareček, Jakub - Parkes, Andrew - Rudová, Hana
PY  - 2012
TI  - A Branch-and-cut Procedure for the Udine Course Timetabling Problem
JF  - Annals of Operations Research
VL  - 194
IS  - 1
SP  - 71-87
EP  - 71-87
PB  - Springer Science+Business Media, LLC
SN  - 02545330
KW  - Integer programming
KW  - Branch-and-cut
KW  - Cutting planes
KW  - Soft constraints
KW  - Educational timetabling
KW  - University course timetabling
N2  - 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.
ER  -

BURKE, Edmund, Jakub MAREČEK, Andrew PARKES and Hana RUDOVÁ. A Branch-and-cut Procedure for the Udine Course Timetabling Problem. \textit{Annals of Operations Research}. Springer Science+Business Media, LLC, 2012, vol.~194, No~1, p.~71-87. ISSN~0254-5330. Available from: https://dx.doi.org/10.1007/s10479-010-0828-5.

Detailed Information on Publication Record