Simplex Algorithm

Build a clear mental model of simplex as a structured walk on an LP’s vertices, not a blind search. Learn what a pivot really updates, why feasibility is preserved, what breaks in edge cases, and how to choose variants and alternatives in practice.

Linear programs (LPs) look like they should require searching infinitely many points, yet simplex often solves them by visiting a small number of corners. The trick is that the best solution, when it exists, lives at a vertex of the feasible polytope, so simplex turns optimization into navigation. Each step is not a guess. It is a controlled move that keeps constraints satisfied while improving the objective, until improvement is impossible or the model itself is telling you something is wrong.

Take a look at how an objective’s level sets interact with the feasible region.

That picture is the whole game. Simplex does not roam the interior. It rides the boundary from vertex to vertex, always along an edge that is allowed by the constraints.

The objects simplex actually manipulates

An LP only becomes simplex-friendly after it is in standard form, typically written as maximize $c^Tx$ subject to $Ax=b$, $x\ge 0$. Equalities and nonnegativity are not cosmetic. They let you describe a corner using a small, discrete choice.

That choice is a basis. Pick $m$ linearly independent columns of $A$ (when there are $m$ equality constraints). Set the remaining variables to zero, solve $A_Bx_B=b$, and you get a basic feasible solution (BFS) if $x_B\ge 0$. Geometrically, that BFS is a vertex. Algebraically, it is a partition of variables into two roles.

• Basic variables: the $m$ variables currently solving $A_Bx_B=b$.
• Nonbasic variables: the rest, fixed at 0 for this corner.
• Basis matrix $A_B$: the columns that define the current corner.
• Feasibility: $x_B=A_B^{-1}b\ge 0$, the condition that makes the corner legal.

Explore how switching which variables are basic changes the corner you are standing on.

Once you see bases as the state, simplex becomes less mysterious. A simplex step is just replacing one basis column with another, then recomputing the implied BFS.

One pivot, end to end

A simplex pivot is the single move that changes the basis. It is also where most confusion hides, because one step uses both objective information and feasibility constraints in a precise way.

A standard primal simplex step, starting from a feasible BFS, is:

1. Choose an entering variable with a direction that improves the objective.
2. Move in that direction until some basic variable hits 0.
3. Declare that variable the leaving variable and update the basis.

The objective signal comes from reduced costs, the coefficients that tell you how the objective changes if you increase a nonbasic variable from 0 while keeping feasibility. For a maximization problem, a positive reduced cost means the objective can improve by letting that variable enter.

Feasibility is protected by the ratio test. Increasing the entering variable changes the basic variables along a direction $d=A_B^{-1}a_j$. Any component of $d$ that is positive will shrink some basic variable, so you limit the step to keep all basics nonnegative. The first one to hit 0 leaves.

Try a pivot choice and watch how reduced costs and the ratio test cooperate.

Two gates
Reduced costs decide whether improvement exists. The ratio test decides how far you can move without breaking $x\ge 0$.

If no nonbasic variable has the right reduced-cost sign, you are optimal for primal feasibility. If the ratio test has no bound, the LP is unbounded in that improving direction.

Tableaux, dictionaries, and why pivots stay feasible

The geometric view says you traverse edges of a polytope. The algebraic view says you maintain a system of equations that always expresses basic variables in terms of nonbasic ones.

Dictionary form

In dictionary form, each basic variable is written as

$$x_B=b'-Dx_N$$

and the objective is

$$z=z_0+\bar c^Tx_N.$$

Here $b'$ and $D$ are what you get after multiplying by $A_B^{-1}$. This is why feasibility is easy to check. If $b'\ge 0$ and $x_N=0$, then $x_B=b'$ is feasible.

A pivot is just solving one row for the entering variable and substituting it into the other rows and the objective. You are not changing the feasible set. You are changing which variables are treated as free to vary and which are computed.

Tableau intuition without the mystique

A tableau packages the same substitutions into a compact array so you can do row operations. The key invariant is that the tableau continues to represent the same constraint equations, just rewritten. Row operations preserve equivalence, and the pivot specifically re-expresses the system so the new basis variables appear with an identity matrix again.

