Title: Bridging the gap between Linear and Integer Programming
| Speaker: | Bertrand Guenin |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: Informally, an Integer Program is obtained from a Linear Program by adding the condition that some variables be restricted to be integer. What kind of other restrictions lead to interesting classes of optimization problems? One such class of problems is obtained by restricting the variables in a Linear Program to be dyadic rationals, i.e. rationals where the denominator is a power of two. These problems borrow features from both Linear Programming and Integer Programming. Notably, they can be solved in polynomial time, but optimal solutions may have large support.
There is a rich body of work investigating which Linear Programs are guaranteed to have integer solutions. We study which Linear Programs are guaranteed to have dyadic solutions. This is motivated by a 1975 conjecture by Paul Seymour on ideal clutters, that has implications for matchings in graphs, and for directed cuts in digraphs. We also show that this theory has some surprising implications for combinatorial optimization as it leads to a geometric characterization of Total Dual Integrality for non-degenerate instances.