IPAM Workshop – Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?


Workshop at IPAM: January 18 – 21, 2011

Here is the link to the IPAM conference


Scientific Overview


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. 


Confirmed Speakers



Nina Amenta (University of California, Davis (UC Davis))
David Bremner (University of New Brunswick)
Friedrich Eisenbrand (École Polytechnique Fédérale de Lausanne (EPFL))
Komei Fukuda (ETH Zürich)
Fred Holt (University of Washington)
Edward Kim (Technische Universiteit te Delft)
Nimrod Meggido (Stanford University)
Jim Renegar (Cornell University)
Francisco Santos (University of Cantabria)
Tamás Terlaky (Lehigh University)
Santosh Vempala (Georgia Institute of Technology)
Yinuy Ye (Stanford University)
Günter Ziegler (Technische Universität Berlin)
Yuriy Zischenko (University of Calgary)

This entry was posted in Combinatorics, Computer Science and Optimization, Conferences, Convex polytopes. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s