Improving Bounds on the Football Pool Problem by Integer Programming and High-Throughput Computing
Jeff Linderoth, François Margot, Greg Thain
INFORMS Journal on Computing · 2009 · Volume 21 · Issue 3
Abstract
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.
Keywords
football pool problem, high-throughput computing, branch and bound, Condor, master-worker
Enable JavaScript for citation tools and additional paper interactions.