Improving Bounds on the Football Pool Problem by Integer Programming and High-Throughput Computing

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.