ALCOMFT-TR-01-84

Matthias Elf, Michael Jünger and Giovanni Rinaldi
Minimizing Breaks by Maximizing Cuts
Cologne. Work package 4. May 2001.

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.

Postscript file: ALCOMFT-TR-01-84.ps.gz (97 kb).