On Polyhedra Parametrizing ALL pivot rules for the Simplex Method

Abstract: The simplex method is one of the most famous and popular algorithms in optimization. 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 and types, but after 80 years we are still ignorant whether there is one that can make the simplex method run in polynomial time. This talk is about the polyhedral combinatorics of the simplex method. I 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. Its construction is a generalization of the Fiber polytope construction of Billera Sturmfels. 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. Lutjeharms, and R. Sanyal). No prior knowledge of the simplex method will be assume, I will only assume the audience loves polytopes.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic

Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456