The Simplex Method: Theory, Complexity, and Applications
FU Berlin, June 26-27, 2025
Invited speakers Program Registration Abstracts ContactInvited speakers
Program
Thursday (June 26)
Room: A3 SR 024- 12:30 - 13:45 Lunch
- 14:00 - 14:10 Introduction
- 14:15 - 15:00 Talk
- 15:05 - 15:50 Talk
- 15:50 - 16:20 Break (with Tea / Coffee / Cake)
- 16:25 - 17:10 Talk
- 17:10 - 18:00 Discussion
- 18:00 - 21:00 Dinner (self-organized)
Friday (June 27)
Room: A3 SR 019- 10:00 - 10:45 Talk
- 10:50 - 11:35 Talk
- 11:40 - 12:25 Talk
- 12:30 - 13:45 Lunch
- 13:45 - 17:00 Discussion
- June 26, 14:00 - 18:00 : A3 SR 024
- June 27, 10:00 - 13:00 : A3 SR 019
Abstracts
-
Eleon Bach: Optimal smoothed analysis of the simplex method
Smoothed analysis is a method for analysing the performance of algorithms, used especially for those algorithms whose running time in practice is significantly better than what can be proven through worst-case analysis and which have significant structure such that average case analysis remains inconclusive. Given an arbitrary linear program with $d$ variables and $n$ inequality constraints, we prove that there exists a simplex method whose smoothed complexity is upper bounded by $O(\sigma^{-1/2} d^{11/4} \log(n)^{7/4})$ pivot steps. Furthermore, we prove a matching high-probability lower bound of $\Omega( \sigma^{-1/2} d^{1/2}\ln(4/\sigma)^{-1/4})$ on the combinatorial diameter of the feasible polyhedron after smoothing, on instances using $n = \lfloor (4/\sigma)^d \rfloor$ inequality constraints. This lower bound indicates that our algorithm has optimal noise dependence among all simplex methods, up to polylogarithmic factors.
In this talk we will discuss the algorithmic improvements that we used for the above new upper bound. This is joint work with Sophie Huiberts. -
Alex Black: NP-Hardness of Finding Short Paths on Polytopes
The simplex method traces a path of in the graph of a polytope. The length of a path is a lower bound for a run-time for simplex method, which motivated the well-studied and wide-open polynomial Hirsch conjecture asking whether a polynomial length path always exists between any pair of vertices of a polytope. However, even if such a path always existed, the simplex method would need to be able to find it in polynomial time. Furthermore, a recent result of Kaibel and Kukharenko shows that one can reduce in strongly polynomial time to linear programs in which a linear length path always exists. Both these observations motivate the following broad question: Can one find short paths on polytopes in polynomial time? I will survey several results of this type including a result from joint work with Christian Nöbel and Raphael Steiner, and I will try to provide some pointers to what one can do next. -
Sophie Huiberts: Lessons from Paula Harris
Paula Harris was a mathematician at British Petroleum. Together with 3 others, she was responsible for LP solving in the company. In light of that task, she developed a number of algorithmic techniques and insights into the functioning of the simplex method. This talk will be about the person, as well as about some of her insights that have made their way into all serious LP software. -
Matthew Maat: Generalized worst-case instances for the simplex algorithm using games on graphs
Markov decision processes (MDPs), longest shortest path problems (LSPs) and parity games (PGs) can be seen as infinite duration games played on the vertices of a graph. One thing that these games have in common is that they can be solved by some form of policy iteration (also called strategy iteration): starting with an arbitrary strategy, this algorithm keeps improving the strategy until it is optimal. It has long been known that for MDPs performing policy iteration is equivalent to performing the simplex algorithm on some LP. In the past, this has led to some lower bounds on running time for some pivot rules for the simplex algorithm, for example for random-edge and for Zadeh’s rule. It turns out that a direct connection between strategy improvement for LSP and PGs and the simplex algorithm is also possible.
The aim of this research is to use these techniques to prove more general statements about pivot rules. While it could be very difficult to show statements about all pivot rules, we propose some models for pivot rules in which we can prove statements. Specifically, we identify a number of classes of pivot rules, for which we show that for each pivot rule from the class, there exists a sequence of LPs, such that the pivot rule takes a superpolynomial number of steps on the LPs associated to these games. These LPs are constructed via games on graphs: this is done by relating pivot rule properties to properties of strategy improvement, and then showing that strategy improvement must take a superpolynomial number of steps to reach the optimum. Based on joint work with Nils Mosis, Georg Loho and Yann Disser -
Nils Mosis: An unconditional lower bound for the active-set method on the hypercube
The existence of a polynomial-time pivot rule for the simplex method is a fundamental open question in optimization. While many super-polynomial lower bounds exist for individual or very restricted classes of pivot rules, there currently is little hope for an unconditional lower bound that addresses all pivot rules. We approach this question by considering the active-set method as a natural generalization of the simplex method to non-linear objectives. This generalization allows us to prove the first unconditional lower bound for all pivot rules. More precisely, we construct a multivariate polynomial of degree linear in the number of dimensions such that the active-set method started in the origin visits all vertices of the hypercube. We hope that our framework serves as a starting point for a new angle of approach to understanding the complexity of the simplex method.