Integer programming models for round robin tournaments
研究了三种循环赛赛程安排的整数规划模型，发现匹配模型的线性松弛更强且可多项式求解，并提出了有效不等式和分支定价算法。
Round robin tournaments are omnipresent in sport competitions and beyond. We investigate three integer programming formulations for scheduling a round robin tournament, one of which we call the matching formulation. We analytically compare their linear relaxations, and find that the relaxation of the matching formulation is stronger than the other relaxations, while 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.