|
27th Seminar of the POC group
15-15 Dec 2023 Paris (France)
|
|
Location The seminar will take place at the La Defense campus of ESSEC Business School. Address: CNIT building, ESSEC Executive Education, Pl. de la Défense (92800, Puteaux) Room: Amphi 103 About the seminar The POC group (Polyhèdres et Optimization Combinatoire) is a research group transversal to various French research laboratories (LAMSADE, LIMOS, LIPN, ESSEC, etc.) which welcomes academics but also colleagues from companies (such as Orange and EDF) brought together by the interest towards the polyhedral (both theoretical and algorithmic) aspects of combinatorial optimization problems. The group organizes two seminars per year (SPOC) on topics complementary to the group's themes, as well as JPOC and ISCO. The topic of this edition of SPOC is "Recent progress and interesting facts about the Simplex Algorithm" and it will include the talks of some distinguished experts in the field such as:
Even after more than 50 years, the Simplex algorithm is a topic of great interest and discovery. Our speakers will share their insights, recent findings, and perspectives on this algorithm. The day before the seminar, on the afternoon of Thursday, December 14th, from 2pm to 6pm, we are pleased to announce an “outside the walls” meeting of the POC group, also at the ESSEC campus at La Défense. This half-day is dedicated to presentations by PhD students and young doctors about different topics of combinatorial optimization, in particular those topics related to the POC group themes. This opportunity is designed to present the students current work, as well as their research topics, in an informal context. For all those who want to be present on this occasion, please send an email to spoc27@sciencesconf.org with the title of your presentation. Registration The seminar is free of charge but registration is mandatory. Follow this link to register. Program 9:00am -- 9:30am Reception with coffe and viennoiseries! 9:30am -- 10:30am Interior point methods are not worse than Simplex 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. 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 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 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 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. Sponsors
|
| Online user: 1 | Privacy |
|
