Friday, December 9, 2005
1:30 p.m. Posner Hall 151
Francois Margot
Associate Professor of Operations Research, Tepper School of Business
Code Construction with ILP
This talk covers on-going work to solve one of the oldest and most famous problems in combinatorial coding theory, the Football Pool Problem. A more technical description of the problem is finding a ternary code of minimum cardinality with covering radius one. The smallest open case, for code words of length 6, still resists all solution attempts, despite a lot of efforts.
The talk covers techniques proposed by others and their integration within several ILP formulations used as preliminary steps in a solution approach. Partial results obtained are promising and improving the best known lower bound on the solution seems possible.
Improving the formulation of the ILPs is an open research problem that has received little attention so far. Some research directions will be mentioned.
The solution of the ILPs (binary and non binary) uses isomorphism pruning techniques to good effect. Yet, extensive computing resources will be required for a complete solution. Code using Condor and MW giving access to large parallel grid computing has been implemented.
