Minimizing Breaks by Maximizing Cuts

Elf, Matthias and Jünger, Michael and Rinaldi, Giovanni (2003) Minimizing Breaks by Maximizing Cuts.
Published in: Operations Research Letters Vol. 31 (5). pp. 343-349.


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.

Download: [img] Postscript - Preprinted Version
Download (1MB) | Preview
Download: [img] PDF - Preprinted Version
Download (203kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 45 (Google Scholar) | 21 (Web of Science)
Uncontrolled Keywords: maximum cut sports scheduling
Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Juenger
Related URLs:
Deposit Information:
ZAIK Number: zaik2001-409
Depositing User: Matthias Elf
Date Deposited: 19 Jul 2003 00:00
Last Modified: 19 Dec 2011 09:44