Title: Generating Short Monotone Paths in 0/1 LPs: From Circuits to Simplex
| Speaker: | Sean Kafer |
| Affiliation: | University of Waterloo |
| Zoom: | 945 0789 9910 (passcode: kafer) |
Abstract:
Even after decades of study, it is unknown whether there exists a pivot rule for the Simplex method that always solves an LP with only a polynomial number of pivots. This remains unknown even in the special case of 0/1 LPs - i.e., LPs defined over 0/1 polytopes - a case that includes many extensively studied problems in combinatorial optimization.
In the pursuit of better understanding the behavior of the Simplex method on 0/1 LPs, we study the length of the monotone edge-path generated by following steepest edges, where here we determine steepness by normalizing with the 1-norm instead of the usual 2-norm. We show that this path is of a strongly-polynomial length and that it can be computed in polynomial time. We achieve this by first considering the length of the so-called circuit-path generated by steepest descent circuit steps, where the circuits are a set of augmentation directions that generalize the set of edges. We then show that, at an extreme point solution of a 0/1 LP, a steepest descent circuit step is always equal to a steepest descent edge step, i.e., that these concepts are unified in the setting of 0/1 LPs.
Finally, in light of the fact that these results do not describe the behavior of the steepest edge Simplex pivot rule, we devise an alternate pivot rule for 0/1 LPs which is guaranteed to follow the path generated by steepest edges. That is, we show the existence of a Simplex pivot rule for 0/1 LPs which is guaranteed to require only a polynomial number of non-degenerate pivots. We are able to use similar techniques to propose two variants on the shadow vertex pivot rule for 0/1 LPs which require at most n (the number of variables) and d (the dimension of the polytope itself) non-degenerate pivots, respectively.
Joint work with Jesús De Loera, Laura Sanità, and Alex Black.