3.4.4. Solving the Auxiliary LP

Now that we know how to construct \(P^{(0)}\) from the LP \(Q'\) corresponding to an optimal solution of \(Q\) (provided this solution has objective function value \(0\)), the last remaining piece in the puzzle is to figure out how to solve \(Q\).

As I said, we use the Simplex Algorithm to solve \(Q\). Does this work? We observed that if \(\hat z\) is the basic solution of \(P\), then \(\bigl(\hat z, \hat s\bigr)\) with \(\hat s = 0\) is the basic solution of \(Q\). Since we need to solve \(Q\) only if \(\hat z\) is infeasible, \(\bigl(\hat z, \hat s\bigr)\) is also infeasible in this case. Therefore, before we can apply the optimization phase of the Simplex Algorithm to find an optimal solution of \(Q\), we first need to transform \(Q\) into an equivalent LP \(Q^{(0)}\) whose basic solution is feasible.

To obtain \(Q^{(0)}\), we cannot apply the standard initialization phase just described to \(Q\) because this would lead to an infinite recursion: We'd construct an auxiliary LP \(R\) whose optimal solution gives us a feasible solution of \(Q\) and allows us to construct \(Q^{(0)}\), but the basic solution of \(R\) is just as infeasible as the basic solution of \(Q\), so we need to first transform \(R\) into an equivalent LP whose basic solution is feasible, and so on ad infinitum.

Fortunately, the structure of \(Q\) is special enough that a single pivoting operation transforms \(Q\) into an equivalent LP \(Q^{(0)}\) whose basic solution is feasible:

The set of equality constraints of \(Q\) is \(b = Az - 1s\). Let \(k\) be an index such that

\[b_k = \min\{b_1, \ldots, b_m\}.\]

Since we assume that the basic solution of \(Q\) is infeasible, there exists an index \(i\) such that \(b_i < 0\). Thus, \(b_k < 0\).

To obtain \(Q^{(0)}\), we apply a pivoting operation to \(Q\) in which the \(k\)th basic variable \(z_{j_k}\) leaves the basis and \(s\) enters the basis.

Let \(\bigl(\hat z^{(0)}, \hat s^{(0)}\bigr)\) be the basic solution of \(Q^{(0)}\).

Since \(s\) has coefficient \(-1\) in the \(k\)th constraint of \(Q\) and coefficient \(1\) in the \(k\)th constraint of \(Q^{(0)}\), the \(k\)th constraint of \(Q^{(0)}\) is obtained by multiplying the \(k\)th constraint of \(Q\) with \(-1\). Thus, \(\hat s^{(0)} = -b_k > 0\).

Pivoting does not change the value of any other non-basic variable \(z_j\) of \(Q\), so \(\hat z_j^{(0)} = \hat z_j = 0\) for each such variable.

The \(k\)th basic variable \(z_{j_k}\) of \(Q\) becomes non-basic in \(Q^{(0)}\) and thus satisfies \(\hat z_{j_k}^{(0)} = 0\).

For any basic variable \(z_{j_i}\) of \(Q\) with \(i \ne k\), we have \(\hat z_{j_i}^{(0)} = b_i^{(0)} = b_i - b_k\) because to give \(s\) coefficient \(0\) in the \(i\)th constraint of \(Q^{(0)}\), we simply add the \(k\)th constraint of \(Q^{(0)}\) to the \(i\)th constraint of \(Q\): \(s\) has coefficient \(1\) in the \(k\)th constraint of \(Q^{(0)}\) and coefficient \(-1\) in the \(i\)th constraint of \(Q\). Since \(b_k = \min \{ b_1, \ldots, b_m \}\), we have \(b_i - b_k \ge 0\), that is, \(\hat z_{j_i}^{(0)} \ge 0\).

This shows that the basic solution of \(Q^{(0)}\) is a BFS and we are now ready to find an optimal solution of \(Q^{(0)}\) using standard pivoting operations.