Solving the Travelling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach
Solving the Travelling Tournament Problem: A Combined Integer Programming and Constraint Programming Approach
复制标题
解决旅行锦标赛问题：整数规划和约束规划相结合的方法
DOI：
10.1007/978-3-540-45157-0_6
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Trick
中科院分区：
文献类型：
--
作者：
Kelly Easton;G. Nemhauser;M. Trick
旅行锦标赛问题是一个运动竞赛问题，要求为n个参赛队设计一个最小距离的双循环赛。这个问题即使是很小的例子似乎也很难解决。在本文中，我们为八个团队的实例提供了第一个可证明的最佳解决方案。该解决方案的方法是一个并行实现的分支和价格算法，使用整数规划来解决主问题和约束规划来解决定价问题。此外，约束规划被用作原始启发式。
The Travelling Tournament Problem is a sports timetabling problem requiring production of a minimum distance double round-robin tournament for a group ofnteams. Even small instances of this problem seem to be very difficult to solve. In this paper, we present the first provably optimal solution for an instance of eight teams. The solution methodology is a parallel implementation of a branch-and-price algorithm that uses integer programming to solve the master problem and constraint programming to solve the pricing problem. Additionally, constraint programming is used as a primal heuristic.