Optimization Online


The simplex method and the diameter of a 0-1 polytope

Tomonari Kitahara (kitahara.t.ab***at***m.titech.ac.jp)
Shinji Mizuno (mizuno.s.ab***at***m.titech.ac.jp)

Abstract: We will derive two main results related to the primal simplex method for an LP on a 0-1 polytope. One of the results is that, for any 0-1 polytope and any two vertices of it, there exists an LP instance for which the simplex method finds a path between them, whose length is at most the dimension of the polytope. This proves a well-known result that the diameter of any 0-1 polytope is bounded by its dimension. Next we show that the upper bound obtained by the authors for the number of distinct solutions generated by the simplex method is tight by constructing an LP instance on a 0-1 polytope.

Keywords: Linear programming; the number of solutions; the simplex method; 0-1 polytope.

Category 1: Linear, Cone and Semidefinite Programming

Citation: Technical report, Graduate School of Decision Science and Technology, Tokyo Institute of Technology, 2012.


Entry Submitted: 05/09/2012
Entry Accepted: 05/09/2012
Entry Last Modified: 07/04/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society