Exercise 3.26 (The big-$M$ method)

Consider the variant of the big- M method in which M is treated as an undetermined large parameter. Prove the following.

(a)
If the simplex method terminates with a solution (x,y) for which y = 0, then x is an optimal solution to the original problem.
(b)
If the simplex method terminates with a solution (x,y) for which y≠0, then the original problem is infeasible.
(c)
If the simplex method terminates with an indication that the optimal cost in the auxiliary problem is −∞, show that the original problem is either infeasible or its optimal cost is −∞. Hint: When the simplex method terminates, it has discovered a feasible direction d = (dx,dy) of cost decrease. Show that dy = 0.
(d)
Provide examples to show that both alternatives in part (c) are possible.

Answers

We define the original and the auxiliary big-M optimization problems as follows:

minimize  c′x subject to Ax= b x ≥0 minimize  c′x + M∑ i=1myi subject to  Ax + y = b (x,y) ≥0.

Proof.

(a)
If the simplex method terminates with a solution (x,y) for which y = 0, then x is an optimal solution to the original problem.
Suppose for the sake of contradiction that the component x ∈ ℜn of the optimal solution of the big-M problem (x,0) ∈ ℜn+m does not constitute for an optimal solution of the original problem. In other words, there exists a feasible solution z ∈ ℜn such that c′z < c′x. Obviously, the point (z,0) ∈ ℜn+m is a feasible solution for the big-M problem as well. But then the objective function gives us c′z + M0∑ i=1my i < c′x + M0∑ i=1my i

- a contradiction to the fact that (x,0) is an optimal solution for the big-M problem.

(b)
If the simplex method terminates with a solution (x,y) for which y≠0, then the original problem is infeasible.
Suppose for the sake of contradiction that the big-M method terminates with a solution (x,y) ∈ ℜn+m for which y≠0, whereas the original problem is feasible with some optimal solution z ∈ ℜn. Consider (z,0) ∈ ℜn+m; obviously, this point is feasible for the big-M method. But we then obtain c′z + M0 < c′x + M∑ i=1my i

for M > 0 large enough. But this means that the simplex method will not terminate at (x,y) - a contradiction.

(c)
If the simplex method terminates with an indication that the optimal cost in the auxiliary problem is −∞, show that the original problem is either infeasible or its optimal cost is −∞.

Suppose for the sake of contradiction that the big-M method terminates at a point (x,y) ∈ ℜn+m with the optimal cost of −∞, whereas the original problem has an optimal solution z ∈ ℜn. Whenever the big-M simplex method does not result in a finite cost, it instead discovers a feasible direction d = (dx,dy) ∈ ℜn+m of cost decrease

c′d x + M∑ i=1md yi < 0
(1)

such that d ≥0 with at least one component dj positive. We argue that the dx ∈ ℜn part of d is a feasible cost-reducing direction for the original solution z as well - this would be a contradiction to the optimality of z. To do so, notice that no component of dy is positive as we could simply take M > 0 large enough and contradict (1). The fact that dy = 0 together with (1) immediately implies that dx is cost reducing c′dx < 0 and that it is feasible direction at z with respect to the original problem since

A(x + dx) + (y + dy) = 0⟹Adx = b − (Ax + y) = 0.

We hence conclude that the original problem cannot have any optimal solutions (i.e., it is either infeasible or unbounded).

(d)
Provide an example of an infeasible original problem with an unbounded big-M problem.
Consider the following linear optimization problem along its big-M version:
minimize  x1 − x2 + x3 subject to  − 2x1 − x3 = 1 − 3x1 + x3 = 1 x1,x2,x3 ≥ 0 minimize  x1 − x2 + x3 + My1 + My2 subject to  − 2x1 − x3 + y1 = 1 − 3x1 + x3 + y2 = 1 x1,x2,x3,y1,y2 ≥ 0

A closer inspection reveals that the original problem is infeasible. The initial tableau for the big-M problem is the following

x1 x2 x3 y1 y2
− 2M 1 + 5M − 1 1 0 0
y 1 = 1 − 2 0 − 1 1 0
y 2 = 1 − 3 0 1 0 1

The second column is cost-reducing while none of its components is positive; thus, the big-M problem immediately terminates with an optimal cost of −∞.

(e)
Provide an example of an unbounded original problem with an unbounded big-M problem.
Consider the following linear optimization problem along its big-M version:
minimize  − x1 − x2 subject to  x1 − x2 = 1 x1,x2 ≥ 0 minimize  − x1 − x2 + My1 subject to  x1 − x2 + y1 = 1 x1,x2,y1 ≥ 0 .

A closer inspection reveals that the original problem has an optimal cost of −∞. The initial tableau for the big-M problem is the following

