Title: Dyadic Linear Programming
| Speaker: | Ahmad Abdi |
| Affiliation: | London School of Economics |
| Zoom: | Please email Emma Watson |
Abstract:
Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:
Given a linear program, determine whether it admits an optimal solution whose entries have an exact floating-point representation.
This question motivates the study of Dyadic Linear Programming, a problem that sits somewhere between Linear Programming and Integer Linear Programming, and benefits surprisingly from both worlds.
In this talk, I will talk about an ongoing project on this topic, and address some of the basic questions. I will also discuss applications and connections to some classical problems in Combinatorial Optimization, including the Cycle Double Cover Conjecture, and the Generalized Berge-Fulkerson Conjecture.
Joint work with Bertrand Guenin, Gérard Cornuéjols, and Levent Tunçel.