| Popis: |
Round robin tournaments are omnipresent in sport competitions and beyond. We propose two new integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations with the linear relaxation of a well-known traditional formulation. We find that the matching formulation is stronger than the other formulations, while its LP relaxation is still being solvable in polynomial time. In addition, we provide an exponentially sized class of valid inequalities for the matching formulation. Complementing our theoretical assessment of the strength of the different formulations, we also experimentally show that the matching formulation is superior on a broad set of instances. Finally, we describe a branch-and-price algorithm for finding round robin tournaments that is based on the matching formulation. |
Full Text from ScienceDirect