ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pass

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A degenerate six-pivot cycle prevented by Bland's rule

Example

Consider the exact minimization problem with $x_{1}, \dots, x_{7} \geq 0$ and $\frac{1}{2} x_{1} - \frac{11}{2} x_{2} - \frac{5}{2} x_{3} + 9 x_{4} + x_{5} = 0, \frac{1}{2} x_{1} - \frac{3}{2} x_{2} - \frac{1}{2} x_{3} + x_{4} + x_{6} = 0, x_{1} + x_{7} = 1,$ minimizing $- 10 x_{1} + 57 x_{2} + 9 x_{3} + 24 x_{4}$ . Start from basis $(5, 6, 7)$ ; exact reduced costs and ratio tests below show that the most-negative reduced-cost rule cycles, while Bland's least-index entering and leaving rules terminate.

Facts & Assumptions

Given: The exact seven-variable LP in the Example and the two pivot rules being compared.

[F1]

Primal revised simplex with Bland's rule: On exact full-row-rank standard-form data at a primal-feasible basis, choose the least index $j \notin B$ with ${\overset{ˉ}{c}}_{j} < 0$ and solve $A_{B} d = a_{j}$ . Among minimum-ratio rows, leave the basic variable of least index.

[F2]

Primal revised-simplex pivot identities and certificates: At a primal-feasible basis with nonbasic entering index $j$ and ${\overset{ˉ}{c}}_{j} < 0$ , put $d = A_{B}^{- 1} a_{j}$ . If some $d_{i} > 0$ , the step $θ = \min_{d_{i} > 0} (x_{B_{i}} / d_{i})$ is finite and nonnegative, every minimizing row gives a valid pivot, the new basic vector is feasible, and the objective change is $θ {\overset{ˉ}{c}}_{j} \leq 0$ . A primal-feasible basis with all nonbasic reduced costs nonnegative is optimal.

[F3]

Bland-rule finite termination and optimal-basis existence: Under its exact-arithmetic, finite-standard-form, full-row-rank hypotheses, the primal run terminates after finitely many pivots at an optimal basis or returns a feasible ray of strictly negative cost.

Verification

1.1givenF1F2algebra

Initially $B = (5, 6, 7)$ , $x_{B} = (0, 0, 1)$ , and the only negative reduced cost is ${\overset{ˉ}{c}}_{1} = - 10$ . For entering $x_{1}$ , $d = (1 / 2, 1 / 2, 1)$ gives ratios $(0, 0, 1)$ for $(x_{5}, x_{6}, x_{7})$ , so the least-index leaving tie is $x_{5}$ and $θ = 0$ . The next basis is $(1, 6, 7)$ .

2.1F1F2step 1.1algebra

At $B = (1, 6, 7)$ the negative reduced costs are ${\overset{ˉ}{c}}_{2} = - 53$ and ${\overset{ˉ}{c}}_{3} = - 41$ . Both rules choose $x_{2}$ . Its direction is $d = (- 11, 4, 11)$ ; the eligible ratios for $(x_{6}, x_{7})$ are $(0, 1 / 11)$ , so $x_{6}$ leaves at $θ = 0$ and the basis becomes $(1, 2, 7)$ .

3.1F1F2step 2.1algebra

At $B = (1, 2, 7)$ the negative reduced cost is ${\overset{ˉ}{c}}_{3} = - 29 / 2$ . Its direction is $d = (1 / 2, 1 / 2, - 1 / 2)$ , so the eligible ratios for $(x_{1}, x_{2})$ are $(0, 0)$ ; the least-index leaving variable is $x_{1}$ , giving $θ = 0$ and basis $(3, 2, 7)$ .

4.1F1F2step 3.1algebra

At $B = (3, 2, 7)$ the negative reduced costs are ${\overset{ˉ}{c}}_{4} = - 18$ and ${\overset{ˉ}{c}}_{5} = - 15$ , so both rules choose $x_{4}$ . Its direction is $d = (- 8, 2, 0)$ ; the only eligible ratio is $0$ for $x_{2}$ , which leaves and gives basis $(3, 4, 7)$ .

5.1F1F2step 4.1algebra

At $B = (3, 4, 7)$ the only negative reduced cost is ${\overset{ˉ}{c}}_{5} = - 21 / 2$ . Its direction is $d = (1 / 2, 1 / 4, 0)$ ; the eligible ratios for $(x_{3}, x_{4})$ are $(0, 0)$ , so $x_{3}$ leaves at $θ = 0$ and the basis becomes $(5, 4, 7)$ . Thus the first five pivots agree under both rules.

6.1F2step 1.1step 5.1algebra

At $B = (5, 4, 7)$ , ${\overset{ˉ}{c}}_{1} = - 22$ and ${\overset{ˉ}{c}}_{6} = - 24$ . The most-negative rule chooses $x_{6}$ , whose direction $d = (- 9, 1, 0)$ has only the eligible ratio $0$ for $x_{4}$ . The pivot leaves $x_{4}$ and returns to $(5, 6, 7)$ with the same basic vector and objective $0$ ; repeating the deterministic choices cycles.

6.2F1F2step 5.1algebra

At the same basis $(5, 4, 7)$ , Bland chooses $x_{1}$ because $1 < 6$ . Its direction is $d = (- 4, 1 / 2, 1)$ ; the eligible ratios for $(x_{4}, x_{7})$ are $(0, 1)$ , so $x_{4}$ leaves and the next basis is $(5, 1, 7)$ , still with $θ = 0$ .

7.1F1F2step 6.2algebra

At $B = (5, 1, 7)$ the only negative reduced cost is ${\overset{ˉ}{c}}_{3} = - 1$ . Its direction is $d = (- 2, - 1, 1)$ , so only $x_{7}$ is eligible and its ratio is $1$ . The pivot gives basis $(5, 1, 3)$ and basic values $(2, 1, 1)$ , hence the full vector is $x = (1, 0, 1, 0, 2, 0, 0)$ .

8.1F1F2F3step 7.1algebra∎

At this final basis the objective is $- 10 + 9 = - 1$ and the remaining reduced costs for $(x_{2}, x_{4}, x_{6}, x_{7})$ are $(30, 42, 18, 1)$ , all nonnegative. The basic vector is feasible, so [F2] proves it optimal; [F3] also confirms finite termination. The six-pivot most-negative cycle and Bland's terminating branch are thereby checked with exact rational pivots.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Robert G. Bland, New Finite Pivoting Rules for the Simplex Method, pp. 103–105 (standard reference, not scraped)
Dimitris Bertsimas and John N. Tsitsiklis, Introduction to Linear Optimization, §3.4 and Example 3.6 (standard reference, not scraped)
Michel Goemans, MIT 18.310 Lecture Notes: Linear Programming, §2.4 (standard reference, not scraped)