Reading Group Talk - Sean Kafer

Title: Generating Short Monotone Paths in 0/1 LPs: From Circuits to Simplex

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.