Dual feasible tableau

Let \(m\) and \(n\) be positive integers. Let \(\mathbf{A}\in \mathbb{R}^{m\times n}\) with rank \(m\), \(\mathbf{b} \in \mathbb{R}^m\), \(\mathbf{c} \in \mathbb{R}^n\), and \(\mathbf{x} = \begin{bmatrix} x_1\\ \vdots\\ x_n\end{bmatrix}\) be a tuple of variables. Consider the following linear programming problem: \[\begin{array}{rl} \min & \mathbf{c}^\mathsf{T}\mathbf{x} \\ (P)~~~~\mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x}\geq \mathbf{0}. \end{array}\] The dual problem of \((P)\) is \[\begin{array}{rl} \max & \mathbf{y}^\mathsf{T}\mathbf{b} \\ (D)~~~~\mbox{s.t.} & \mathbf{y}^\mathsf{T}\mathbf{A} \leq \mathbf{c}^\mathsf{T}. \end{array}\] Recall that a basis \(B\) of \(\mathbf{A}\) is said to be dual feasible with respect to \((P)\) if \(\mathbf{y}^*\) satisfying \({\mathbf{y}^*}^\mathsf{T}\mathbf{A}_B = \mathbf{c}_B^\mathsf{T}\) is a feasible solution to \((D)\).

Note that if \(\mathbf{y}^*\) satisfies \({\mathbf{y}^*}^\mathsf{T}\mathbf{A}_B = \mathbf{c}_B^\mathsf{T}\), then \(\mathbf{y}^*\) must be \( \left(\mathbf{c}_B^\mathsf{T}\mathbf{A}_B^{-1}\right)^\mathsf{T}\). With this, \(\mathbf{y}^*\) is a feasible solution to \((D)\) if and only if \({\mathbf{y}^*}^\mathsf{T}\mathbf{A}_N \leq \mathbf{c}^\mathsf{T}_N\) where \(N = \{1,\ldots, n\} \backslash B\).

The tableau associated with a dual feasible basis \(B\) is called a dual feasible tableau. Recall that the tableau associated with \(B\) is \begin{eqnarray*} z- (\mathbf{c}^\mathsf{T}_N - \mathbf{y}^\mathsf{T}\mathbf{A}_N)\mathbf{x}_N & = & \mathbf{y}^\mathsf{T}\mathbf{b}\\ \mathbf{x}_B + \mathbf{A}_B^{-1} \mathbf{A}_N\mathbf{x}_N & = & \mathbf{A}_B^{-1} \mathbf{b} \end{eqnarray*} where \(\mathbf{y}^\mathsf{T} = \mathbf{c}^\mathsf{T}_B\mathbf{A}_B^{-1}\). Thus, a dual feasible tableau is a tableau such that in the \(z\)-row, the coefficients of \(\mathbf{x}\) are all nonpositive and the right-hand side value is the objective function value of \(\mathbf{y}\) with respect to \((D)\).

Hence, a dual feasible tableau specifies implicitly a dual feasible solution whose objective function value is given by the right-hand side value of the \(z\)-row. Since \((D)\) is a maximization problem, we want to pivot in a way that improves the dual objective function value while maintaining dual feasibility. For this to be possible, the leaving variable needs to be a basic variable that has a negative value in the basic solution. But how do we choose the entering variable? Let us look at an example.

Consider \((P)\) with \(\mathbf{A} = \begin{bmatrix} 2 & 1 & 0 & -1 \\ -5 & -2 & 1 & 1\end{bmatrix}\), \(\mathbf{b} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}\), \(\mathbf{c} = \begin{bmatrix} 3 \\ 1 \\ 3 \\ -1 \end{bmatrix}\). The tableau associated with the basis \(B = \{2,4\}\) is dual feasible: \[\begin{array}{rcrcrcc} z & - & x_1 & & & - & 3x_3 & & & = & 1 \\ & & 3x_1 & + & x_2 & - & x_3 & & & = & -2 \\ & & x_1 & & & - & x_3 & +& x_4 & = & -3. \end{array}\] Since both basic variables in the basic feasible solution determined by \(B\) are negative, either variable can be chosen as the leaving variable. We choose \(x_2\).

