Geometric/Combinatorial problems arising from trying to understand the Simplex Method

The simplex method is one of the most famous and popular algorithms in optimization, it was even named one of the top 10 algorithms of the 20th century! But despite this great success and fame we do not fully understand it. There are a number of natural open questions arising from the analysis of its performance. This talk highlights several fascinating geometric problems we wish to answer. Many open questions will be available for the eager young researcher. I promise!

In the first half I introduce natural geometric-topological structure one can associate to the set of all possible monotone paths of a linear program, I will then use the geometric structure to study. How long can the longest monotone paths on a linear program become? How many different monotone paths can there be on a linear program? We report on two papers, the first joint work with M. Blanchard and Q. Louveaux, and another with C. Athanasiadis and Z. Zhang. A lot of what I present builds up on to the classical Fiber polytope construction of Billera Sturmfels. Next, the engine of any version of the simplex method is a pivot rule that selects the outgoing arc for a current vertex. Pivot rules come in many forms, definitions, and types, but after 80 years we are still ignorant whether there is one that can make the simplex method run in polynomial time. Can we classify all pivot rules? How many possible different pivot rules can there be on a linear Program? Do these questions even make sense? In the second half of my talk will present two recent positive results: For 0/1 polytopes there are explicit pivot rules for which the number of non-degenerate pivots is polynomial and even linear (joint work with A. Black, S. Kafer, L. Sanita). I also present a parametric analysis for all pívot rules. We construct a polytope, the pivot rule polytope, that parametrizes all memoryless pívot rules of a given LP. This is an attempt to get a complete picture of the structure “space of all pivot rules of an LP” (joint work with A. Black, N. Lu ̈tjeharms, and R. Sanyal).

I will start reviewing the Simplex method, you will not need to be an expert to understand. All papers are available at arxiv.org