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.

zaik2001-409.pdf - Submitted Version

Download (203kB) | Preview


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
CreatorsEmailORCIDORCID Put Code
Rinaldi, GiovanniUNSPECIFIEDorcid.org/0000-0003-0148-2470UNSPECIFIED
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


Downloads per month over past year


Actions (login required)

View Item View Item