Big-M Method and Two-Phase Method

Big-M Method

The Big-M method of handling instances with artificial variables is the “commonsense approach”. Essentially, the notion is to make the artificial variables, through their coefficients in the objective function, so costly or unprofitable that any feasible solution to the real problem would be preferred, unless the original instance possessed no feasible solutions at all. But this means that we need to assign, in the objective function, coefficients to the artificial variables that are either very small (maximization problem) or very large (minimization problem); whatever this value,let us call it Big M.

In fact, this notion is an old trick in optimization in general; we simply associate a penalty value with variables that we do not want to be part of an ultimate solution(unless such an outcome is unavoidable). Indeed, the penalty is so costly that unless any of the  respective variables' inclusion is warranted algorithmically, such variables will never be part of any feasible solution. This method removes artificial variables from the basis. Here,  we assign a large undesirable (unacceptable penalty) coefficients to artificial variables from the objective function point of view. If the objective function (Z) is to be minimized, then a very large positive price (penalty, M) is assigned to each artificial variable and if Z is to be minimized, then a very large negative price is to be assigned. The penalty will be designated by +M for minimization problem and by –M for a maximization problem and also M>0.

Two-Phase Method

This method differs from Simplex method that first it is necessary to accomplish an auxiliary problem that has to minimize the sum of artificial variables. Once this first problem is resolved and reorganizing the final board, we start with the second phase, that consists in making a normal Simplex. Steps to solve a problem using two-phase simplex method:

n   Step 1

Modify the constraints so that the right-hand side of each constraint is nonnegative. This requires that each constraint with a negative right-hand side be multiplied through by -1.

n  Step 2

Identify each constraint that is now an = or ≥ constraint. In step 3, we will add an the artificial variable to each of these constraints.

n  Step 3

Convert each inequality constraint to standard form.

For ≤ constraint i, we add a slack variable s_i;

For ≥ constraint i, we add an excess variable e_i;

n  Step 4

For now, ignore the original LP’s objective function. Instead solve an LP whose objective function is min w’= (sum of all the artificial variables). This is called the Phase I LP. The act of solving the phase I LP will force the artificial variables to be zero.

Since each a_i≥0, solving the Phase I LP will result in one of the following three cases:

n  Case 1

The optimal value of w’ is greater than zero. In this case, the original LP has no feasible solution.

n  Case 2

The optimal value of w’ is equal to zero, and no artificial variables are in the optimal Phase I basis. In this case, we drop all columns in the optimal Phase I tableau that correspond to the artificial variables. We now combine the original objective function with the constraints from the optimal Phase I tableau. This yields the Phase II LP. The optimal solution to the Phase II LP is the optimal solution to the original LP.

n  Case 3

The optimal value of w’ is equal to zero and at least one artificial variable is in the optimal Phase I basis. In this case, we can find the optimal solution to the original LP if at the end of Phase I we drop from the optimal Phase I tableau all non-basic artificial variables and any variable from the original problem that has a negative coefficient in row 0 of the optimal Phase I tableau.

Tableau
		C0	C1	C2	...	Cn-k	...	Cn
Base	Cb	P0	P1	P2	...	Pn-k	...	Pn
P1	Cb1	b1	a11	a12	...	a1n-k	...	a1n
P2	Cb2	b2	a21	a22	...	a2n-k	...	a2n
...	...	...	...	...	...	...	...	...
Pm	Cbm	bm	am1	am2	...	amn-k	...	amn
Z		Z0	Z1	Z2	...	Zn-k	...	Zn

Being Zj = Σ(Cb·Pj) - Cj with Cj = 0 for all decision, slacks and surplus variables and Cj = -1 for artificial variables.

- Halt condition: The halt condition is the same that in Simplex method. The difference reside in that can occur two cases when halt condition is reached: the function takes zero value, it means that the original problem has solution, or function takes a different value, suggesting that our model does not have solution.

Special cases and solutions

Obtaining the solution : When halt condition is reached, we can see the basic variables' values that are in the base, and the optimal value that take the function looking at P0 column. At case we are minimizing, the optimal value must be multiplied by "-1".

Infinite Solution: Once halt condition is obeyed, if you notice that any variable that does not appear in the base, has a 0 value at row Z, it means that there exists another solution that gives us the same optimal value for the objective function. If we are in face with this case, we have a problem that admits infinite solutions, all of them among the segment that defines Ax+By=Z0.

Unbounded solution: If we notice that every variable in the incoming variable column has all its elements negative or void when we are searching the outgoing variable, we are face to face with a problem which have unbounded solution. There is no optimal concrete value, right now growing the values of variables, the objective function value also grows, and does not violate any restriction.

No Solution: In case that there seems to be no solution, we will have to solve it using Two-Phase Simplex method, so at the end of the 1st phase we will know if we are in such situation.

1st Phase Curiosity: When first phase finalize, if the original problem has solution, all the artificial variables, in the Z row, must have the value "1".

Pivot's value being 0 is possible?: It cannot be 0, because, quotients must be greater than 0.