If the ratio test was applied correctly, the new $b'$ remains nonnegative, so the new BFS is feasible by construction. That is the entire reason simplex can walk corners without falling outside the polytope.

When simplex behaves badly

Simplex is a clean idea on paper, but LPs have edge cases where naive pivot rules lead to stalling, looping, or misleading numerical signals. These are not rare in large, sparse models.

• Degeneracy: a BFS where at least one basic variable is 0. Pivots can change the basis without improving the objective.
• Cycling: returning to a previously visited basis, possible under degeneracy with unlucky pivot choices.
• Unboundedness: an improving direction exists and the ratio test never blocks it.
• Infeasibility: no point satisfies all constraints, so there is no BFS to walk among.
• Numerical issues: near-singular bases and floating-point tolerances make feasibility and reduced costs ambiguous.

Explore how symptoms connect to causes and standard fixes.

Stall signal
If the objective does not change for many pivots, suspect degeneracy first, not a bug in reduced costs.

Anti-cycling pivot rules (like Bland’s) trade speed for guarantees. Practical solvers also lean heavily on tolerances and refactorization to keep $A_B^{-1}$ behavior stable.

Getting started with Phase I and Big-M

If your model is not already in a form with an obvious feasible BFS, you need a strategy to find a starting corner. This is the job of Phase I–Phase II simplex, or the alternative big-M construction.

Phase I introduces artificial variables to create an easy-to-find feasible basis, then minimizes their sum to drive them to zero. If the minimum is not zero, the original LP is infeasible. Phase II then optimizes the original objective starting from the feasible basis Phase I found.

Big-M folds the idea into a single objective by adding a large penalty $M$ on artificial variables. It can work, but it makes scaling and numerical conditioning fragile. The constant $M$ is not just big. It becomes part of the geometry the solver sees.

Compare the two approaches and when each tends to bite.

A useful habit is to treat Phase I as a diagnostic tool. If Phase I struggles numerically, the original model is often poorly scaled or nearly inconsistent, and Phase II performance will mirror that.

Simplex variants you will actually use

Most modern solvers do not use a classroom tableau for large problems. They use variants that preserve the simplex logic while changing what is computed explicitly.

Revised simplex

Revised simplex keeps the basis idea but avoids storing and updating the full tableau. It works with $A_B$ and solves linear systems to get $A_B^{-1}b$ and reduced costs. This is the default for large sparse LPs because memory and time are dominated by factorizing $A_B$, not by row operations.

Dual simplex

Dual simplex flips the stance. It maintains dual feasibility and fixes primal infeasibility through pivots. It shines when you have a good basis but your right-hand side changes. Common in re-optimization and in branch-and-bound nodes for mixed-integer linear programs.

Primal–dual intuition

Primal simplex searches vertices of the primal feasible polytope. Dual simplex searches vertices of the dual feasible polytope, while keeping the other side consistent enough to make progress. Thinking in terms of which feasibility you can maintain cheaply is often the right way to pick a variant.

Describe your LP situation and see which variant fits best.

Choosing simplex or interior-point in practice

Simplex and interior-point methods both solve LPs well, but they feel different because they exploit different structure.

Simplex is compelling when:

• You need a warm start and expect many related solves. Basis reuse can be extremely effective.
• You care about sensitivity analysis. Shadow prices and reduced costs come naturally from a basis.
• The optimal solution is sparse and you want an extreme point solution explicitly.

Interior-point methods are compelling when:

• The problem is huge and well-scaled, and you want predictable polynomial-time behavior in practice.
• You can tolerate an interior solution that is later rounded to a vertex if needed.
• The constraint matrix has structure that makes large linear solves efficient.

Sparsity matters either way, but in different places. Simplex performance often hinges on how fill-in grows in $A_B$ factorizations across pivots. Interior-point performance hinges on repeated solves of related KKT systems and how well they condition.

The most practical rule is to think about change. If your LP is part of a pipeline where constraints or bounds update repeatedly, simplex with warm starts or dual simplex often wins. If you solve one massive instance once, interior-point can be the safer first try.