The simplex method and the diameter of a 0-1 polytope
Tomonari Kitahara (kitahara.t.abm.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
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|