Geometric/Combinatorial problems arising from trying to understand the Simplex Method
Ponente: Jesús de Loera
Institución: UC Davis
Tipo de Evento: Investigación
Institución: UC Davis
Tipo de Evento: Investigación
| Cuándo |
18/11/2022 de 12:00 a 13:00 |
|---|---|
| Dónde | ZOOM ID 882 9372 3602 |
| Agregar evento al calendario |
vCal
iCal
|
The simplex method is one of the most famous and popular algorithms in optimization, itwas 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 theeager 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 manypossible different pivot rules
can there be on a linear Program? Do these questions even make sense? In the second half of my talkwill 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).
