Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

Organizing Committee | Scientific Overview | Speaker List

Application/Registration | Contact Us

Margaret Bayer (University of Kansas, Mathematics)
Jesus De Loera (University of California, Davis (UC Davis), Mathematics)
Antoine Deza (McMaster University)
Gil Kalai (Hebrew University, Institute of Mathematics)
Shanghua Teng (University of Southern California (USC))

Back to Top

Linear programs are the backbone of computation and theory in mathematical optimization. Linear optimization problems involve maximizing or minimizing a linear function over a domain defined by a set of linear equalities and inequalities. The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization. The simplex method can be viewed as a family of combinatorial local search algorithms on the boundary of a convex polyhedron. More precisely, the search is done over a finite graph, the skeleton of the polyhedron, composed of the vertices and edges of the feasible region. The search moves from a vertex of the skeleton to a neighboring one with a better objective value, according to a chosen “pivot rule”. Today, after sixty years of use and despite remarkable progress with competing interior point methods, the simplex method is still widely used and remains important in practice, particularly in combinatorial optimization and integer programming.

However, while the polynomial complexity of interior point methods has been established, we still do not have a complete understanding of the performance of the simplex method, in particular the number of pivots needed to go from a starting vertex to an optimal vertex. In 1957, Hirsch conjectured that the diameter of the skeleton defined by n inequalities in d dimensions is at most n-d. Fifty-three years later this conjecture, this original Hirsch conjecture, remains open. In fact, despite great effort, we still do not know whether there is a polynomial bound on the shortest path between two vertices in the skeleton of a polyhedron. Many authors have tried to approach this variation of the Hirsch conjecture. The best upper bound, due to Kalai and Kleitman, is quasi-polynomial.

The past five years have seen renewed interest and new ideas for these problems. Recent approaches include the smoothed analysis of the simplex method, analogies with interior point methods, explicit constructions and the systematic search for counterexamples through computational tools, and the investigation of combinatorial-topological abstractions of polyhedra. This workshop is devoted to the simplex method and the Hirsch conjecture, bringing together researchers with these various contemporary approaches.

Back to Top

Back to Top

Back to Top

Contact Us:

Institute for Pure and Applied Mathematics (IPAM)
Attn: SM2011
460 Portola Plaza
Los Angeles CA 90095-7121
Phone: 310 825-4755
Fax: 310 825-4756
Email: ipam@ucla.edu
Website: http://www.ipam.ucla.edu/programs/sm2011/

Back to Top