Now, if we choose \(x_1\) as the entering variable, then we will be using the second equation to clear \(x_1\) in the \(z\)-row and the \(x_4\)-row. But doing so will not result in a dual feasible tableau. It can be seen in general that we must choose a variable that has a negative coefficient in the row of the leaving variable. In our case, \(x_3\) is the only choice. The tableau associated with the new basis \(B = \{3,4\}\) is \[\begin{array}{rcrcrcc} z & - & 10x_1 & - & 3x_2 & & & & & = & 7 \\ & & -3x_1 & - & x_2 & + & x_3 & & & = & 2 \\ & & -2x_1 & - & x_2 & & & +& x_4 & = & -1. \end{array}\] Note that this tableau is still dual feasible. The only choice for the leaving variable is \(x_4\). But we have two variables with a negative coefficient in the \(x_4\)-row. Can either be the entering variable? If we choose \(x_1\) and uses the last equation to clear \(x_1\) in the \(z\)-row, the coefficient of \(x_2\) will become positive, resulting in tableau that is not dual feasible. So we must choose \(x_2\) as the entering variable. The tableau associated with the new basis \(B = \{2,3\}\) is \[\begin{array}{rcrcrcc} z & - & 4x_1 & & & & & - & 3x_4 & = & 10 \\ & & 2x_1 & + & x_2 & & & - & x_4 & = & 1 \\ & & -x_1 & & & + & x_3 & - & x_4 & = & 3. \end{array}\] From this, we see that \(B\) is an optimal basis and so \(\mathbf{x} = \begin{bmatrix} 0 \\ 1 \\ 3\\0\end{bmatrix}\) is an optimal solution.

Tableau method with dual feasible tableaux

Input: The problem \((P)\) and a dual feasible basis \(B\).
Steps:

1. Obtain the tableau associated with \(B\). Let \(N = \{1,\ldots, n\}\backslash B\)

2. Let \(r \in B\) be such that the right-hand side value of the \(x_r\)-row is negative. If no such \(r\) exists, then stop; \(B\) is an optimal basis.

3. For each \(j \in N\), let \(\bar{a}_{rj}\) denote the coefficient of \(x_j\) in the \(x_r\)-row. Let \(K = \{ j \in N : \bar{a}_{rj} \lt 0\}\). If \(K = \emptyset\), then stop; \((P)\) is infeasible.

4. For each \(j \in N\), let \(\bar{c}_j\) denote the negative of the coefficient of \(x_j\) in the \(z\)-row. Let \(k \in K\) be such that \[-\frac{\bar{c}_k}{\bar{a}_{rk}} = \min \left\{ -\frac{\bar{c}_j}{\bar{a}_{rj}} : j \in K \right\}.\]

5. Replace \(B\) with \((B\cup \{k\})\backslash \{r\}\) and go to step 1.

Cycling can occur if we are not careful in our choices of the entering and leaving variables. However, Bland's anti-cycling rule also works here; namely, if we always choose the variable with the smallest index whenever there is a choice, cycling cannot occur.

Worked examples

1. Consider the dual feasible tableau associated with the basis \(B=\{2,3\}\): \[\begin{array}{rcrcrcc} z & - & 4x_1 & & & & & - & 3x_4 & = & 5 \\ & & -2x_1 & + & x_2 & & & - & 2x_4 & = & -1 \\ & & -x_1 & & & + & x_3 & - & x_4 & = & 3. \end{array}\] Suppose that one iteration of the tableau method with dual feasible tableaux is performed. What will be the entering and leaving variables if Bland's anti-cycling rule is used?

   The basic solution \(\mathbf{x}^*\) determined by \(B\) has \(x^*_2 = -1\) and \(x^*_3 = 3\). Thus, \(x_2\) will be the leaving variable.

   Now, \(\bar{c}_1 = 4\), \(\bar{c}_4 = 3\), \(\bar{a}_{2,1} = -2\), and \(\bar{a}_{2,4} = -2\). Hence, \[\min\left\{-\frac{\bar{c}_1}{\bar{a}_{2,1}},-\frac{\bar{c}_4}{\bar{a}_{2,4}} \right\} = \min\left\{2,\frac{3}{2}\right\} = \frac{3}{2}.\] Hence, \(x_4\) is the entering variable.

