 Solution

Encode a vertex of a polytope by three bits: bit $j$ records whether the lower or upper bound of coordinate $j$ is tight. Every choice is possible because $0<\epsilon <1/2$, and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing $x_3$. It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string $110$, switching bit 2 decreases $x_3$, so the rule switches bit 1, leaving facet 2. At $010$, neither of the earlier-coordinate switches improves $x_3$, so the rule finally leaves facet 5. The upper face reverses the direction in which changes of $x_2$ improve $x_3$, and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of $\epsilon$.

Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in $n$ dimensions has $2n$ inequalities and $2^n$ vertices of a polytope. On its lower last-coordinate face, increasing $x_n$ means increasing $x_{n-1}$, and the first $n-1$ coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing $x_n$ means decreasing $x_{n-1}$, and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies $T_n=2T_{n-1}+1$, $T_1=1$, andThe usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed $\epsilon$, the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.

For a lower bound that applies to every pivot choice, use $0\le x_i\le 1$ and maximize ${\sum }_{i=1}^n{x}_i$, starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is $(1,\dots ,1)$. Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least $n$ pivots, and every strictly improving route takes exactly $n$.

For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates byThe transformed linear program still maximizes $y_3$, now with boundsWhen the active facet for coordinate $i$ is freed, the other active equations give $|d{x}_3/d{x}_i|={\epsilon }^{3-i}$. The positive rates per unit $y_i$ are thereforefor $i=1,2,3$, respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate $i$ changes its entering slack by $|d{y}_i|$. Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In $n$ dimensions set $y_i={\epsilon }^{2(n-i)}{x}_i$; the rates ${\epsilon }^{-(n-i)}$ give the same $2^n-1$ pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.