9:00am -- 9:30am
Reception with coffe and viennoiseries!
9:30am -- 10:30am
Interior point methods are not worse than Simplex
Daniel Dadush, CWI Institute, Netherlands
Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.
The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths.
Time permitting, I will briefly discuss how this work was subsequently applied to solve all linear programs with a most 2 variables per per inequality in strongly polynomial time.
This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).
10:30am -- 11:00am
Coffee break
11:00am -- 12:00am
Monotone paths in polyhedra and the greatest improvement rule
Quentin Louveaux, Institut Montefiore, Université de Liège, Belgium
Motivated by the problem of bounding the number of iterations of the simplex algorithm, we investigate the possible lengths of monotone paths followed inside polyhedra (oriented by the objective function). We consider both the shortest and the longest monotone paths and estimate the monotone diameter and height of polyhedra. Our analysis applies to combinatorial cubes, transportation polytopes, matroid polytopes, matching polytopes, shortest-path polytopes, and the TSP, among others. For some of these polytopes, we also analyze the number of pivots generated by the greatest improvement rule of the simplex algorithm.
This is based on a joint work with Moise Blanchard, Jesus De Loera and Victor Kani.
12:00am -- 14:00am
Lunch break
14:00am -- 15:00am
No self-concordant barrier interior point method is strongly polynomial
Xavier Allamigeon, INRIA / CMAP, École Polytechnique, France
A long-standing question has been to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative. In this talk, I will show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, for convex optimization problems, the image under the logarithmic map of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. This curve, called the tropical central path, has a strong connection with the simplex method in the case of LP. I will provide an explicit linear program that falls in the same class as the Klee-Minty counterexample, i.e., a combinatorial n-cube for which interior-point methods require at least 2^n-1 iterations.
This is a joint work with Stéphane Gaubert and Nicolas Vandame (Inria and Ecole Polytechnique).
15:00am -- 15:30am
Coffee break
15:30am -- 16:30am
Open problems about the simplex method
Sophie Huiberts, CNRS / LIMOS, France
The simplex method is perhaps the most important algorithm for solving linear programming problems in practice. However, we do not understand why this algorithm is so efficient; it takes exponential time in the theoretical worst case but only linear time in practice. The talk will start with some social context and women's history. Then I will introduce the state-of-the-art theoretical models for explaining the simplex method's performance. Finally, we will discuss in what ways the state-of-the-art fails to be a proper scientific theory and what needs to happen before we can hope to achieve such a thing.