x1 x2 y1
− M − 1 − M − 1 + M 0
y 1 = 1 1 − 1 1

Letting y1 exit the basis and x1 enter, we obtain

x1 x2 y1
1 0 − 2 1 + M
x 1 = 1 1 − 1 1

The second column is cost-reducing while none of its components is positive; thus, the big-M problem terminates with an optimal cost of −∞.

□
User profile picture
2022-03-13 23:13
Comments

(a) If the simplex terminates with ( x ∗ , 0 ) optimal for

min ⁡ x , y c ⊤ ⁡ x + M 1 ⊤ ⁡ y s.t. Ax + Iy = b , x , y ≥ 0 ,

then y ∗ = 0 ⇒ A x ∗ = b . From optimality,

c ⊤ ⁡ x ∗ + M 1 ⊤ ⁡ y ∗ ≤ c ⊤ ⁡ x + M 1 ⊤ ⁡ y , ∀ ⁡ ( x , y )  feasible.

Since y ∗ = 0 ,

c ⊤ ⁡ x ∗ ≤ c ⊤ ⁡ x + M 1 ⊤ ⁡ y .

Setting y = 0 gives c ⊤ ⁡ x ∗ ≤ c ⊤ ⁡ x , so x ∗ is optimal for the original problem

min ⁡ x c ⊤ ⁡ x s.t. Ax = b , x ≥ 0 .

(b) If the simplex terminates with ( x ∗ , y ∗ ) where y ∗ ≠ 0 , consider any ( x ^ , 0 ) feasible for the big- M problem

min ⁡ x , y c ⊤ ⁡ x + M 1 ⊤ ⁡ y s.t. Ax + Iy = b , x , y ≥ 0 .

For M sufficiently large,

c ⊤ ⁡ x ^ < c ⊤ ⁡ x ∗ + M 1 ⊤ ⁡ y ∗ ,

contradicting the optimality of ( x ∗ , y ∗ ) . Hence no ( x ^ , 0 ) is feasible for the big- M problem, so the original problem has no feasible solution (i.e., it is infeasible).

(c) The big- M problem has objective

z = c ⊤ ⁡ x + M 1 ⊤ ⁡ y , M ≫ 0 .

If the optimal cost is − ∞ , the simplex has found a feasible unbounded direction d = ( d x , d y ) satisfying

A ( x + 𝜃 d x ) + I ( y + 𝜃 d y ) = b ⇒ A d x + d y = 0 ,

and

x + t d x ≥ 0 , y + t d y ≥ 0 , ∀ ⁡ t ≥ 0 ,

with

c ⊤ ⁡ d x + M 1 ⊤ ⁡ d y < 0 .

From y + t d y ≥ 0 for all t , we get d y ≥ 0 . Since M is arbitrarily large and the inequality must hold, we must have d y = 0 ; otherwise the term M 1 ⊤ ⁡ d y would dominate c ⊤ ⁡ d x .

Hence

A d x = 0 , c ⊤ ⁡ d x < 0 .

Thus d x is a feasible descent direction for the original problem. If a feasible x exists, then x + t d x remains feasible and drives the objective to − ∞ ⇒ the original problem is unbounded. If no such x exists, the original problem is infeasible.

(d)

1) Original infeasible case

A = ( 1 0 0 0 ) , b = ( 0 1 ) , c = ( 0 − 1 ) .

Big- M formulation admits a feasible point ( x 1 , x 2 , y 1 , y 2 ) = ( 0 , 0 , 0 , 1 ) . A feasible direction is

d x = ( 0 , 1 ) , A d x = 0 , d x ≥ 0 , c ⊤ ⁡ d x = − 1 < 0 .

Hence the auxiliary problem has an unbounded descent ray d = ( d x , d y ) and cost → − ∞ , while no x satisfies Ax = b with x ≥ 0 . ⇒ The original problem is infeasible.

2) Original unbounded case

A = ( 1 0 ) , b = 1 , c = ( − 1 − 1 ) .

A feasible point for the big- M problem is ( x 1 , x 2 , y 1 , y 2 ) = ( 1 , 0 , 0 , 0 ) . The direction

d x = ( 0 , 1 ) , A d x = 0 , d x ≥ 0 , c ⊤ ⁡ d x = − 1 < 0 ,

and d y = 0 gives an unbounded descent ray. Since ( 1 , 0 ) is feasible for the original problem,

x + 𝜃 d x = ( 1 , 𝜃 ) , 𝜃 ≥ 0

remains feasible and drives c ⊤ ⁡ x → − ∞ . ⇒ The original problem is unbounded.

User profile picture
2025-10-23 22:07
Comments