Close Menu

Variations on a Theme by G. Dantzig: Revisiting the Principles of the Simplex Algorithm


Feb 4, 2019 - 1:50pm to 2:55pm


Rettaliata Engineering Center, Room 104


Jesus A. De Loera
Department of Mathematics, University of California at Davis


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). Fast algorithms are indispensable.

George Dantzig's Simplex method is one of the most famous algorithms to solve LPs and SIAM even elected it as one of the top 10 most influential algorithms of the 20th Century. But despite its key importance, many simple easy-to-state mathematical properties of the Simplex method and its geometry remain unknown. The geometry of the simplex method is a topic in the convex-combinatorial geometry of polyhedra. Perhaps the most famous geometric-combinatorial challenge is to determine a worst-case upper bound for the graph diameter of polyhedra.

In this talk, I will look at how abstractions of simplex method provide useful insight into the properties of this famous algorithm. The first type of abstraction is to remove coordinates entirely and is related to combinatorial topology, the second is related to generalizing the pivoting moves. This survey lecture includes joint work with Steve Klee, Raymond Hemmecke, and Jon Lee.



Event Type: 

Department of Applied Mathematics - Colloquia