Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 38 ยท Simplex Method

Implementing Simplex in Python

Write your own simplex solver in Python with NumPy: a tableau function with entering rules, ratio test, status codes and duals, tested against SciPy on random LPs.

Now that you can run simplex by hand, let us package it as a reusable Python function. Writing it yourself is the best way to understand what linprog does internally. Our solver handles the standard "easy" form, maximize c . x subject to A x <= b, x >= 0, b >= 0, so the slack basis is a ready-made starting vertex. The next lessons lift the restriction on b.

Design of the solver

A good small implementation has five parts:

  1. Build the tableau [A | I | b] with an objective row [-c | 0 | 0].
  2. Select the entering column (a rule: Dantzig, or Bland's for anti-cycling).
  3. Ratio test, picking the leaving row; report unbounded if none.
  4. Pivot using row operations.
  5. Extract the solution, objective value, status and dual values.

We also track the path of vertices visited, which is a nice way to see the algorithm move.

Python A simplex function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The path shows the simplex route through the polygon: it starts at the origin and visits improving vertices until the optimum. Under Dantzig's rule the route can differ from Bland's rule: both reach the same final vertex, but possibly by a different number of steps.

Testing against SciPy

A solver is not trustworthy until you test it. A good test generates many random LPs with a known-bounded, known-feasible structure (positive A, positive b give a bounded region that contains the origin) and compares optimal values with linprog.

Python Random tests against linprog

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both rules solve all 200 problems correctly. Dantzig's rule usually needs fewer pivots; Bland's rule is slower on average but is guaranteed never to cycle (next lesson).

Entering-variable rules

The choice of entering variable changes the path, not the answer:

Rule Picks Pros and cons
Dantzig (largest coefficient) Most negative reduced cost Simple, fast in practice; can cycle in rare degenerate cases
Bland Smallest index with a negative reduced cost Never cycles; often slow
Steepest edge Largest improvement per unit of distance Fewest pivots; costlier per step; used by good solvers (dual steepest-edge in HiGHS)
Greatest improvement Tries every candidate's full ratio test Expensive per step
Random Random candidate Useful in theory (randomized simplex)

What a production solver does differently

Our tableau stores everything and updates (m+1)(n+m+1) entries per pivot. Industrial solvers use the revised simplex method: keep only the basis matrix B (via an LU factorization), compute the dual prices y = c_B Bโปยน, price out the non-basic columns to find the entering variable, and solve one linear system for the entering column. This exploits sparsity (real constraint matrices are over 99% zeros), reduces memory and arithmetic, and enables presolve, scaling and crash starting bases. The logic, however, is exactly the loop you wrote.

Python Revised simplex: prices from the basis

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If any reduced profit were positive, that column would enter the basis, exactly like a negative entry in the tableau's objective row.

Common implementation bugs

  • Floating-point comparisons. Compare with a tolerance (tol = 1e-9), never == 0.
  • Ratio test with non-positive entries. Only rows with a strictly positive entry take part. Dividing by zero or negatives yields wrong pivots.
  • Updating the objective row. It must be pivoted like every other row.
  • Forgetting to return unbounded. An infinite loop or an inf ratio produces nonsense.
  • Infinite loops. Always have an iteration limit and consider Bland's rule.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does our simplex_max function require b >= 0?

    With b >= 0 the slacks are non-negative, so the origin is feasible. Otherwise a Phase 1 search is needed.
  2. 2. Which rule guarantees that simplex never cycles?

    Bland's rule (smallest index for entering and leaving) is a proven anti-cycling rule.
  3. 3. In the revised simplex method, what is the dual price vector y?

    y solves B^T y = c_B; reduced profits are c - yA.
  4. 4. Why test your solver against linprog?

    Randomized comparison against a trusted solver is a cheap, powerful regression test.

Summary

  • A tableau simplex fits in about 30 lines: build, choose entering, ratio test, pivot, repeat.
  • Return a status: optimal, unbounded or iteration limit; always use tolerances.
  • Entering rules change the path (Dantzig fast, Bland safe, steepest edge strong).
  • Test on random LPs against linprog.
  • Production solvers use the revised simplex with sparse LU factorization and presolve.

Next: Degeneracy, Cycling and Bland's Rule