On the Simplex method for 0/1 polytopes
The Simplex method is one of the most popular algorithms for solving linear programs, but despite decades of study, it is still not known whether there exists a pivot rule that guarantees it will always reach an optimal solution with a polynomial number of pivots. In fact, a polynomial pivot rule is not even known for linear programs over 0/1 polytopes (0/1-LPs), despite the fact that the diameter of a 0/1 polytope satisfies the Hirsch bound.
This talk will focus on the behavior of the Simplex method for 0/1-LPs, and discuss pivot rules that are guaranteed to require only a polynomial number of non-degenerate pivots.
Joint work with: Alexander Black, Jesus De Loera, Sean Kafer.
Online