Le séminaire aura lieu sur le campus de La Défense de l'ESSEC Business School.

Adresse : Bâtiment CNIT, ESSEC Executive Education, Pl. de la Défense (92800, Puteaux)

Room: Amphi 103

Link to Google maps

Instructions détaillées pour accéder au lieu

Le groupe POC (Polyhèdres et Optimisation Combinatoire) est un groupe de recherche transversal à différents laboratoires de recherche français (LAMSADE, LIMOS, LIPN, ESSEC, etc.) qui accueille des universitaires mais aussi des collègues d'entreprises (comme Orange et EDF) réunis par le intérêt pour les aspects polyédriques (à la fois théoriques et algorithmiques) des problèmes d'optimisation combinatoire. Le groupe organise deux séminaires par an (SPOC) sur des sujets complémentaires aux thématiques du groupe, ainsi que JPOC et ISCO.

Le sujet de cette édition du SPOC est « Recent progress and interesting facts about the Simplex Algorithm » et comprendra les exposés de certains experts éminents dans le domaine tels que :

• Xavier Allamigeon (INRIA / CMAP, École Polytechnique, France)
• Daniel Dadush (CWI Institute, Netherlands)
• Sophie Huiberts (CNRS / LIMOS, France)
• Quentin Louveaux (Institut Montefiore, Université de Liège, Belgium)

Même après plus de 50 ans, l’algorithme du Simplexe reste un sujet de grand intérêt. Nos conférenciers partageront leurs idées, leurs découvertes récentes et leurs perspectives sur cet algorithme.

Le séminaire est gratuit mais l'inscription est obligatoire. Suivez ce lien pour vous inscrire.

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.