A BRANCH AND CUT ALGORITHM FOR SHEDULING THE HIGHLY-CONSTRAINED CHILEAN SOCCER TOURNAMENT
Author
Duran Maggiolo, Guillermo AlfredoNoronha, Thiago F
Ribeiro, Celso
Souyris, Sebastian
Weintraub Pohorille, Andres Felix
Abstract
The qualifying phase of the Chilean soccer championship follows the structure of a compact single round robin tournament. Good schedules are of major importance for the success of the tournament, making them more balanced, profitable, and attractive. The schedules were prepared by ad hoc procedures until 2004, when a rough integer programming strategy was proposed. In this work, we improve the original integer programming formulation. We derive v...
Ver más
The qualifying phase of the Chilean soccer championship follows the structure of a compact single round robin tournament. Good schedules are of major importance for the success of the tournament, making them more balanced, profitable, and attractive. The schedules were prepared by ad hoc procedures until 2004, when a rough integer programming strategy was proposed. In this work, we improve the original integer programming formulation. We derive valid inequalities for improving the linear relaxation bound and we propose a new branch-and-cut strategy for the problem. Computational results on a real-life instance illustrate the effectiveness of the approach and the improvement in solution quality.
Ver menos
Book's title
PRACTICE AND THEORY OF AUTOMATED TIMETABLING VI
Publication date of the book
2007Start page
174
End page
186
Country
ALEMANIA