Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 38 ยท Simplex Method

Two-Phase Simplex and Big-M

Handle >= and = constraints in simplex with artificial variables: build a Phase 1 feasibility search, then Phase 2, compare with Big-M, and test against linprog.

Our simplex solver started from the origin, which is feasible only when every constraint is a . x <= b with b >= 0. Real models have requirements (>=) and equalities (=), for which the origin is infeasible. We need a way to find a starting vertex. The classic answer is to add temporary artificial variables and to drive them out of the solution. There are two standard ways: the two-phase method and the Big-M method.

Artificial variables

Suppose a constraint is x1 + x2 >= 4. Subtracting a surplus variable gives x1 + x2 - s = 4, but then setting x = 0 makes s = -4, which is not allowed. So we add an artificial variable a >= 0:

TEXT
x1 + x2 - s + a = 4

Now a = 4 (with x1 = x2 = s = 0) gives a starting basic feasible solution for the augmented problem. The artificial variable has no real meaning: a solution to the original problem is exactly a solution of the augmented one where all artificials are zero.

The rule for building the starting basis, after making every right-hand side non-negative (multiply a row by -1 if b < 0, flipping its sense):

Original row Add Starting basic variable
<= slack +s the slack
>= surplus -s and artificial +a the artificial
= artificial +a the artificial

Phase 1: find a feasible vertex

Phase 1 solves an auxiliary LP: minimize the sum of artificial variables (the total amount of "cheating"). Start from the artificial basis. When the optimum is reached:

  • Optimum = 0: all artificials are zero, and the current basis is a feasible vertex of the original problem. Continue to Phase 2.
  • Optimum > 0: some cheating is unavoidable, so the original problem is infeasible.

Phase 2: optimize the real objective

Remove (forbid) the artificial columns, restore the real objective row and price it out against the current basis, and continue simplex as usual from the feasible vertex Phase 1 found.

Python A two-phase simplex solver

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 solver returns the optimum (3, 1) with cost 9, corner of the two >= lines: x + y = 4 and x + 3y = 6 meet at (3, 1). Neither the origin nor any single slack basis would have been feasible, but Phase 1 found a starting vertex automatically.

Testing the solver, including infeasible and equality cases

Python Compare with linprog on random mixed problems

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 the two disagree on a handful of numerically delicate random instances you will want a tolerance study, but the large majority match: optimal values, infeasible and unbounded verdicts alike.

The Big-M method

The Big-M method merges both phases into one by charging artificial variables a huge penalty M in the objective. For a minimization, the objective becomes

TEXT
minimize  c . x + M * (a1 + a2 + ...)

With a large enough M, the optimizer would rather set the artificials to zero than pay M per unit. If artificials are still positive at the optimum, the original problem is infeasible. In a tableau, you must first price out the artificial variables so the objective row has zeros under the basic columns.

The method is easy to explain and implement but has a practical weakness: M must be large enough to make cheating unattractive but small enough not to destroy floating-point accuracy. With M = 10^9 and coefficients around 1, round-off can swamp the real data. Production solvers prefer two-phase methods, or avoid artificial variables entirely (the dual simplex method and "crash" starting bases).

Python Big-M with a too-small and a large M

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.

When M is too small (0.5 or 1) the optimizer prefers to cheat and leaves artificials positive, giving a "solution" that violates the original constraints. Once M is big enough (10 here), the artificials vanish and the true optimum appears. The right size depends on the data, which is exactly why the two-phase method is safer.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which constraint types need an artificial variable?

    A <= row can start with its slack, but >= and = rows have no ready-made basic variable.
  2. 2. Phase 1 ends with a positive optimum (sum of artificials > 0). What does this mean?

    Some cheating is unavoidable, so no point satisfies all original constraints.
  3. 3. In Phase 2, why are artificial columns forbidden from entering?

    Artificials are not part of the original problem; allowing them back could silently violate constraints.
  4. 4. What is the main weakness of the Big-M method?

    Too small an M gives wrong answers; too large an M causes round-off trouble.

Summary

  • >= and = rows need artificial variables to create a starting basis.
  • Two-phase simplex: Phase 1 minimizes the sum of artificials (positive optimum means infeasible), Phase 2 optimizes the real objective.
  • Big-M combines both with a penalty M on artificials but is numerically delicate.
  • After Phase 1, drive remaining zero-valued artificials out of the basis before Phase 2.
  • Always test a custom solver against linprog on many random instances.

Next: The Dual Problem