The longest monotone path on a polyhedron in LP
The simplex method for a linear programming problem finds an op timal solution by generating a sequence of vertices on a polyhedron (or a sequence of basic solutions of the feasible region) such that the object function value is minimized. Then the sequence of vertices could be seen as a monotone path on the network consisted of the vertices and the edges of the polyhedron. If the problem is non-degenerate, the number of iterations of the simplex method is equal to the length of the path. Otherwise, the number could be bigger than the length. In this talk, we will discuss lower and upper bounds for the number of iterations of the simplex method and the length of the monotone path. We also show simple linear programming instances for which the simplex method requires an exponential number of iterations, but the length of the path is very small.