BURKE, Edmund, Jakub MAREČEK, Andrew PARKES a Hana RUDOVÁ. A Branch-and-cut Procedure for the Udine Course Timetabling Problem. Annals of Operations Research. Springer Science+Business Media, LLC, 2012, roč. 194, č. 1, s. 71-87. ISSN 0254-5330. Dostupné z: https://dx.doi.org/10.1007/s10479-010-0828-5. |
Další formáty:
BibTeX
LaTeX
RIS
@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 a Hana RUDOVÁ. A Branch-and-cut Procedure for the Udine Course Timetabling Problem. \textit{Annals of Operations Research}. Springer Science+Business Media, LLC, 2012, roč.~194, č.~1, s.~71-87. ISSN~0254-5330. Dostupné z: https://dx.doi.org/10.1007/s10479-010-0828-5.
|