Starting the Simplex Method, how to begin when no obvious basic solution exists

In linear optimization, the Simplex method is one of the most widely used techniques for finding optimal solutions. However, before the algorithm can begin, it needs a starting point: an initial feasible basic solution.

Why do we need artificial variables?

When all the constraints in a problem are of the “less than or equal to” ($\leqslant$) type with positive right-hand sides, the slack variables naturally form an identity matrix, which provides an initial basis.

The difficulty appears when equality constraints ($=$) or “greater than or equal to” constraints ($\geqslant$) are present. In these situations, an identity matrix is not immediately available. To overcome this issue, we introduce artificial variables ($x^a \geqslant 0$).

These variables have no meaning in the original problem, they are simply a mathematical device used to construct an initial basis. The goal is for these variables to leave the basis and take the value zero in the final solution. If an artificial variable remains positive in the final solution, the original problem is infeasible, meaning that no solution satisfies all the constraints.

Two main approaches are commonly used to handle these variables: the penalty method, also known as the Big-M method, introduced in (Charnes et al., 1953), and the Two-Phase method, introduced in (Wagner, 1956).

The Big-M (Penalty) Method

This approach penalizes artificial variables in the objective function using a very large constant M.

• If the objective is minimization, we add $M \cdot x^a$ for each artificial variable.
• If the objective is maximization, we subtract $M \cdot x^a$ for each artificial variable.

This large penalty forces the algorithm to push artificial variables toward zero in order to improve the objective value.

Consider the following linear optimization problem:

\[\begin{aligned} \max\;\; & z = -5x_1 + 6x_2 + 7x_3 \\ \textrm{s. t.:}\;\; & 2x_1 + 10x_2 - 6x_3 \geqslant 30 \\ & 3x_1 - 3x_2 + 5x_3 \leqslant 10 \\ & 2x_1 + 2x_2 + 2x_3 = 5 \\ & x_1, x_2, x_3 \geqslant 0 \end{aligned}\]

To apply the Big-M method, we introduce slack variables ($x_4^h$ and $x_5^h$). Since the first constraint is of type $\geqslant$ and the third is an equality, we cannot directly obtain an identity matrix. Therefore, artificial variables ($x_6^a, x_7^a$) must also be introduced. The standard form becomes:

\[\begin{aligned} \max\;\; & z = -5x_1 + 6x_2 + 7x_3 \\ \textrm{s. t.:}\;\; & 2x_1 + 10x_2 - 6x_3 - x_4^h + x_6^a = 30 \\ & 3x_1 - 3x_2 + 5x_3 + x_5^h = 10 \\ & 2x_1 + 2x_2 + 2x_3 + x_7^a = 5 \\ & x_1, x_2, x_3, x_4^h, x_5^h, x_6^a, x_7^a \geqslant 0 \end{aligned}\]

The second tableau gives the final result:

\[\begin{array}{rc|rrrrrrr|r} & & {\color{gray}-5} & {\color{gray}6} & {\color{gray}7} & {\color{gray}0} & {\color{gray}0} & {\color{gray}-M} & {\color{gray}-M} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^a & x_7^a & \\ \hline & z_j - c_j & 8M+11 & 0 & 16M-1 & M & 0 & 0 & 6M+3 & -5M+15 \\ \hline {\color{gray}-M} & x_6^a & -8 & 0 & -16 & -1 & 0 & 1 & -5 & 5 \\ {\color{gray}0} & x_5^s & 6 & 0 & 8 & 0 & 1 & 0 & 3/2 & 35/2 \\ {\color{gray}6} & x_2 & 1 & 1 & 1 & 0 & 0 & 0 & 1/2 & 5/2 \\ \hline \end{array}\]

Since the objective value is $-5M+15 \neq 0$, at least one artificial variable remains in the basis. Therefore, the original problem is infeasible.

The Two-Phase Method

This approach separates the procedure into two clearly defined stages.

• Phase 1: The original objective function is temporarily ignored. Instead, we minimize the sum of all artificial variables ($w = \sum x^a$).
  • If the minimum value of $w$ is 0, we have found a feasible solution for the original problem and can proceed to Phase 2.
  • If the value is greater than 0, the problem is infeasible.
• Phase 2: The auxiliary objective function and the columns corresponding to the artificial variables are removed. The original objective function is restored, and the Simplex method continues from the solution obtained in Phase 1.

For the previous example, the auxiliary model solved in Phase 1 is:

\[\begin{aligned} \max\;\; & w = x_6^a + x_7^a \\ \textrm{s. t.:}\;\; & 2x_1 + 10x_2 - 6x_3 - x_4^h + x_6^a = 30 \\ & 3x_1 - 3x_2 + 5x_3 + x_5^h = 10 \\ & 2x_1 + 2x_2 + 2x_3 + x_7^a = 5 \\ & x_1, x_2, x_3, x_4^h, x_5^h, x_6^a, x_7^a \geqslant 0 \end{aligned}\]

The second tableau provides the final result:

\[\begin{array}{rc|rrrrrrr|r} & & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}0} & {\color{gray}1} & {\color{gray}1} & \\ & & x_1 & x_2 & x_3 & x_4^s & x_5^s & x_6^a & x_7^a & \\ \hline & w_j - c_j & -8 & 0 & -16 & -1 & 0 & 0 & -6 & 5 \\ \hline {\color{gray}1} & x_6^a & -8 & 0 & -16 & -1 & 0 & 1 & -5 & 5 \\ {\color{gray}0} & x_5^s & 6 & 0 & 8 & 0 & 1 & 0 & 3/2 & 35/2 \\ {\color{gray}0} & x_2 & 1 & 1 & 1 & 0 & 0 & 0 & 1/2 & 5/2 \\ \hline \end{array}\]

Since the objective value is $5 \neq 0$, at least one artificial variable remains in the basis, in this case $x_6^a$. Therefore, the original problem has no feasible solution.

If a basic solution with $w = 0$ had been obtained, the algorithm would proceed to Phase 2 using the original objective function.

Both methods allow us to construct an initial basis for the Simplex method. The penalty approach incorporates artificial variables directly into the objective function, whereas the Two-Phase method explicitly separates the search for feasibility from the optimization step.

In summary, both the Big-M method and the Two-Phase method provide systematic ways to initialize the Simplex method when no obvious starting basis is available. Although both approaches aim at the same goal, the Two-Phase method is usually conceptually clearer and is more commonly used in modern implementations.