2. Consider the tableau \[\begin{array}{rcrcrcc} z & - & 4x_1 & & & & & - & 3x_4 & = & 10 \\ & & 2x_1 & + & x_2 & & & - & x_4 & = & 1 \\ & & -x_1 & & & + & x_3 & - & x_4 & = & 3. \end{array}\] associated with the optimal basis \(B = \{2,3\}\). Suppose that the constraint \(-2x_2 + x_3 + x_5 = 0\) is added where \(x_5\) is a new variable required to be nonnegative. Obtain a dual feasible tableau for the modified problem and solve modified problem using the tableau method discussed above.

   Adding the equation to the tableau gives: \[\begin{array}{rcrcrcrcc} z & - & 4x_1 & & & & & - & 3x_4 & & & = & 10 \\ & & 2x_1 & + & x_2 & & & - & x_4 & & & = & 1 \\ & & -x_1 & & & + & x_3 & - & x_4 & & & = & 3 \\ & & & & -2x_2 & + & x_3 & & & + & x_5 & = & 0. \end{array}\] Adding \(2\) times the second equation to the last equation and adding \(-1\) times the third equation to the last equation gives: \[\begin{array}{rcrcrcrcc} z & - & 4x_1 & & & & & - & 3x_4 & & & = & 10 \\ & & 2x_1 & + & x_2 & & & - & x_4 & & & = & 1 \\ & & -x_1 & & & + & x_3 & - & x_4 & & & = & 3 \\ & & 5x_1 & & & & & - & x_4 & + & x_5 & = & -1. \end{array}\] This is a dual feasible tableau associated with the basis \(B = \{2,3,5\}\). Note that we must have \(x_5\) as the leaving variable and \(x_4\) as the entering variable. The new tableau is: \[\begin{array}{rcrcrcrcc} z & - & 19x_1 & & & & & & & - & 3x_5 & = & 13 \\ & & -3x_1 & + & x_2 & & & & & - & x_5 & = & 2 \\ & & -6x_1 & & & + & x_3 & & & - & x_5 & = & 4 \\ & & -5x_1 & & & & & + & x_4 & - & x_5 & = & 1. \end{array}\] Thus, \(B = \{2,3,4\}\) is an optimal basis. Hence, \(\begin{bmatrix} x_1\\x_2\\x_3\\x_4\\x_5\end{bmatrix} =\begin{bmatrix} 0\\2\\4\\1\\0\end{bmatrix}\) is an optimal solution to the modified problem.

3. Consider \((P)\) with \(\mathbf{c} = \mathbf{0}\). Let \(B\) be a basis. Show that the tableau associated with \(B\) is dual feasible.

   Let \(B\) be a basis. Recall that the tableau associated with \(B\) is \begin{eqnarray*} z- (\mathbf{c}^\mathsf{T}_N - \mathbf{y}^\mathsf{T}\mathbf{A}_N)\mathbf{x}_N & = & \mathbf{y}^\mathsf{T}\mathbf{b}\\ \mathbf{x}_B + \mathbf{A}_B^{-1} \mathbf{A}_N\mathbf{x}_N & = & \mathbf{A}_B^{-1} \mathbf{b} \end{eqnarray*} where \(\mathbf{y}^\mathsf{T} = \mathbf{c}_B^\mathsf{T}\mathbf{A}_B^{-1}\). Hence, if \(\mathbf{c} = \mathbf{0}\), \(\mathbf{y} = \mathbf{0}\) and \(\mathbf{c}_N = \mathbf{0}\). Thus \(\mathbf{c}^\mathsf{T}_N - \mathbf{y}^\mathsf{T}\mathbf{A}_N = \mathbf{0}\), implying that the tableau is dual feasible.

