Docs / Simplex

The Simplex method

The Simplex method solves a linear program by walking along the edges of the feasible region, hopping from vertex to vertex so that the objective improves at every step. In lpviz, that walk is drawn right on the polytope you sketched.

A convex polygon whose vertices are visited one at a time by the Simplex method, ending at the optimal vertex.
Phase 1 (dashed) finds a first vertex; Phase 2 pivots along edges to the optimum (black dot).

The idea

A linear objective over a convex polytope always attains its maximum at a vertex (a basic feasible solution). So instead of searching the whole region, Simplex searches only vertices — and only ever moves to an adjacent vertex that improves the objective. Since a polytope has finitely many vertices and the objective strictly improves (with a suitable pivot rule), the method terminates at an optimal vertex, or proves along the way that the LP is unbounded or infeasible.

Invented by George Dantzig in 1947, Simplex remains a workhorse of practical optimization. Its geometry is exactly what lpviz shows: each iterate in the log is a vertex, and consecutive iterates share an edge.

How lpviz sets up the problem

Your drawing defines the LP maximize cᵀx s.t. Ax ≤ b, with one row per edge. Simplex operates on standard form (equality constraints, nonnegative variables), so lpviz converts first:

A basis is a choice of m variables (one per constraint) allowed to be nonzero; solving the basis system yields the vertex it represents. The bit-string in the iteration log is this basis: one 0/1 per standard-form variable, with 1 marking a basic variable.

Two phases

Simplex needs a feasible vertex to start from, and finding one is itself an LP. lpviz uses the classic two-phase method:

  1. Phase 1 adds one artificial variable per constraint and maximizes minus their sum. Artificials measure constraint violation, so driving them to zero lands on a genuine vertex of your region. If the Phase 1 optimum is negative, no feasible point exists and the LP is declared infeasible. Any artificials still lingering in the basis at value zero are pivoted out before Phase 2.
  2. Phase 2 starts from that vertex and optimizes the true objective cᵀx.

Both phases are shown: the Phase 1 iterates are drawn in a different color than the Phase 2 path, and the sidebar log separates the two blocks. On many drawings Phase 1 is short — but tilt or translate your region and you can watch it grow.

The pivot loop

At each iteration, Simplex computes the reduced cost of every nonbasic variable — the rate at which the objective would improve per unit increase of that variable. Then:

  1. Entering variable: by default lpviz uses Bland's rule — pick the lowest-index variable with positive reduced cost (Bland (low) in the Simplex settings). Bland's rule is not the fastest pivot rule, but together with the lowest-index tie-break below it provably never cycles. Two alternatives are available: Dantzig picks the variable with the largest reduced cost — the classic textbook rule, which often needs fewer pivots — and Bland (high) picks the highest index. Neither of those guarantees termination on a degenerate drawing, so lpviz counts consecutive degenerate pivots and switches back to Bland's rule for the rest of the phase when a run of them looks like a cycle. Iterations pivoted under that fallback are marked with a d after their number in the log, like the r that marks PDHG restarts.
  2. Leaving variable (ratio test): increase the entering variable until some basic variable hits zero; the minimum ratio decides which one leaves; ties are broken by index — lowest by default, or highest via the Leaving rule setting. Geometrically, this is sliding along an edge until the next constraint becomes tight.
  3. Unboundedness: if no basic variable ever hits zero, the edge is a ray on which the objective grows forever — the log reports LP is unbounded. You can trigger this by leaving the region open in the objective direction.

Degenerate pivots happen when the minimum ratio is zero: the basis changes but the vertex does not move. In the log you'll see consecutive iterations with identical coordinates but different basis strings — the algorithm is reindexing the same corner before it can leave it. Vertices where more than n constraints meet (easy to create by dragging edges) produce exactly this.

Dual simplex mode

Every LP has a dual: for max cᵀx s.t. Ax ≤ b, the dual is min bᵀy s.t. Aᵀy = c, y ≥ 0 — one dual variable per constraint, and equal optimal values (strong duality). With Dual simplex mode checked, lpviz runs the same two-phase primal algorithm on the dual problem, then maps every dual basis back into your picture: the basic dual variables select which constraints are tight, and the displayed point is the intersection of those constraint lines (complementary slackness in action).

A polygon with the primal simplex path walking its vertices, and a dual simplex path of open circles sliding in along the extension of one constraint line from far outside the region, reaching the same optimal vertex last. primal — walks the vertices, always feasible dual — constraint intersections outside the region
Dual iterates are intersections of constraint lines, drawn here sliding in along the extension of one edge (dashed). They are super-optimal and infeasible until the final one.

The behavior looks completely different from primal simplex. The path hops between intersections of constraint lines that are usually outside the feasible region — "super-optimal" points that satisfy the optimality conditions but not feasibility — and only becomes feasible at the very last step, which is the optimum. The status logic flips accordingly: an infeasible dual means your (nonempty) primal is unbounded, and an unbounded dual means the primal is infeasible.

Reading the log

 Iter        x        y        Obj  basis
    1    -8.00    -5.00   -7.1e+1  10010…
    2     8.00    -4.00    4.4e+1  10001…

Behavior to watch for