On the Geometry of the Simplex Method and Other Simplex-Like Algorithms

Linear programs (LPs) and their associated convex polyhedra are, without any doubt, at the core of both the theory and the practice  of Mathematical Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). Despite their key importance, many simple easy-to-state mathematical properties of LP and their polyhedra remain unknown.  My talk presents two new results:

1) Perhaps the most famous geometric-combinatorial challenge is on the simplex method is to determine a worst-case upper bound for the graph diameter of polyhedra. Although a lot of progress has been made, today even for the most elementary textbook linear programs we remain ignorant as to what the exact diameter upper bounds are. In this talk, I will discuss this  geometric problem and present the key ideas for proving that the diameter of graphs of all network-flow polytopes satisfy the Hirsch linear bound. This is joint work with S. Borgwardt and E. Finhold.

2) In the study of the simplex method one is interested on the number of pivots needed to reach the optimum, Klee-Minty cubes provide negative news. But, what if we allow more  pivot directions or augmentations to the usual simplex method allowing even to go through the interior? Can one bound those steps? I will discuss why using the right pivot rule with generalized pivots gives several surprising results; E.g., one can prove polynomially many augmentation steps are possible if best augmenting steps along all possible directions are allowed. These results extend to integer optimization and there are strongly polynomial-time pivoting-like algorithms for the solution of special ILPs. This is joint work with Raymond Hemmecke and Jon Lee.