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.
Citation
Technical report, Graduate School of Decision Science and Technology, Tokyo Institute of Technology, 2012.