Usted está aquí: Inicio / Actividades / Coloquio Queretano / Actividades - Coloquio Queretano / Problems Abiertos que Salen de Entender el Algoritmo SIMPLEX

Problems Abiertos que Salen de Entender el Algoritmo SIMPLEX

Ponente: Jesus De Loera
Institución: UC Davis
Tipo de Evento: Investigación

Cuándo 18/11/2022
de 12:00 a 13:00
Dónde https://unam.zoom.us/j/9794432722?pwd=NHFsZGNkc1ZuUzQzTWRwbWI5djM0Zz09
Agregar evento al calendario vCal
iCal
The simplex method is one of the most famous and popular algorithms in optimization; it was 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 the eager young researcher.
I promise!

In the first half, I introduce a 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 of whether there is one that
can make the simplex method run in polynomial time. Can we classify all pivot rules? How many possible different pivot rules
can there be on a linear Program? Do these questions even make sense? In the second half of my talk will 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).