Improving Bounds on the Football Pool Problem by Integer Programming and High-Throughput Computing
Improving Bounds on the Football Pool Problem by Integer Programming and High-Throughput Computing
复制标题
通过整数规划和高吞吐量计算改善足球池问题的界限
DOI：
--
复制
发表时间：
2009
影响因子：
2.1
通讯作者：
G. Thain
中科院分区：
文献类型：
--
作者：
Jeff T. Linderoth;F. Margot;G. Thain
足球博彩问题得名于一种彩票型游戏，参与者预测足球比赛的结果，该问题是确定长度为v的三进制字的半径1的最小覆盖码。对于v=6，最优解未知。使用同构剪枝、子码枚举和基于线性规划的定界相结合的方法，在由数千个处理器组成的高吞吐量计算网格上运行，我们能够将最优码大小的下界从65提高到71。
The football pool problem, which gets its name from a lottery-type game where participants predict the outcome of soccer matches, is to determine the smallest covering code of radius 1 of ternary words of length v. For v = 6, the optimal solution is not known. Using a combination of isomorphism pruning, subcode enumeration, and linear programming-based bounding, running on a high-throughput computational grid consisting of thousands of processors, we are able to improve the lower bound on the size of the optimal code from 65 to 71.