Who Solved the Hirsch Conjecture?

Günter M. Ziegler

2010 Mathematics Subject Classification: 90C05 Keywords and Phrases: Linear programming

1 Warren M. Hirsch, who posed the Hirsch conjecture

In the section “The simplex interpretation of the simplex method” of his 1963 classic “Linear Programming and Extensions”, George Dantzig [5, p. 160] describes “informal empirical observations” that

While the simplex method appears a natural one to try in the ndimensional space of the variables, it might be expected, a priori, to be inefficient as tehre could be considerable wandering on the outside edges of the convex [set] of solutions before an optimal extreme point is reached. This certainly appears to be true when n − m = k is small, (…)

However, empirical experience with thousands of practical problems indicates that the number of iterations is usually close to the number of basic variables in the final set which were not present in the initial set. For an m-equation problem with m different variables in the final basic set, the number of iterations may run anywhere from m as a minimum, to 2m and rarely to 3m. The number is usually less than 3m/2 when there are less than 50 equations and 200 variables (to judge from informal empirical observations). Some believe that on a randomly chosen problem with fixed m, the number of iterations grows in proportion to n.

Thus Dantzig gives a lot of empirical evidence, and speculates about random linear programs, before quoting a conjecture about a worst case:

Warren M. Hirsch (1918–2007) (http://thevillager.com/villager_223/
warrenhirsch.html)

This is reiterated and also phrased geometrically in the problems for the same section [5, p. 168]:

13. (W. M. Hirsch, unsolved.) Does there exist a sequence of m or less pivot operations, each generating a new basic feasible solution (b.f.s.), which starts with some given b.f.s. and ends at some other given b.f.s., where m is the number of equations? Expressed geometrically: In a convex region in n − m dimensional space defined by n halfplanes, is m an upper bound for the minimum-length chain of adjacent vertices joining two given vertices?

This is the “Hirsch conjecture” – a key problem in the modern theory of polyhedra, motivated by linear programming, backed up by a lot of experimental evidence. Dantzig thus gives credit to Warren M. Hirsch, who had gotten his Ph.D. at New York University’s Courant Institute in 1952, was on the faculty there from 1953 to his retirement 1988. We may note, however, that Hirsch has lasting fame also in other parts of science: Obituaries say that he is best known for his work in mathematical epidemiology.

With hindsight, Dantzig’s two renditions of the problem point to many different facets of the later developments. In particular, random linear programs are mentioned – for which good diameter bounds were later proved in celebrated work by Karl Heinz Borgwardt [4]. As the present writer is a geometer at heart, let us translate Dantzig’s geometric version into current terminology (as in [21, Sect. 3.3]):

The Hirsch conjecture:

For n ≥ d ≥ 2, let Δ(d, n) denote the largest possible diameter of the graph of a d-dimensional polyhedron with n facets. Then Δ(d, n) ≤ n − d.

2 A first counterexample

We now know that the Hirsch conjecture – as stated by Dantzig – is false: The credit for this result goes to Victor Klee and David W. Walkup, who in Section 5 of their 1967 Acta paper [15] indeed gave an explicit example of a simple 4-dimensional polyhedron P_{4} with n = 8 facets and 15 vertices whose graph diameter is equal to δ(P_{4}) = 5. Thus, indeed,

Δ(4, 8) = 5,

which disproved the Hirsch conjecture.

Kim & Santos [12, Sect. 3.3] explain nicely how this polyhedron can be derived from a (bounded!) polytope Q_{4} of dimension 4 with 9 facets – found also by Klee & Walkup – that has two vertices x and y of distance 5, by moving the facet that does not meet x or y to infinity by a projective transformation. From much later enumerations by Altshuler, Bokowski & Steinberg [1] we now know that Q_{4} is unique with these properties among the 1142 different simple 4-dimensional polytopes with 9 facets. What a feat to find this object!

However, instead of just celebrating their example and declaring victory, Klee and Walkup mounted a detailed study on a restricted version of the Hirsch conjecture, which considers (bounded) polytopes in place of (possibly unbounded) polyhedra:

The bounded Hirsch conjecture:

For n ≥ d ≥ 2, let Δ_{b}(d, n) denote the largest possible diameter of the graph of a d-dimensional polytope with n facets. Then Δ_{b}(d, n) ≤ n − d.

As a consequence of the Klee–Walkup example, also using projective transformations, Mike Todd observed that the monotone version of the Hirsch conjecture is false even for polytopes: There is a simple 4-dimensional polytope with

