Other formats:
BibTeX
LaTeX
RIS
@proceedings{767076,
author = {Burke, Edmund K. and Mareček, Jakub and Parkes, Andrew J. and Rudová, Hana},
booktitle = {Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling},
keywords = {integer programming; branch-and-cut; cutting planes; soft constraints; educational timetabling; university course timetabling},
language = {eng},
title = {A Branch-and-Cut Procedure for the Udine Course Timetabling Problem},
url = {http://w1.cirrelt.ca/%7Epatat2008/PATAT_7_PROCEEDINGS/Papers/Papers.htm},
year = {2008}
}
TY - CONF
ID - 767076
AU - Burke, Edmund K. - Mareček, Jakub - Parkes, Andrew J. - Rudová, Hana
PY - 2008
TI - A Branch-and-Cut Procedure for the Udine Course Timetabling Problem
KW - integer programming
KW - branch-and-cut
KW - cutting planes
KW - soft constraints
KW - educational timetabling
KW - university course timetabling
UR - http://w1.cirrelt.ca/%7Epatat2008/PATAT_7_PROCEEDINGS/Papers/Papers.htm
N2 - 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.
ER -
BURKE, Edmund K., Jakub MAREČEK, Andrew J. PARKES and Hana RUDOVÁ. A Branch-and-Cut Procedure for the Udine Course Timetabling Problem. In \textit{Proceedings of the 7th International Conference on the Practice and Theory of Automated Timetabling}. 2008.
|
