Now for Simplex algorithm, we only have the last piece of puzzle missing, that is we need to figure out how to find the initial basic feasible solution. In this blog, we will introduce several ways to implement it.
Start from easy example
Let’s start with some easy cases that can give us some intuitions. For following LP problems, this is straightforward:
\[\begin{aligned} & \min & \bar{c}^\top \bar{x} \\ & \text{s.t. } & A\bar{x} \leq \bar{b}\\ && \bar{x} \geq \bar{0}\\ \end{aligned}\]introduce slack variables
\[\begin{aligned} & \min & \bar{c}^\top \bar{x} + \bar{0}^\top \bar{s} \\ & \text{s.t. } & A\bar{x} + I \bar{s} \leq \bar{b}\\ && \bar{x} ,\bar{s} \geq \bar{0}\\ \end{aligned}\]The vector ${ \left[ \begin{array}{c} \bar{x} & \bar{s} \end{array}\right] ^\top }$ is a basic feasible solution of above LP problem in standard form. Since it satisfies the all the nonnegativity constraints with corresponding basis matrix ${B = I}$
Next, we can apply the simplex algorithm to the LP problem starting from the initial basis matrix ${B = I}$ and ${\bar{s}_1, \bar{s}_2, …, \bar{s}_m}$ as basic variables.
General cases
We will introduce two strategies to find the initial basic feasible solution.
Two Phase Simplex
Auxiliary Problem
For a general LP problem in standard form, it can be done by solving an auxiliary LP problem. Consider the standard form LP problem
\[\begin{aligned} & \min & \bar{c}^\top \bar{x} \\ & \text{s.t. } & A\bar{x} = \bar{b}\\ && \bar{x} \geq \bar{0}\\ \end{aligned}\]Without loss of generality, we may assume that ${A}$ has full row rank and ${\bar{b} \geq \bar{0}}$. (If not, we can 1) remove redundant rows from the linear system ${A\bar{x} = \bar{b}}$ and 2) multiply some of the equations/constraints by $-1$ to ensure that ${\bar{b} \geq \bar{0}}$)
We consider the auxiliary problem
\[\begin{aligned} & \min & y_1 + y_2 + \cdots + y_m \\ & \text{s.t. } & A\bar{x} + I \bar{y} = \bar{b}\\ && \bar{x},\bar{y} \geq \bar{0}\\ \end{aligned}\]The variables $y_1, y_2, \ldots, y_m$ are called artificial variables. The following vector
\[\begin{aligned} \left[ \begin{array}{c} 0 \\ 0 \\ \vdots \\ 0 \\ b_1 \\ b_2 \\ \vdots \\ b_m \\ \end{array} \right] \end{aligned}\]is an initial basic feasible solution for this auxiliary problem with the identity $m \times m$ matrix as its corresponding basis matrix and $b_1 + b_2 + \cdots + b_m (\geq 0)$ as initial cost.
Thus, the auxiliary problem is necessarily feasible. Furthermore, since $\bar{y} \geq 0$, the auxiliary cost function $y_1 + y_2 + \cdots + y_m$ is bounded below over the (auxiliary) polyhedron and the optimal cost of the auxiliary problem is $\geq 0$.
- If the original problem is feasible and $\bar{x}^*$ is a feasible solution of it, then the following vector
is necessarily a feasible solution of the auxiliary problem with zero cost. Therefore, if the optimal cost of the auxiliary problem is $> 0$, we can conclude that the original problem is infeasible.
- On the other hand, if solving the auxiliary problem yields a zero cost solution, then this solution is of type
and $\bar{x}^*$ is necessarily a feasible solution of the original problem.
Thus, this detour via the auxiliary problem either detects infeasibility of the original problem or finds a feasible solution of the original problem.
| AUXILIARY PROBLEM | ORIGINAL PROBLEM |
|---|---|
| FEASIBLE with optimal cost $> 0$ | INFEASIBLE |
| FEASIBLE with optimal cost $= 0$ | FEASIBLE and $\bar{x}^*$ is an initial b.f.s. |
GO back to Original Problem
If the simplex algorithm applied to the auxiliary problem terminates with a basis matrix $B$ consisting exclusively of columns of $A$, we can use that basis matrix $B$ as initial basis matrix for the simplex algorithm applied to the original problem.
However, it can happen that the basis matrix associated with the b.f.s. with zero cost found for the auxiliary problem does not consist exclusively of columns of $A$ but does contain columns of the identity matrix.
Claim: There exists another basis corresponding to the optimal b.f.s. $\left[ \begin{array}{c} \bar{x}^* \mid \bar{0} \end{array} \right]^\top$ of the auxiliary problem consisting exclusively of columns of $A$, i.e. containing no artificial variable.
Proof. Suppose the simplex algorithm applied to the auxiliary problem terminates with a feasible solution $\bar{x}^*$ to the original problem, but some of the artificial variables are in the final basis.
Let $k$ be the number of columns of $A$ that belong to the basis. (We have $k<m$ since we assumed that some column corresponding to an artificial variable is in the basis.)
Without loss of generality, we may assume that these are the columns $\bar{A}_{B(1)}, \bar{A}_{B(2)}, \ldots, \bar{A}_{B(k)}$. In particular, $x_{B(1)}, x_{B(2)}, \ldots, x_{B(k)}$ are the only components of $\bar{x}^*$ that may be nonzero.
Since $A$ has full row rank, the columns of $A$ span $\mathbb{R}^m$. Columns $\bar{A}_{B(1)}, \bar{A}_{B(2)}, \ldots, \bar{A}_{B(k)}$ are linearly independent (because they are part of a basis) and we can choose $m-k$ additional columns $\bar{A}_{B(k+1)}, \bar{A}_{B(k+2)}, \ldots, \bar{A}_{B(m)}$ of $A$ so as to obtain a set of $m$ linearly independent columns, that is, a basis consisting exclusively of columns of $A$. For this basis, all non-basic components of $\bar{x}^$ are zero and $\bar{x}^$ is therefore a b.f.s. associated with this new basis as well.
Therefore, we will
- drive the artificial variables out of the basis one by one until the basis no longer contains any column corresponding to an artificial variable
- drop the artificial variables and the corresponding columns from the tableau.
Kick artificial variables out of the basis.
Suppose that the $l$-th basic variable is an artificial variable which is in the basis as zero. We want this variable to exit the basis. We check the $l$-th row of the tableau and find some $j$ such that the $l$-th entry of the $j$-th column $B^{-1}\bar{A}_j$ is not zero.
We claim that $\bar{A}_j$ is linearly independent from $\bar{A}_{B(1)}, \bar{A}_{B(2)}, \cdots, \bar{A}_{B(k)}$. Otherwise, we had $\bar{A}_j = c_1 \bar{A}_{B(1)} + \ldots + c_k \bar{A}_{B(k)}$ for some $c_1, \ldots, c_k \in \mathbb{R}$, then we have
\[B^{-1}\bar{A}_j = c_1 B^{-1}\bar{A}_{B(1)} + \ldots + c_k B^{-1}\bar{A}_{B(k)} = c_1 e_1 + \ldots + c_k e_k = \begin{bmatrix} c_1 \\ \vdots \\ c_k \\ 0 \\ \vdots \\ 0 \end{bmatrix}\]which is not possible since we have chosen $j$th column such that its $l$-th entry is not zero.
The $l$-th basic variable (which is an artificial variable) exits the basis and $x_j$ is brought into the basis.
The tableau is updated as usual, the only difference is that the pivot element (the $l$-th entry of $B^{-1}\bar{A}_j$) could be negative. Note that the $l$-th basic variable was (artificial and) zero, which means adding a multiple of the $l$-th row to the other rows does not change the values of the zeroth column. So, we are still at the same b.f.s. to the auxiliary problem but we have removed an artificial variables from bases.
We repeat this procedure as many times as needed until all artificial variables are driven out of the basis.
Tips: In practice, we never check if $A$ has full row rank before we solve the auxiliary problem. Therefore, it could happen that the $l$-th row of the tableau does not contain a nonzero entry. In that case, we know the $l$-th row of $[B^{-1}\bar{b} \mid B^{-1}A]$ is some linear combination of remaining rows. Hence, the $l$-th row of the linear system $\left[ B^{-1}\bar{b} \mid B^{-1}A \right]$ is a redundant constraint and we simply drop that $l$-th row from the tableau.
In this strategy, we first use auxiliary LP problem, which called phase 1 Simplex. And the following steps solving original problem are called phase 2. Hence, this strategy is called 2-Phase Simplex.
Big-M Method
The “big-M” method is an alternate approach that combines the two phases into a single one.
Idea: Introduce the artificial variables $y_i$ of the auxiliary problem but use the cost function \(c_1x_1 + c_2x_2 + \ldots + c_nx_n + M(y_1 + y_2 + \ldots + y_m)\)
where we treat $M$ as a very large positive constant.
Because $M$ is sufficiently large, if the original problem is feasible and its optimal cost is finite, all of the artificial variables are eventually equal to zero, which takes us back to the minimization of the original cost function $c_1x_1 + c_2x_2 + \ldots + c_nx_n$.
In practice, we don’t need to set an actual value for $M$; we can leave $M$ as a parameter and let the reduced costs be functions of $M$. Whenever $M$ is compared to another number in order to determine whether a reduced cost is negative, $M$ is treated as being larger.