Linear Programming: Artificial Variable Technique

When George Dantzig originally put forward the simplex method, it was limited only to LP problems having a known feasible solution, commonly called the initial basic feasible solution. When the traditional simplex method is applied to larger LP problems, the number of variables and number of iterations is increased considerably and with this, also the complexity.

Because simplex method is possibly the best and most universally applied pivot algorithm for solving LP problems, it became important to develop more general methods to solve LP problems, where an arbitrary initial basic solution (which was not necessarily a feasible solution) may be used to begin the pivoting process.

Dantzig (1955) and Wagner (1956) highlighted that for LPs without an initial basic feasible solution, almost all the current variants of the simplex method are applicable in two phases. In Phase I, a basic feasible solution is generated by adding variables known as artificial variables to the problem with a specially constructed auxiliary objective, aiming to minimise the sum of all the artificial variables while maintaining feasibility.

When all the artificial variables reach a value of zero, it means all the infeasibilities have been eliminated and we can continue with the normal simplex method in Phase II. If not, the problem does not have a feasible solution. Artificial variables are also used in another simplex method that predates the two-phase method and is known as the Big M method.

The Big M method allows the simplex algorithm to be applied to problems that contain a greater-than type of constraints by introducing a large negative constant M which would not be part of the final optimal solution if there is any.

In this article, readers will gain an insight into artificial variables and the two methods that use them to extend the simplex method to solve LP problems.

Artificial Variables Technique

In the previous article, you studied problems where slack and surplus variables readily provided an initial basic feasible solution. You assign zero cost to these variables in the objective function. A problem may arise when slack variables do not provide an initial basic feasible solution and it becomes difficult to start and proceed with the initial simplex tableau. This happens when the slack variables have negative values. For example, let us consider a constraint:

x + 3y ≥ 175

To replace this inequality with an equation, you need to subtract a slack variable so that you have:

x + 3y – S = 175

Now, if x and y are non-basic variables in the problem, then S is taken as the starting basic variable. But this means that the value of S = –175 which is infeasible. You cannot continue any more iterations of the simplex method with an infeasible basic solution. To generate an initial solution, you need to use the artificial variable technique so that you can proceed with the simplex method until the optimal solution is reached.

Artificial variables are added to constraints with greater than or equal to sign to generate an initial solution to an LP problem. In a physical sense, artificial variables have no meaning, they are purely a means for getting an initial solution to an LP problem and are eliminated later.

Big M Method (Penalty Method/ Charnes Method)

In some LP problems, the slack variables cannot give the initial basic feasible solution. In these types of LP problems, a minimum of one constraint is of ≥ type. Since a basis matrix cannot be obtained as an identity matrix in the initial simplex tableau, you use a new type of variable called the artificial variable to generate the initial basic solution.

You can extend the simplex method to solve such LP problems with artificial variables using either of the two methods:

• The Big M Method (also known as the Penalty Method or Charnes method)
• The Two-phase Simplex Method

Big M Algorithm

Step 1: Express the LP problem in the standard form by adding slack and/or surplus variables.

Step 2: Introduce non-negative artificial variables to the left side of all equations with constraints of the type >, or =. Remember that adding these artificial variables results in violation of the corresponding constraints. Hence, we have to eliminate these variables and cannot allow them to appear in the final solution. In order to do this, we have to assign a very large penalty (–M for maximisation and + M for minimisation) in the objective function.

Step 3: Use the simplex method to solve the modified LP problem, until any one of the three cases arise at an iteration:

• If in the basis, no vector corresponding to the artificial variable appears and the optimality conditions are met, the current solution is said to be the optimal basic feasible solution.
  
  
• If there is at least one vector corresponding to the artificial variable at zero level in the basis and the conditions of optimality are met, then the current basic solution is the optimal albeit degenerate solution.
  
  
• If there is at least one vector corresponding to the artificial variable at a positive level in the basis and the conditions of optimality are met, then there is no feasible solution to the original problem. The penalty, in this case, is very large, while the solution satisfies the constraints it does not optimise the objective function.

