Worst case behavior of the steepest edge simplex method

Donald Goldfarb, William Y. SitDiscret. Appl. Math 1979 · OpenReview

Abstract

At each nondegenerate iteration of the steepest-edge simplex method one moves from a vertex of the polyhedron, P, of feasible points to an adjacent vertex along an edge that is steepest with respect to the linear objective function ψ. In this paper we show how to construct a sequence of linear programs (Pn,ψn) in n variables for which the number of iterations required by the steepest edge simplex method is 2n−1.
BibTeX
@inproceedings{goldfarb1979worst,
  author = {Donald Goldfarb and William Y. Sit},
  title = {{Worst case behavior of the steepest edge simplex method}},
  booktitle = {Discret. Appl. Math},
  year = {1979},
  url = {https://openreview.net/forum?id=De4Rv4f15B},
}

Loading related content...

Figure