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.
Other formats:   BibTeX LaTeX RIS
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
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
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
Tags International impact, Reviewed
Changed by Changed by: doc. Mgr. Hana Rudová, Ph.D., učo 3840. Changed: 11/4/2012 08:51.
Abstract
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
PrintDisplayed: 27/5/2024 21:50