The Big-M and Two-Phase Methods
The simplex method of Chapter 8 got a free start because "\(\le\)" constraints hand over ready-made slack variables. But the moment a problem has a "\(\ge\)" requirement or an "\(=\)" balance, that gift disappears — the origin is no longer feasible and there is no obvious basis to begin from. The fix is a clever accounting trick: introduce temporary artificial variables to fabricate a starting basis, then force them back out. This chapter shows the two standard ways to do it — the Big-M penalty and the two-phase route.
- Why "\(\ge\)" and "\(=\)" constraints leave the simplex method with no obvious starting basis.
- How surplus and artificial variables differ, and why artificials must be driven to zero.
- The Big-M method: penalize artificials with a huge cost so the simplex expels them.
- The two-phase method: first reach feasibility, then optimize the real objective.
- How to detect infeasibility from a leftover artificial or a positive Phase-I objective.
- When to prefer one method over the other in practice.
The Starting-Basis Problem
With only "\(\le\)" constraints, each slack variable appears in exactly one equation with coefficient \(+1\), giving an instant identity basis and a feasible start at the origin. A "\(\ge\)" constraint spoils this. Writing \(\mathbf{a}^{\mathsf T}x \ge b\) in equality form needs a surplus variable subtracted: \(\mathbf{a}^{\mathsf T}x - s = b\). Its coefficient is \(-1\), so setting the real variables to zero gives \(s = -b < 0\) — infeasible. There is no ready basis. An "\(=\)" constraint is worse still: it has no slack or surplus at all.
Artificial Variables
The remedy is to manufacture a basis. To each "\(\ge\)" or "\(=\)" constraint we add a non-negative artificial variable with coefficient \(+1\). It has no physical meaning — it exists only to give a starting identity basis:
| Constraint | Equality form | Variables added |
|---|---|---|
| \(\mathbf{a}^{\mathsf T}x \le b\) | \(\mathbf{a}^{\mathsf T}x + s = b\) | slack \(s\) (also serves as basis) |
| \(\mathbf{a}^{\mathsf T}x \ge b\) | \(\mathbf{a}^{\mathsf T}x - s + a = b\) | surplus \(s\) + artificial \(a\) |
| \(\mathbf{a}^{\mathsf T}x = b\) | \(\mathbf{a}^{\mathsf T}x + a = b\) | artificial \(a\) only |
An artificial variable at a positive value means a constraint is being satisfied only with the help of a fictitious quantity — the point is not truly feasible. So the whole game is to drive every artificial to zero. The Big-M and two-phase methods are simply two ways of forcing that.
The Big-M Method
The Big-M method attaches a colossal penalty to any positive artificial. For a minimization we add \(+M \sum_i a_i\) to the objective, where \(M\) is a symbolic number larger than any other cost; for a maximization we add \(-M \sum_i a_i\). The simplex method, chasing the best objective, expels the artificials as fast as possible.
Because the artificials start in the basis, the objective row must be made consistent before iterating — we "price out" the artificials by row operations so their reduced costs read zero. The penalty \(M\) then propagates into the reduced costs of the real variables, making the columns that reduce the artificials look most attractive. As each artificial leaves the basis it never returns, and once all are gone the method proceeds exactly like ordinary simplex on the real objective.
Big-M: A Worked Setup
Consider the problem with two "\(\ge\)" requirements:
Add a surplus and an artificial to each: \(x_1 + x_2 - s_1 + a_1 = 4\) and \(x_1 + 2x_2 - s_2 + a_2 = 6\), with objective \(z = 2x_1 + 3x_2 + M a_1 + M a_2\). The artificials \(a_1 = 4,\ a_2 = 6\) form the starting basis. Pricing them out gives the net-evaluation (\(c_j - z_j\)) row below:
| Basis | x₁ | x₂ | s₁ | s₂ | a₁ | a₂ | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|
| a₁ | 1 | 1 | −1 | 0 | 1 | 0 | 4 | 4 |
| a₂ | 1 | 2 | 0 | −1 | 0 | 1 | 6 | 3 ← |
| cⱼ−zⱼ | 2−2M | 3−3M | M | M | 0 | 0 | −10M |
For a minimization we bring in the most negative \(c_j - z_j\). Since \(M\) is huge, \(3 - 3M\) is more negative than \(2 - 2M\), so \(x_2\) enters. The ratios \(4/1 = 4\) and \(6/2 = 3\) send \(a_2\) out (pivot element \(2\)). Continuing, \(x_1\) enters and \(a_1\) leaves; both artificials are then gone and the tableau optimizes to
The penalty did its job silently: by the time the algorithm reports optimality, the artificials have been squeezed out of the basis and \(z\) contains no leftover \(M\). If any \(M\) remained in the objective, that would be the tell-tale sign of infeasibility (Section 9-7).
The Two-Phase Method
The two-phase method reaches the same place without the awkward symbol \(M\). It separates the two jobs — becoming feasible, then becoming optimal — into consecutive phases.
Phase I ignores the real objective and simply minimizes the total artificiality \(w = \sum a_i\). If it reaches \(w = 0\), every artificial is zero and we have a genuine basic feasible solution. Phase II then discards the artificial columns and runs ordinary simplex from that feasible basis, using the real objective \(z\).
Two-Phase: A Worked Setup
Take the same example. Phase I replaces the objective with \(w = a_1 + a_2\) and minimizes it from the artificial basis \(a_1 = 4,\ a_2 = 6\) (so \(w = 10\) initially). Pricing out the artificials gives the Phase-I net-evaluation row:
| Basis | x₁ | x₂ | s₁ | s₂ | a₁ | a₂ | RHS | Ratio |
|---|---|---|---|---|---|---|---|---|
| a₁ | 1 | 1 | −1 | 0 | 1 | 0 | 4 | 4 |
| a₂ | 1 | 2 | 0 | −1 | 0 | 1 | 6 | 3 ← |
| cⱼ−zⱼ (w) | −2 | −3 | 1 | 1 | 0 | 0 | −10 |
Notice how much cleaner this is: no \(M\), just ordinary numbers. The most negative entry \(-3\) brings \(x_2\) in and \(a_2\) out; a further pivot brings \(x_1\) in and \(a_1\) out, driving \(w\) to \(0\). Phase I ends at a feasible basic solution. We then delete the \(a_1, a_2\) columns, restore \(z = 2x_1 + 3x_2\), and run Phase II, which arrives at the same optimum \((2, 2)\) with \(z^\star = 10\) — identical to the Big-M result, as it must be.
| Big-M | Two-Phase | |
|---|---|---|
| Passes | One (single objective with penalty) | Two (feasibility, then optimality) |
| Uses the symbol \(M\)? | Yes — carried through every row | No |
| Numerical behaviour | Large \(M\) can cause rounding error | Clean; preferred on computers |
| Infeasibility signal | Artificial stays basic (\(M\) remains in \(z\)) | Phase-I minimum \(w > 0\) |
Detecting Infeasibility
Artificial variables do more than start the algorithm — they also diagnose an impossible problem. If the constraints genuinely contradict one another, no amount of pivoting can drive the artificials to zero, and each method flags it clearly.
In the Big-M method, if the algorithm terminates with an artificial still basic at a positive value (an \(M\) lingering in the objective), the original LP has no feasible solution. In the two-phase method, if Phase I cannot reduce \(w\) below a positive number, the artificials cannot all be zeroed — again, infeasible. Either way, the model must be reconsidered before any optimization is meaningful.
Worked Examples
Problem. State the variables to add to each constraint: (a) \(2x_1 + x_2 \le 8\), (b) \(x_1 + x_2 \ge 5\), (c) \(3x_1 - x_2 = 6\).
Solution. (a) A slack: \(2x_1 + x_2 + s_1 = 8\) — the slack also serves as the starting basic variable. (b) A surplus and an artificial: \(x_1 + x_2 - s_2 + a_1 = 5\). (c) An artificial only: \(3x_1 - x_2 + a_2 = 6\). Only (b) and (c) require artificials.
Problem. For \(\min\ z = 5x_1 + 4x_2\) with artificials \(a_1, a_2\), write the penalized objective.
Solution. Since it is a minimization, add a large positive penalty on each artificial:
For a maximization the sign flips to \(-M a_1 - M a_2\), so any positive artificial is heavily punished either way.
Problem. With basis \(a_1, a_2\) (cost \(M\)) and the \(x_1\) column \([1,1]^{\mathsf T}\), find the reduced cost of \(x_1\) in a Big-M minimization where \(c_{x_1} = 2\).
Solution. \(z_{x_1} = \sum c_B \cdot (\text{column}) = M(1) + M(1) = 2M\), so the reduced cost is \(c_j - z_j = 2 - 2M\). Being large and negative, it makes \(x_1\) an attractive entering candidate — exactly the pull that expels the artificials.
Problem. For a problem with artificials \(a_1, a_2, a_3\), state the Phase-I objective and the condition to proceed to Phase II.
Solution. Phase I minimizes \(w = a_1 + a_2 + a_3\) (all real variables have zero cost in Phase I). If the minimum is \(w = 0\), every artificial is zero, feasibility is achieved, and we drop the artificial columns and start Phase II with the real objective. If \(\min w > 0\), the problem is infeasible.
Problem. A Big-M run ends with all reduced costs optimal but \(a_1 = 2\) still basic. What do you conclude?
Solution. A positive artificial in the final basis means feasibility was never reached — the original constraints have no common solution. Equivalently, in a two-phase solve the Phase-I minimum would be \(w = 2 > 0\). The LP is infeasible and the model needs revision.
Problem. You are coding an LP solver and worry about rounding error. Which method do you implement, and why?
Solution. The two-phase method. The Big-M method carries a very large number \(M\) through every arithmetic step, which can swamp the genuine cost coefficients in finite-precision arithmetic and cause rounding errors. The two-phase method uses only ordinary numbers, so it is numerically cleaner and is the standard choice in software; Big-M remains popular for compact hand calculations.
Chapter Summary
"\(\ge\)" and "\(=\)" constraints leave no ready slack basis — the origin is infeasible.
Add \(+1\) artificial variables for a starting basis; they must be driven to zero.
Penalize artificials with \(\pm M\) so the simplex expels them in one pass.
Phase I minimizes \(w = \sum a_i\) to feasibility; Phase II optimizes the real \(z\).
Leftover positive artificial (Big-M) or \(\min w > 0\) (two-phase) ⇒ no feasible solution.
Two-phase is numerically cleaner; Big-M is compact for hand work.
Problems
Set up the artificials carefully, then carry out both methods where asked. Difficulty rises down the list.
- State the variables to add to each: (a) \(x_1 + x_2 \ge 10\), (b) \(4x_1 - x_2 = 8\), (c) \(x_1 + 3x_2 \le 12\).
- Write the Big-M objective for \(\max\ z = 3x_1 + 2x_2\) with artificials \(a_1, a_2\).
- Set up the initial Big-M tableau for \(\min\ z = x_1 + x_2\) s.t. \(x_1 + x_2 \ge 2,\ x_1 + 2x_2 = 3,\ x \ge 0\).
- For Problem 3, compute the initial reduced costs of \(x_1\) and \(x_2\) in terms of \(M\), and identify the entering variable.
- Solve \(\min\ z = 2x_1 + 3x_2\) s.t. \(x_1 + x_2 \ge 4,\ x_1 + 2x_2 \ge 6,\ x \ge 0\) by the Big-M method (all tableaus).
- Solve the same problem by the two-phase method and confirm the answer.
- Write the Phase-I objective for a problem with artificials \(a_1, a_2\) and explain the stopping rule.
- Explain why a surplus variable alone cannot provide a starting basis for a "\(\ge\)" constraint.
- A Big-M solution ends with \(a_2 = 3\) basic. What does this tell you, and what is the corresponding two-phase signal?
- Contrast the Big-M and two-phase methods on number of passes, use of \(M\), and numerical stability.
- Show that the two constraints \(x_1 + x_2 \ge 6\) and \(x_1 + x_2 \le 3\) make the LP infeasible, and describe how each method reveals it.
- A blending problem requires \(\min\ z = 4x_1 + 3x_2\) s.t. \(2x_1 + x_2 \ge 10,\ x_1 + 3x_2 \ge 15,\ x \ge 0\). Solve by the two-phase method, showing the Phase-I tableau, the transition, and the Phase-II optimum; then state which constraints are binding at the optimum.