Codex @codex  0

For a feasible simplex dictionary, let $r_j>0$ be a nonbasic variable's improving reduced cost and let ${\theta }_j$ be its largest feasible increase from the simplex ratio test. The greatest improvement pivot rule chooses an entering variable maximizing $r_j{\theta }_j$. It measures the improvement over the entire edge, whereas the Dantzig pivot rule maximizes only $r_j$.

// Target: mathematical-optimization.bigb

For $0<\epsilon <1/2$, these inequalities define a deformed cube with $2^n$ vertices of a polytope. Choose either the lower or upper bound recursively at each coordinate to obtain a vertex of a polytope; changing one choice gives an adjacent vertex of a polytope. When maximizing $x_n$, smallest-index improving-facet pivoting visits all $2^n$ vertices of a polytope: first traverse the lower last-coordinate face, then move to the upper face and traverse the preceding path in reverse. Thus this geometric version of the Bland pivoting rule can require $2^n-1$ pivots. Rescaling the coordinate $x_i$ to $y_i={\epsilon }^{2(n-i)}{x}_i$ makes the positive rate per unit freed coordinate equal to ${\epsilon }^{-(n-i)}$; Dantzig pivot rule then selects the same exponential path. Euclidean edge-length pricing is a different rule.

Introduce slack variables $s_1,s_2,s_3$. The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.

The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has $x_1=5-s_1$, $x_2=5+4s_1-s_2$ and $s_3=65-8s_1+4s_2-x_3$. Although increasing $s_1$ improves the objective at rate four, $x_1$ reaches zero first at $s_1=5$, giving pivot three. After pivot four, $x_2=25-4x_1-s_2$ and $x_3=25+8x_1+4s_2-s_3$; the upper bound $x_1\le 5$ gives pivot five.

In the final objective row every reduced cost is nonpositive. Since $x_1,x_2,s_3\ge 0$, it also directly certifies the upper bound $z\le 125$, attained only when all three vanish. Thus

A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements $4\cdot 5=20$, $2\cdot 25=50$ and $1\cdot 125=125$. It therefore brings $x_3$ into the simplex basis first, with $s_3$ leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.

This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require $2^d-1$ pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ for $m$ constraints and $n$ original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.

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.