Linear programs (LPs) are, without any doubt, at the core of both the theory and the practice of modern applied and computational Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes).

George Dantzig’s Simplex method is one of the most famous algorithms to solve LPs. But despite its key importance, many fundamental questions about the simplex method remain open. In this lecture, I will review some things we still do not know about the simplex method’s performance and I will discuss a simple variation of simplex method that has helped us gain insight about the behavior of pivot rules.

This lecture welcomes students and non-experts and it is based in papers joint work with Raymond Hemmecke, Jon Lee, Laura Sanita, & Sean Kafer.

Jesus De Loera is a Professor of Mathematics at the University of California, Davis. He is an expert in the field of Discrete Mathematics, but his research encompasses a diverse set of topics including his work in (pure) Convex Geometry, Algebraic Combinatorics, and Combinatorial Commutative Algebra, as well as his (applied) work in Combinatorial Optimization and Algorithms. In addition to more than 80 published research papers, he has co-written two graduate level textbooks: “ Triangulations: Structures for Algorithms and Applications” (Springer, with J. Rambau and F. Santos) and “ Algebraic and Geometric Ideas in the Theory of Discrete Optimization” (SIAM, with R. Hemmecke and M. Koeppe). The first being a treatise about combinatorics of triangulations of polytopes and the second an introduction to the state of the art in algebraic-geometric algorithms in optimization.