Ahmad Abdi (LSE)

Ideal matrices and dyadic linear programming

A 0,1 matrix M is ideal if the set cover inequalities Mx>=1, together with nonnegativity constraints x>=0, define a polyhedron where every vertex is integral. The study of ideal matrices was initiated in the 1960s by Alfred Lehman and Ray Fulkerson, and continues to this day due to their intimate connections to Integer Programming, Combinatorial Optimization, and Graph Theory. Despite having being studied for about 60 years, several basic questions about them remain open to this day. In this talk, I will discuss some of these questions.

Given an ideal matrix M, consider the set covering linear program min{1Tx: Mx>=1,x>=0} and its dual max{1Ty : MT y <= 1, y>=0}. The notion of idealness certifies that the primal linear program has an integral optimal solution. If the dual had an integral optimal solution, too, it would lead to a beautiful min-max relation, extending many classical ones such as Menger’s and König’s Theorems. Unfortunately, this is not the case, but an old conjecture by Paul Seymour from 1975 predicts that the dual has an optimal solution whose entries are dyadic rationals, i.e. whose entries have an exact floating point representation.

In this talk, I will motivate this conjecture, discuss its potential applications to theory and practice, and discuss how Minor Theory has led to a proof of the conjecture when the dual has optimal value 2. Based on joint work with Gérard Cornuéjols, Bertrand Guenin, and Levent Tunçel.

VIDEOSTREAM