Exercise 3.26 (The big-$M$ method)

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\in {\Re }^n$ of the optimal solution of the big-$M$ problem $(x,0)\in {\Re }^{n+m}$ does not constitute for an optimal solution of the original problem. In other words, there exists a feasible solution $z\in {\Re }^n$ such that $c^{\prime }z<c^{\prime }x$. Obviously, the point $(z,0)\in {\Re }^{n+m}$ is a feasible solution for the big-$M$ problem as well. But then the objective function gives us $$c^{\prime }z+M0\sum _{i=1}^m{y}_i<c^{\prime }x+M0\sum _{i=1}^m{y}_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\ne 0$, then the original problem is infeasible.
Suppose for the sake of contradiction that the big-$M$ method terminates with a solution $(x,y)\in {\Re }^{n+m}$ for which $y\ne 0$, whereas the original problem is feasible with some optimal solution $z\in {\Re }^n$. Consider $(z,0)\in {\Re }^{n+m}$; obviously, this point is feasible for the big-$M$ method. But we then obtain $$c^{\prime }z+M0<c^{\prime }x+M\sum _{i=1}^m{y}_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 $-\infty$, show that the original problem is either infeasible or its optimal cost is $-\infty$.

Suppose for the sake of contradiction that the big-$M$ method terminates at a point $(x,y)\in {\Re }^{n+m}$ with the optimal cost of $-\infty$, whereas the original problem has an optimal solution $z\in {\Re }^n$. Whenever the big-$M$ simplex method does not result in a finite cost, it instead discovers a feasible direction $d=\left(d_x,d_y\right)\in {\Re }^{n+m}$ of cost decrease

$$c^{\prime }{d}_x+M\sum _{i=1}^m{d}_{y_i}<0$$

(1)

such that $d\ge 0$ with at least one component $d_j$ positive. We argue that the $d_x\in {\Re }^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 $d_y$ is positive as we could simply take $M>0$ large enough and contradict (1). The fact that $d_y=0$ together with (1) immediately implies that $d_x$ is cost reducing $c^{\prime }{d}_x<0$ and that it is feasible direction at $z$ with respect to the original problem since

$$A(x+d_x)+(y+d_y)=0⟹A{d}_x=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:

$$\begin{array}{cc}\text{minimize }\hfill & x_1-x_2+x_3\hfill \\ \text{subject to }\hfill & -2x_1-x_3=1\hfill \\ \hfill & -3x_1+x_3=1\hfill \\ \hfill & x_1,x_2,x_3\ge 0\hfill \end{array}\begin{array}{cc}\text{minimize }\hfill & x_1-x_2+x_3+M{y}_1+M{y}_2\hfill \\ \text{subject to }\hfill & -2x_1-x_3+y_1=1\hfill \\ \hfill & -3x_1+x_3+y_2=1\hfill \\ \hfill & x_1,x_2,x_3,y_1,y_2\ge 0\hfill \end{array}$$

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

	$x_1$	$x_2$	$x_3$	$y_1$	$y_2$
$-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 $-\infty$.

(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:

$$\begin{array}{cc}\text{minimize }\hfill & -x_1-x_2\hfill \\ \text{subject to }\hfill & x_1-x_2=1\hfill \\ \hfill & x_1,x_2\ge 0\hfill \end{array}\begin{array}{cc}\text{minimize }\hfill & -x_1-x_2+M{y}_1\hfill \\ \text{subject to }\hfill & x_1-x_2+y_1=1\hfill \\ \hfill & x_1,x_2,y_1\ge 0\hfill \end{array}.$$

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

	$x_1$	$x_2$	$y_1$
$-M$	$-1-M$	$-1+M$	$0$
$y_1=1$	$1$	$-1$	$1$

Letting $y_1$ exit the basis and $x_1$ enter, we obtain

	$x_1$	$x_2$	$y_1$
$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 $-\infty$.