Auxiliary problem

The simplex method requires an initial basic feasible solution. So far, we have not discussed how to obtain one. We now show how we can use the simplex method to obtain an initial basic feasible solution.

Let \(\mathbf{A}\in\mathbb{R}^{m\times n}\) with \(\operatorname{rank}(\mathbf{A}) = m\). Let \(\mathbf{b}\in \mathbb{R}^m\). Assume that \(\mathbf{b} \geq \mathbf{0}\). Let \((P')\) denote the problem \[ \begin{array}{rl} \min & x_{n+1} + \cdots + x_{n+m} \\ \text{s.t.} & \begin{bmatrix} \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} x_1 \\ \vdots \\ x_n \\ x_{n+1} \\ \vdots\\ x_{n+m}\end{bmatrix} = \mathbf{b} \\ & x_1,\ldots, x_{n+m} \geq 0 \end{array} \] where \(\mathbf{I}\) denotes the \(m\times m\) identity matrix.

The problem \((P')\) is called the auxiliary problem associated with \(\mathbf{A}\mathbf{x} =\mathbf{b},~\mathbf{x} \geq \mathbf{0}\).

Proposition 5.2.

The system \(\mathbf{A}\mathbf{x} = \mathbf{b},~\mathbf{x} \geq \mathbf{0}\) has a solution if and only if the optimal value of \((P')\) is \(0\).

Proposition 5.3.

Suppose that the optimal value of \((P')\) is 0. If the simplex method with an anti-cycling rule is applied to \((P')\) starting with the basis \(B=\{n+1,\ldots,n+m\}\), it will terminate with a basic feasible solution to \(\mathbf{A}\mathbf{x} = \mathbf{b},~\mathbf{x} \geq \mathbf{0}\) after components \(n+1,\ldots,n+m\) are removed.

Two-phase method

The following is an outline of the two-phase method for solving \[\begin{array}{rl} \min & \mathbf{c}^\mathsf{T} \mathbf{x} \\ \text{s.t.} & \mathbf{A}^\mathsf{T} \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \end{array}\] where \(\mathbf{A} \in \mathbb{R}^{m\times n}\) is of rank \(m\), \(\mathbf{b} \in \mathbb{R}^m\), and \(\mathbf{c} \in \mathbb{R}^n\):

1. Solve the auxiliary problem associated with \(\mathbf{A}^\mathsf{T} \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\) to obtain a basic feasible solution \(\mathbf{x}^*\) to \(\mathbf{A}^\mathsf{T} \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\).

2. Obtain a basis \(B\) determining \(\mathbf{x}^*\) and apply the simplex method starting with the basis \(B\).

With the two-phase method, we can now solve any linear programming problem in standard form.

We end with a few words should on the efficiency of the simplex method. Computational experiments over the years suggest that the simplex method is quite efficient in practice: the number of iterations is often linear in the number of constraints. Unfortunately, in the worst case, the number of iterations that the simplex method with every popular anti-cycling rule requires is exponential in the number of variables. At the moment, there is no known variant of the simplex method that requires a polynomial number of iterations in the worst case. Finding a choice rule for the entering and leaving variables that gives a polynomial-time simplex method is still an open problem.

Worked examples

1. Obtain a basic feasible solution to \[\begin{array}{rrcrcrcl} & x_1 & - & 2x_2 & - & x_3 & = & 1 \\ & x_1 & - & x_2 & + & x_3 & = & 3 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0. \end{array}\] by solving its associated auxiliary problem.

   The auxiliary problem is \[\begin{array}{rrcrcrcrcrcl} \min & & & & & & & x_4 & + & x_5 \\ (P)~~~~~\mbox{s.t.} & x_1 & - & 2x_2 & - & x_3 & + & x_4 & & & = & 1 \\ & x_1 & - & x_2 & + & x_3 & & & + & x_5 & = & 3 \\ & x_1 & , & x_2 & , & x_3 & , & x_4 & , & x_5 & \geq & 0. \end{array}\]

   We apply the revised simplex method starting with the basis \(B = \{4,5\}\). Note that \(B\) determines the basic feasible solution \(\mathbf{x}^* = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 3\end{bmatrix}\) to the auxiliary problem.

   Iteration 1

   1. \(N = \{1,2,3\}\).

   2. Solve \(\mathbf{y}^\mathsf{T}\mathbf{A}_B = \mathbf{c}_B^\mathsf{T}\); i.e. \(\begin{bmatrix}y_1 & y_2\end{bmatrix} \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix}1 & 1\end{bmatrix}\). We obtain \(y_1 = 1,~y_2 = 1\).

   3. Choose \(k = 1\) since \(\mathbf{y}^\mathsf{T}\mathbf{A}_1 = 2 \gt 0 = c_1\).

   4. Find \(\mathbf{d} = [d_1,d_2,d_3,d_4,d_5]^\mathsf{T}\) such that \(d_1 = 1\), \(d_2 = 0\), \(d_3 = 0\), and \[\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} d_4\\d_5\end{bmatrix} = \begin{bmatrix} -1\\ -1\end{bmatrix}.\] Solving, we obtain \(d_4 = -1\), \(d_5 = -1\).

   5. It is not true that \(\mathbf{d} \geq 0\).

   6. \(\lambda = \min\left\{\frac{x^*_4}{-d_4}, \frac{x^*_5}{-d_5}\right\} = \min\left\{\frac{1}{1}, \frac{3}{1}\right\} = 1\). Choose \(r = 4\).

   7. New \(\mathbf{x}^* = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \\ 3\end{bmatrix} + 1 \begin{bmatrix} 1 \\ 0 \\ 0 \\ -1 \\ -1 \end{bmatrix} = \begin{bmatrix} 1\\ 0 \\ 0 \\ 0 \\ 2\end{bmatrix}\).

   8. New \(B = \{1,5\}\).

   Iteration 2

   1. \(N = \{2,3,4\}\).

   2. Solve \(\mathbf{y}^\mathsf{T}\mathbf{A}_B = \mathbf{c}_B^\mathsf{T}\); i.e. \(\begin{bmatrix}y_1 & y_2\end{bmatrix} \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix} = \begin{bmatrix}0 & 1\end{bmatrix}\). We obtain \(y_1 = -1,~y_2 = 1\).

   3. Choose \(k = 2\) since \(\mathbf{y}^\mathsf{T}\mathbf{A}_2 = 1 \gt 0 = c_2\).

   4. Find \(\mathbf{d} = [d_1,d_2,d_3,d_4,d_5]^\mathsf{T}\) such that \(d_2 = 1\), \(d_3 = 0\), \(d_4 = 0\), and \[\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}\begin{bmatrix} d_1\\d_5\end{bmatrix} = \begin{bmatrix} 2\\ 1\end{bmatrix}.\] Solving, we obtain \(d_1 = 2\), \(d_5 = -1\).

   5. It is not true that \(\mathbf{d} \geq 0\).

   6. \(\lambda = \min\left\{\frac{x^*_5}{-d_5}\right\} = \min\left\{\frac{2}{1}\right\} = 2\). Choose \(r = 5\).

   7. New \(\mathbf{x}^* = \begin{bmatrix} 1\\ 0 \\ 0 \\ 0 \\ 2\end{bmatrix} + 2 \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ -1 \end{bmatrix} = \begin{bmatrix} 5\\ 2 \\ 0 \\ 0 \\ 0\end{bmatrix}\)

   8. New \(B = \{1,2\}\).

   Note that \(B = \{1,2\}\) is a basis with respect to the original system. Hence, \(\mathbf{x}^* = \begin{bmatrix} 5\\ 2 \\ 0 \end{bmatrix}\) is a basic feasible solution to the original system.