Inserting Slack, Surplus and Artificial Variables in the Big M Method

A slack variable is added to less than or equal to type of constraints to convert them to equalities. A surplus variable is added to greater than or equal to type of constraints to convert them to equalities.

For a binding constraint, the corresponding slack or surplus value will equal zero. Artificial variable is introduced in the LP model to obtain the initial basic feasible solution. It is used for the equality constraints and for the greater than or equal to type of inequality constraints.

Comparison Between the Different Types of Variables

Let us now see where the variables are inserted in the Big M method:

In Step 1 of the Big M method, the constraints of the given LP problem are expressed in the equation form by including slack variables for constraint of the type ≤ or surplus variables for constraint of the type ≥.

Now, the basic solution for the problem, an infeasible one can be determined as the basic variable is negative for constraints of the type ≥.

In Step 2 of the Big M method, non-negative artificial variables are added to the left-hand side of each of the equations corresponding to the constraints of the types > and = to generate a starting basic feasible solution.

Two Phase Method

The two-phase method is so named because the LP problem is solved in two phases. Simplex method is applied to a specially constructed auxiliary LP problem in Phase I, and the problem is solved by applying the simplex method which helps in generating a basic feasible solution to the original problem.

The process of elimination of artificial variables is performed in Phase I of the solution and Phase II is used to obtain an optimal solution using a simplex.

In Phase I, the artificial variables are introduced for making the vari- ables of the original problem non-basic and set them to zero even though this might be infeasible to the original problem. The resulting infeasibilities are taken on by the artificial variables and they are basic at the beginning of Phase I.

Let us now look into the steps of the two-phase method:

PHASE 1

Step 1: Express the given LP problem into standard form and check if a starting basic feasible solution to the problem exists. One of the two cases might arise:

• There is a ready starting basic feasible solution, in which case we may proceed to Phase II.
• No starting basic feasible solution exists to the problem, in which case you move on to the next step of Phase I.

Step 2: Add the artificial variable to the left-hand side of each equation that does not have the required starting basic variables. Construct an auxiliary objective function whose aim is to minimise the sum of all artificial variables.

Therefore,

Minimise Z= A1 + A2 + A3 + ………. + An

becomes

Maximize Z* = – A1 – A2 – A3 – ………. – An

where Ai (i = 1,2,3…m) are the non-negative artificial variables.

Step 3: Apply the simplex algorithm to the specially constructed auxiliary LP problem. At the last iteration, we may have one of the follow- ing three cases:

• Max Z* < 0 and at least one positive artificial variable is present in the basis, in which case, no feasible solution exists for the original LP problem.
  
  
• Max Z* = 0 with at least one artificial variable at zero value in the basis, in which case, a feasible solution exists for the original LP problem. To obtain the basic feasible solution, we may either proceed directly to Phase II or else eliminate the artificial basic variable and then proceed to Phase II.
  
  
• Max Z* = 0 and there is no artificial variable in the basis, in which case, you have obtained a basic feasible solution to the original LP problem and we can proceed to Phase II.

PHASE 2

The optimum basic feasible solution of phase I is used as the initial basic feasible solution for the original LP problem. Assign actual coefficients to the variables in the objective function and zero value to the artificial variables that show zero value in the final simplex tableau of Phase I. Use the normal simplex algorithm on the modified simplex tableau to obtain the optimum solution of the original problem.

Comparison of Big M Simplex Method and the Two-phase Simplex Method

The drawback to Big M method is related to how we choose the penalty M. If M is too small, the final solution to the original problem may not even be feasible, let alone optimal, since the penalty for infeasibility was not big enough.

On the other hand, if M is very large, the original problem can have numerical issues and the final solution may not be optimal. Sometimes, no M value exists that can prevent both these issues. Another limitation of the big M method over the two-phase method is that in the former, feasibility is not known until optimality is reached.