Solving 0/1 Linear Programs in Strongly Polynomial Time with Simplex

Abstract: The Simplex method for solving linear programs (LPs) is one of the most widely used LP solvers due to the fact that it runs very quickly in practice. However, despite its practical efficiency and decades of study, it remains unknown whether or not it provably runs in polynomial time. Other methods for solving LPs are known to run in so-called weakly polynomial time for general LPs, but few such results are known for the Simplex method even for very restrictive and well-known subclasses of LPs.

In this talk, I will discuss the special subclass of 0/1 LPs, i.e., those whose vertex solutions have components in {0,1}. These are an important and widely studied class of LPs which model many problems from combinatorial optimization. Even for this important class, the performance of the Simplex method on these LPs remained unknown for decades. I will discuss the history of their study as it pertains to the Simplex method, and I will present a series of results by Alex Black, Jesús De Loera, Laura Sanità, and myself which culminate in a proof that the Simplex method can solve 0/1 LPs in strongly polynomial time.

Mathematics

Audience: researchers in the topic

PIMS-CORDS SFU Operations Research Seminar