Victor L. Klee (1925–2007) (Photo: L. Danzer, Bildarchiv des Mathematischen Forschungsinstituts Oberwolfach)

George Dantzig (1914–2005) (http://lyle.smu.edu/~jlk/personal/
personal.htm)

8 facets, such that from a specified starting vertex and objective function every pivot sequence to the optimum needs at least 5 steps.

3 The Hirsch conjecture, Dantzig figures, and revisits

Published only one year after his classic book, Dantzig [6] presented the following as the first of his “Eight unsolved problems from mathematical programming”:

a. Let C_{n} be an n-dimensional bounded polyhedral convex set defined by 2n distinct faces, n of which determine the extreme point p_{1} and the remaining n of which determine the extreme point p_{2}. Does there always exist a chain of edges joining p_{1} to p_{2} such that the number of edges in the chain is n?

Dantzig did not mention Hirsch in this connection, but he also did not give any references, not even his own book which must just have been published when he compiled the problems. But clearly this is a special case of the Hirsch conjecture, with two restrictions, namely to the case of bounded polytopes with n = 2d facets, and with two antipodal vertices that do not share a facet. This is what Klee and Walkup call a “Dantzig figure.”

Klee and Walkup clarified the situation, by proving that the following three fundamental conjectures on convex polytopes are equivalent:

The Hirsch conjecture for polytopes:

For all d-dimensional bounded polyhedra with n facets, n > d ≥ 2, Δ_{b}(d, n) ≤ n − d.

Dantzig’s bounded d-step conjecture: For all d-dimensional simple polytopes with 2d facets, the distance between any two complementary vertices that don’t share a facet is d, for d ≥ 2.

The nonrevisiting conjecture, by V. Klee and P. Wolfe: From any vertex of a simple convex polytope to any other vertex, there is a path that does not leave a facet and then later come back to it.

Some of these implications are quite obvious: For example, a nonrevisiting path starts on a vertex that lies on (at least) d facets, and in every step it reaches a new facet, so its length clearly cannot be more than n − d. Other implications are harder, and in particular they were not established on a dimension-by-dimension basis (but rather for fixed m = n − d).

The restriction to simple polytopes in all these constructions (that is, ddimensional polytopes such that every vertex lies on exactly d facets) appears at the beginning of the fundamental Klee–Walkup paper. Indeed, right after introduction and preliminaries, Section 2 “Some reductions” starts with the observation

2.1. It is sufficient to consider simple polyhedra and simple polytopes when determining Δ(d, n) and Δ_{b}(d, n).

This is, as we will see, true, easy to eastablish, fundamental – and was quite misleading.

4 Francisco Santos solved the Hirsch conjecture

In May 2010, Francisco Santos from the University of Cantabria in Santander, submitted the following abstract to the upcoming Seattle conference “100 Years in Seattle: the mathematics of Klee and Grünbaum” dedicated to the outstanding geometers Victor Klee (who had passed away in 2007) and Branko Grünbaum (famous for his 1967 book on polytopes [9], which carried a chapter by V. Klee on diameters of polytopes):

Title:  "A counter-example to the Hirsch conjecture"
Author:  Francisco Santos, Universidad de Cantabria
Abstract:  I have been in Seattle only once, in
November 2003, when I visited to give a seminar talk
at U of W. Victor Klee was already retired (he was 78
at that time), but he came to the department.  We had
a nice conversation during which he asked "Why don't
you try to disprove the Hirsch Conjecture"?  Although
I have later found out that he asked the same to many

Francisco “Paco” Santos (*1968)

     people, including all his students, the question and
     the way it was posed made me feel special at that time.
     This talk is the answer to that question.  I will
     describe the construction of a 43-dimensional polytope
     with 86 facets and diameter bigger than 43.  The proof
     is based on a generalization of the d-step theorem of
     Klee and Walkup.

Francisco “Paco” Santos, *1968, was known in the polytopes community as an outstanding geometer, who had previously surprised the experts with constructions such as a 6-dimensional triangulation that does not admit a single “bistellar flip.” Thus, as a preprint of his paper was first circulating among a few experts, and then released on the arXiv [18], there was no doubt that this would be correct. Indeed, the announcement contained only one mistake, which was soon corrected: His visit to Seattle had not been in 2003, but in 2002.

