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: lpviz uses Bland's rule — pick the lowest-index variable with positive reduced cost. Bland's rule is not the fastest pivot rule, but it provably never cycles, so the visualization can never loop forever on a degenerate drawing.
  2. Leaving variable (ratio test): increase the entering variable until some basic variable hits zero; the minimum ratio decides which one leaves (ties broken again by smallest index). 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).

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