4. Consider the tableau associated with a dual feasible basis \(B\) with respect to \((P)\) given by \begin{eqnarray*} z- \sum_{j \in N} \bar{c}_j x_j & = & v \\ x_i + \sum_{j \in N} \bar{a}_{ij} x_j & = & \bar{b}_i ~~~~ i \in B \end{eqnarray*} Suppose that \({\mathbf{y}^*}^\mathsf{T}\) is given by \(\mathbf{c}_B^\mathsf{T}\mathbf{A}_B^{-1},\) \(\bar{c}_j \gt 0\) for all \(j \in N\), and \(\bar{b}_r \lt 0\) for some \(r \in B\).

   1. Show that the \(x_r\)-row is given by \(\mathbf{d}^\mathsf{T} \mathbf{A} \mathbf{x} = \mathbf{d}^\mathsf{T} \mathbf{b}\) where \(\mathbf{d}^\mathsf{T}\) is a row of \(\mathbf{A}_B^{-1}\).

      Recall that the tableau associated with \(B\) is \begin{eqnarray*} z- (\mathbf{c}^\mathsf{T}_N - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_N)\mathbf{x}_N & = & {\mathbf{y}^*}^\mathsf{T}\mathbf{b}\\ \mathbf{x}_B + \mathbf{A}_B^{-1} \mathbf{A}_N\mathbf{x}_N & = & \mathbf{A}_B^{-1} \mathbf{b}. \end{eqnarray*} In other words, \(\mathbf{x}_B + \mathbf{A}_B^{-1} \mathbf{A}_N\mathbf{x}_N = \mathbf{A}_B^{-1} \mathbf{b}\) is given by \(\mathbf{A}_B^{-1} \mathbf{A}\mathbf{x} = \mathbf{A}_B^{-1} \mathbf{b}.\) Since the \(x_r\)-row is one of the equations in \(\mathbf{A}_B^{-1} \mathbf{A}\mathbf{x} = \mathbf{A}_B^{-1} \mathbf{b},\) the result follows.

   2. Show that for a sufficiently small \(\lambda \gt 0\), \(\mathbf{y}^* + \lambda(-\mathbf{d})\) is a feasible solution to \((D)\) with a larger objective function value than \(\mathbf{y^*}\).

      Note that \(\mathbf{y}^* + \lambda(-\mathbf{d})\) is a feasible solution to \((D)\) if and only if \[(\mathbf{y}^* + \lambda(-\mathbf{d})^\mathsf{T}) \mathbf{A} \leq \mathbf{c}^\mathsf{T}\] if and only if \begin{eqnarray*} \lambda(-\mathbf{d}^\mathsf{T}) \mathbf{A}_B & \leq & \mathbf{c}_B^\mathsf{T} - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_B \\ \lambda(-\mathbf{d}^\mathsf{T}) \mathbf{A}_N & \leq & \mathbf{c}_N^\mathsf{T} - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_N. \\ \end{eqnarray*}

      Observe that if \(i \in B\), then \[\mathbf{d}^\mathsf{T} \mathbf{A}_i = \left \{ \begin{array}{ll} 1 & \text{ if } i = r \\ 0 & \text{ otherwise.} \end{array} \right .\] Since \({\mathbf{y}^*}^\mathsf{T}\mathbf{A}_B = \mathbf{c}_B^\mathsf{T}\), we have \(\lambda(-\mathbf{d}^\mathsf{T}) \mathbf{A}_B \leq \mathbf{c}_B^\mathsf{T} - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_B\) for all \(\lambda \geq 0\).

      Next, note that \(\mathbf{c}_j^\mathsf{T} - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_j = \bar{c}_j \gt 0\) for all \(j \in N\) implies that we can choose . \(\lambda\) small enough so that \(\lambda(-\mathbf{d}^\mathsf{T}) \mathbf{A}_N \leq \mathbf{c}_N^\mathsf{T} - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_N.\)

      The objective function value of \(\mathbf{y}^* + \lambda(-\mathbf{d})\) is \({\mathbf{y}^*}^\mathsf{T}\mathbf{b} + \lambda(- \mathbf{d}^\mathsf{T}\mathbf{b}) = {\mathbf{y}^*}^\mathsf{T}\mathbf{b} + \lambda(- \bar{b}_r) \gt {\mathbf{y}^*}\mathbf{b} \) as \(\lambda \gt 0\) and \(\bar{b}_r \lt 0\).

   3. Determine the largest value for \(\lambda\) such that \(\mathbf{y}^* + \lambda(-\mathbf{d})\) is a feasible solution to \((D)\).

      As seen in the previous part, \(\mathbf{y}^* + \lambda(-\mathbf{d})\) is a feasible solution to \((D)\) if and only if \(\lambda(-\mathbf{d}^\mathsf{T}) \mathbf{A}_N \leq \mathbf{c}_N^\mathsf{T} - {\mathbf{y}^*}^\mathsf{T}\mathbf{A}_N.\) When \(\lambda \geq 0\), this inequality holds if and only if for all \(j \in N\) such that \(\mathbf{d}^\mathsf{T} \mathbf{A}_j \lt 0\), we have \(\lambda(-\mathbf{d}^\mathsf{T} \mathbf{A}_j) \leq \bar{c}_j\). As \(\mathbf{d}^\mathsf{T} \mathbf{A}_j = \bar{a}_{rj}\), the maximum value for \(\lambda\) is given by \[\min \left\{ \frac{\bar{c}_{j}}{-\bar{a}_{rj}} : j \in N,~\bar{a}_{rj} \lt 0\right\}.\]