This is not the place to even sketch Santos’ magnificent construction. Let us just say that his starting point is a generalization of Dantzig’s d-step conjecture: Santos calls a spindle a polytope with two vertices x and y such that all facets contains one of them (but not both). If the polytope has dimension d, then it has n ≥ 2d facets. If such a spindle is simple, then n = 2d: This is the case of a Dantzig figure. So the key for Santos’ approach is to not do the reduction to simple polytopes, but to consider spindles that are not simple.

The d-step conjecture for spindles asks for a path of length d between the vertices x and y in any spindle. This happens to exist for d = 3 (exercise for you), and also for d = 4 (not so easy – see Santos et al. [20]). But for d = 5 there is a counterexample, which Santos devised using intuition from a careful

A Santos spindle, from [19]

analysis of the Klee–Walkup example P_{4}, and which he cleverly explained and visualized in 2- and 3-dimensional images. This example can then be lifted, using Klee–Walkup type “wedging” techniques, to yield a counterexample to the d-step conjecture (and hence the Hirsch conjecture), for d = 43:

Δ(43, 86) > 43.

Later “tweaking” and “optimization” yielded counterexamples in lower dimensions, arriving at an explicit example of a 20-dimensional Dantzig figure with 40 facets and 36,425 vertices and graph diameter 21 – proving that

Δ(20, 40) > 21.

See Matschke, Santos & Weibel [16].

5 If there is a short path, there must be a way to find it

If you want to prove the Hirsch conjecture, or at least prove good upper bounds for the diameter of polytopes, one natural approach is to ask for numerical or combinatorial strategies to find short paths.

Indeed, the interest from linear programming certainly is not to only establish the existence of short paths, but to specify pivot rules that find one. Certainly the expectation of Hirsch, Dantzig, and others was that the usual pivot rules used for linear programming (at the time) would not need more than a linear number of steps, which, a fortiori, would establish the existence of “reasonably” short paths.

That hope was seriously damaged by a seminal paper by Victor Klee and George Minty from 1972, with the innocuous title “How good is the simplex algorithm?” [14]. The answer was “It is bad”: Klee and Minty constructed linear programs, certain d-dimensional “deformed cubes,” soon known as the “Klee–Minty cubes”, on which the usual largest coefficient pivot rule would take 2^{d} steps.

Zadeh’s letter to Victor Klee (\begin{matrix}c \\ ◯ \end{matrix}G. M. Ziegler [22], http://www.scilogs.de/

wblogs/blog/mathematik-im-alltag/)

But would a different pivot rule be better? Linear? Establish the Hirsch conjecture? The Klee–Minty breakthrough started a sequence of papers that constructed variants of the “deformed cube” construction, on which the classical pivot rules for lineare programming, one by one, were shown to be exponential in a worst case – an industry that Manfred Padberg criticised as worstcasitis in [17, p. 70]. (The geometric background was formalized as “deformed products” in Amenta & Ziegler [2].)

Two pivot rules remained, and defied all attacks, namely

• random pivots, and

• minimizing revisits.

The latter idea, perhaps inspired by Robert Frost’s famous “road less travelled by,” was proposed by the mathematician (and now controversial businessman) Norman Zadeh, who had once offered $ 1000 for a proof or disproof that his “least entered rule” was polynomial:

This prize was finally in January 2011 collected, at IPAM, by a doctoral student, Oliver Friedman from Munich, who had used game-theoretic methods to construct linear programs on which Zadeh’s rule is exponential [7].

At the same time, Friedmann, Hansen & Zwick also showed that the “random pivot” rule is exponential [8], thus for the time being destroying all hopes for any “reasonable” pivot rule for the simplex algorithm with polynomial worstcase behaviour.

Oliver Friedmann (Photo: E. Kim)

6 The Hirsch conjecture is not solved

Clearly, Hirsch and Dantzig were interested in an upper bound on the maximal number of pivots for the simplex algorithm. Santos’ example shows that the upper bound Δ_{b}(d, n) ≤ n−d does not hold in general, but all the lower bounds we have right now are quite weak: From glueing techniques applied to Santos’ examples we get linear lower bounds of the type

Δ_{b}(d, n) ≥ \frac{21}{20}(n − d)

for very large n and d, while the best available upper bounds by Kalai & Kleitman [11] resp. by Barnette and Larman [3]

Δ(d, n) ≤ n^{log_{2} 2d}  and  Δ(d, n) ≤ \frac{1}{12}2^{d}n

are very mildly sub-exponential, resp. linear in n but exponential in d (and hence, for example, exponential for the case n = 2d of the d-step conjecture).

