A class of linear programs for which the Shadow Vertex Simplex Algorithm requires an exponential number of steps.

The Simplex Method due to Dantzig is one of the most important algorithms to
solve linear optimization problems, see Schrijver [3, Chapter 11]. It walks
along ascending edges from an arbitrary vertex of the polyhedron described by a
set of linear inequalities to an optimal vertex. At each sub-optimal vertex one
needs to make a decision on how to proceed: Which one among the better neighbors
should be chosen? An algorithm to solve this problem is called a *pivoting
strategy*. One major open question is whether there exists a pivoting
strategy which makes the Simplex Method a polynomial time algorithm, even in the
worst case. Up to now, for each of the many pivoting strategies suggested in the
literature there seems to be a class of counter-examples, which are bad. That is
to say, the Simplex Method with the pivoting strategy in question has
super-polynomial running time on the respective input. Strangely enough, most of
the inequality systems which turn out to be difficult for the Simplex method are
combinatorially equivalent to the cube.

In this model, we are focussing on the Shadow Vertex Pivoting Strategy. The
first construction of bad examples for this algorithm is due to Goldfarb. Here
we use the description as a *deformed product* due to Amenta and
Ziegler.

For e<1/2 and g<=1/4e we obtain a linear program:

max x_{d}

0 <= x _{1}<= 1 e x _{1}<= x _{2}<= 1 - e x _{1}e x _{k}- e g x_{k-1}<= x _{k+1}<= 1 - e x _{k}+ e g x_{k-1}, where 2 <= k < d.

The set of admissible solutions is a d-dimensional combinatorial cube, the
*Goldfarb d-cube*. Projecting the Goldfarb d-cube onto the plane spanned by
the last two unit vectors leaves all the vertices visible. This yields a
2^{d}-gon such that the linear objective function x_{d} on the
cube induces an ascending path through all the vertices of the projection.

Substituting g=0 in the above inequality description of the cubes, we obtain the Klee-Minty cubes, see Schrijver [3, 11.4]. Substituting e=0 and g=0 yields the usual 0/1-cube.

Model produced with: polymake 1.3.2

Keywords
| cube; Simplex method; Shadow Vertex Pivoting Strategy | |

MSC-2000 Classification
| 90C05 (52B10, 68U05) | |

Zentralblatt No.
| 01682991 |

- Nina Amenta and Günter M. Ziegler:
*Deformed products and maximal shadows of polytopes*, Contemporary Math.**233**(1999), 57-90. - Donald Goldfarb:
*On the complexity of the simplex algorithm*, in Advances in optimization and numerical analysis, Proc. 6th Workshop on Optimization and Numerical Analysis, Oaxaca, Mexico, January 1992, Kluwer (1994), 25-38. - Alexander Schrijver: Theory of Linear and Integer Programming, Wiley-Interscience (1986).

- Master File: Goldfarb3.poly
- Applet File: Goldfarb3.jvx
- Preview: Goldfarb3.gif

Submitted: Sun Sep 10 07:10:24 CET 2000.

Accepted: Mon Nov 20 17:06:57 CET 2000.

Technische Universität Berlin

Fachbereich Mathematik, MA 7-1

Straße des 17. Juni 136

10623 Berlin, Germany

joswig@math.tu-berlin.de

http://www.math.tu-berlin.de/~joswig