论文标题
循环赛的整数编程模型
Integer Programming Models for Round Robin Tournaments
论文作者
论文摘要
Round Robin比赛在体育比赛及其他地区无处不在。我们提出了两个新的整数编程公式，用于安排循环锦标赛，其中之一是我们称之为匹配的公式。我们通过分析将它们的线性放松与众所周知的传统配方的线性松弛进行比较。我们发现匹配配方比其他配方更强，而其LP松弛仍可以在多项式时间内解决。此外，我们为匹配公式提供了指数尺寸的有效不平等类别。与我们对不同配方强度的理论评估相辅相成，我们还通过实验表明，在广泛的实例中，匹配公式是优越的。最后，我们描述了一种基于匹配配方的循环锦标赛的分支机构和价格算法。
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.
