The algorithm

Maintain a current vertex x and its base B, and rewrite the LP in that base (see 07) 1:14:34, 1:15:22:

  1. Halting condition — if c̃_N ≥ 0 (non-negative vector), halt and return x 1:15:22.
  2. Improving step — if some j ∈ N has c̃_j < 0, increment x_j as far as feasibility allows 1:16:34.
  3. The initial vertex comes from the auxiliary LP of topic 04 1:17:32.
flowchart TD
    S[Vertex x + base B] --> R[Rewrite LP in base B → c̃_N]
    R --> Q{c̃_N ≥ 0 ?}
    Q -->|yes| H[Halt: x is optimal]
    Q -->|no| J[Pick j with c̃_j < 0]
    J --> K{x_B strictly positive?}
    K -->|yes| I[Increment x_j until some<br/>basic coordinate hits 0]
    K -->|no, some x_k = 0| P[Pivot: swap k out, j in]
    I --> P
    P --> S

What "increment as far as we can" means

  • x_B depends on x_N: changing a non-basic x_j moves the basic coordinates 1:17:50.
  • Push x_j until some coordinate of x_B hits zero; going further would make it negative 1:18:21, 1:18:45.

The annoying detail: degenerate bases

  • If B had size exactly m without padding, all of x_B is strictly positive, so a strictly positive increment of x_j is always available 1:18:45, 1:19:20, 1:20:26.
  • If B was padded from a smaller support, some k ∈ B already has x_k = 0 and x_j may not be incrementable at all 1:19:48, 1:20:26, 1:21:09.
  • The fix is a pivot: put j into the base and kick out one of the already-zero coordinates k — which by the base↔vertex correspondence means moving to a new vertex 1:19:48, 1:21:09, 1:21:58.

Pivoting rules and cycling

  • Two open choices at every step: which j with c̃_j < 0 enters, and which k leaves 1:20:05, 1:24:46.
  • Choosing carelessly can produce infinite loops: you insert someone, kick someone out, and undo it on the next iteration, forever 1:21:58.
  • Bland's Rule (Bland, Mathematics of Operations Research, 1977) is a greedy pivoting rule provably free of infinite loops; the proof is deferred to the next lecture 1:22:27, 1:22:56.
  • Other loop-free rules exist post-Bland; before Bland the known rules all had infinite loops. In practice people sometimes still use rules known to cycle, on the belief that cycling only arises in contrived cases 1:23:55, 1:24:25.

Next lecture

  • State Bland's Rule, prove Simplex correct, and show that a dual feasible solution matching the primal cost can be read directly off the halting condition — giving strong duality 1:22:56, 1:23:26.