The huge gap between these is striking. And if we interpret Hirsch’s question as asking for a good (linear?) upper bound for the worst-case behaviour of the Hirsch conjecture, then all we can say as of now is: We honestly don’t know.

Much more could be said – but we refer the readers to Santos’ paper [18], to the surveys by Klee & Kleinschmidt [13] and Kim & Santos [12], and to Gil Kalai’s blog [10] instead.

References

[1] Amos Altshuler, Jürgen Bokowski, and Leon Steinberg. The classification of simplicial 3-spheres with nine vertices into polytopes and nonpolytopes. Discrete Math., 31:115–124, 1980.

[2] Nina Amenta and Günter M. Ziegler. Deformed products and maximal shadows. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry (South Hadley, MA, 1996), volume 223 of Contemporary Mathematics, pages 57–90, Providence RI, 1998. Amer. Math. Soc.

[3] David W. Barnette. An upper bound for the diameter of a polytope. Discrete Math., 10:9–13, 1974.

[4] Karl Heinz Borgwardt. The Simplex Method. A Probabilistic Analysis, volume 1 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 1987.

[5] George B. Dantzig. Linear Programming and Extensions. Princeton University Press, Princeton, 1963. Reprint 1998.

[6] George B. Dantzig. Eight unsolved problems from mathematical programming. Bulletin Amer. Math. Soc., 70:499–500, 1964.

[7] Oliver Friedmann. A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In In Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization, IPCO’11, New York, NY, USA, 2011.

[8] Oliver Friedmann, Thomas Hansen, and Uri Zwick. Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. In In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC’11, San Jose, CA, USA, 2011.

[9] Branko Grünbaum. Convex Polytopes, volume 221 of Graduate Texts in Math. Springer-Verlag, New York, 2003. Second edition prepared by V. Kaibel, V. Klee and G. M. Ziegler (original edition: Interscience, London 1967).

[10] Gil Kalai. Combinatorics and more. Blog, http://gilkalai.wordpress.

com/.

[11] Gil Kalai and Daniel J. Kleitman. A quasi-polynomial bound for the diameter of graphs of polyhedra. Bulletin Amer. Math. Soc., 26:315–316, 1992.

[12] Edward D. Kim and Francisco Santos. An update on the Hirsch conjecture. Jahresbericht der DMV, 112:73–98, 2010.

[13] Victor Klee and Peter Kleinschmidt. The d-step conjecture and its relatives. Math. Operations Research, 12:718–755, 1987.

[14] Victor Klee and George J. Minty. How good is the simplex algorithm? In O. Shisha, editor, Inequalitites, III, pages 159–175. Academic Press, New York, 1972.

[15] Victor Klee and David W. Walkup. The d-step conjecture for polyhedra of dimension d < 6. Acta Math., 117:53–78, 1967.

[16] Benjamin Matschke, Francisco Santos, and Christophe Weibel. The width of 5-dimensional prismatoids. Preprint, February 2012, 28 pages, http://

arxiv.org/abs/1202.4701.

[17] Manfred Padberg. Linear Optimization and Extensions, volume 12 of Algorithms and Combinatorics. Springer-Verlag, Heidelberg, second edition, 1999.

[18] Francisco Santos. A counterexample to the Hirsch conjecture. Preprint

http://arxiv.org/abs/1006.2814, 27 pages, June 2010; Annals of

Math. 176 (2012), to appear (published online Nov. 2011).

[19] Francisco Santos. Über ein Gegenbeispiel zur Hirsch-Vermutung. Mitteilungen der DMV, 18:214–221, 2010. Translated by J. Pfeifle.

[20] Francisco Santos, Tamon Stephen, and Hugh Thomas. Embedding a pair of graphs in a surface, and the width of 4-dimensional prismatoids. Discrete Comput. Geometry, 47:569–576, 2012.

[21] Günter M. Ziegler. Lectures on Polytopes, volume 152 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. Revised edition, 1998; seventh updated printing 2007.

[22] Günter M. Ziegler. Typical and extremal linear programs. In M. Grötschel, editor, The Sharpest Cut: The Impact of Manfred Padberg and His Work, volume 4 of MPS-SIAM Series on Optimization, chapter 14, pages 217– 230. SIAM, Philadelphia, PA, 2004.

Günter M. Ziegler Inst. Mathematics Freie Universität Berlin Arnimallee 2 14195 Berlin Germany

                 ziegler@math.fu-berlin.de

86

Documenta Mathematica · Extra Volume ISMP (2012)