Universität zu Köln

Elf, Matthias, Jünger, Michael and Rinaldi, Giovanni ORCID: 0000-0003-0148-2470 (2003). Minimizing Breaks by Maximizing Cuts. Operations Research Letters, 31 (5). pp. 343-349. Elsevier Science.

Preview

PDF zaik2001-409.pdf - Submitted Version Download (203kB) | Preview

Abstract

Jean Charles Régin and Michael Trick have proposed to solve the schedule generation problem for sports leagues in two phases in which the first generates a tournament schedule and the second fixes the home-away pattern so as to minimize the number of breaks. While constraint programming techniques appear to be the methods of choice for the first phase, we propose to solve the break minimization problem in sports scheduling by transforming it into a maximum cut problem in an undirected graph and applying a branch-and-cut algorithm. Our approach outperforms previous approaches with constraint programming and integer programming techniques.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Elf, Matthias UNSPECIFIED UNSPECIFIED UNSPECIFIED Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Rinaldi, Giovanni UNSPECIFIED orcid.org/0000-0003-0148-2470 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-548541
Journal or Publication Title:	Operations Research Letters
Volume:	31
Number:	5
Page Range:	pp. 343-349
Date:	2003
Publisher:	Elsevier Science
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/54854