Exercise 3.16 (Lexicography and the revised simplex method)

Question

Suppose that we have a basic feasible solution and an associated basis matrix $\mathbf{B}$ such that every row of $\mathbf{B}^{-1}$ is lexicographically positive. Consider a pivoting rule that chooses the entering variable $x_{j}$ arbitrarily (as long as $\bar{c}_{j}<0$ ) and the exiting variable as follows. Let $\mathbf{u}=\mathbf{B}^{-1} \mathbf{A}_{j}$. For each $i$ with $u_{i}>0$, divide the $i$ th row of $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1}\right]$ by $u_{i}$ and choose the row which is lexicographically smallest. If row $\ell$ was lexicographically smallest, then the $\ell$ th basic variable $x_{B(\ell)}$ exits the basis. Prove the following:
\begin{enumerate}[label=(\alph*)]
\item The row vector $\left(-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{b},-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1}\right)$ increases lexicographically at each iteration.
\item Every row of $\mathbf{B}^{-1}$ is lexicographically positive throughout the algorithm.
\item The revised simplex method terminates after a finite number of steps.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{remark} extbf{I could not prove the assertion in question for a long time but then I found an Indian webpage (link broken) which gave a counterexample to this exercise. Thus, this exercise is wrong as given. The corrected version is extit{\begin{enumerate}[label=(\alph*)] \item Every row of $[\mathbf{B}^{-1}\mathbf{b} \mid \mathbf{B}^{-1}]$ is lexicographically positive throughout the algorithm. \item The row vector $\left(-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} \mathbf{b},-\mathbf{c}_{B}^{\prime} \mathbf{B}^{-1} ight)$ increases lexicographically at each iteration. \item The revised simplex method terminates after a finite number of steps. \end{enumerate}} The proof and the counterexample from that webpage are presented as follows.} \end{remark} We replicate the proof of the Theorem 3.4.\par \begin{proof} extbf{Part (a).} Suppose that all rows of $\left[\mathbf{B}^{-1} b \mid \mathbf{B}^{-1} ight]$, other than the zeroth row, are lexicographically positive at the beginning of a simplex iteration. Suppose that $x_{j}$ enters the basis and that the pivot row is the $l$th row. According to the lexicographic pivoting rule, we have $u_{\ell}>0$ and \begin{equation} \dfrac{\left(\ell ext { th row of }\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight] ight)}{u_{\ell}} \stackrel{L}{<} \frac{\left(i ext { th row of }\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight] ight)}{u_{i}}, \quad ext{ if } i eq \ell ext{ and } u_{i}>0. \label{rowdiv} \end{equation} Denote by $\bar{\mathbf{B}}$ the new basis matrix, where column $\mathbf{A}_{\ell}$ is replaced by column $\mathbf{A}_{j}$. To determine the new matrix $\left[\bar{\mathbf{B}}^{-1} \mathbf{b} \mid \bar{\mathbf{B}}^{-1} ight]$ from the old one $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]$, the $\ell$ th row is divided by the positive $u_{\ell}$ and, therefore, remains lexicographically positive. Consider the $i$ th row of $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]$ and suppose that $u_{i}<0$. In order to zero $u_{i}$, we need to add a positive multiple of the pivot row to the $i$ th row. Due to the lexicographic positivity of both rows, the $i$ th row will remain lexicographically positive after this addition. Finally, consider the $i$ th row of $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]$ for the case where $u_{i}>0$ and $i eq \ell$. We have \begin{equation*} \left(i ext{th row of }\left[\bar{\mathbf{B}}^{-1} \mathbf{b} \mid \bar{\mathbf{B}}^{-1} ight] ight) = \left(i ext{th row of }\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight] ight)-\frac{u_{i}}{u_{\ell}}\left(\ell ext{th row of }\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight] ight) \end{equation*} Because of the lexicographic inequality $(1)$, which is satisfied by the old rows, the new $i$th row is also lexicographically positive.\par extbf{Part (b).} At the beginning of an iteration, the reduced cost $\bar{c}_{j}$ is negative. In order to make it zero, we need to add a positive multiple of the $\ell$ th row of $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]$. Therefore, the row vector $\left(-\mathbf{c}_{\bar{\mathbf{B}}}^{\prime} \bar{\mathbf{B}}^{-1} \mathbf{b},-\mathbf{c}_{\bar{\mathbf{B}}}^{\prime} \bar{\mathbf{B}}^{-1} ight)$ is obtained from the row vector $\left(-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} \mathbf{b},-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} ight)$ by adding a positive multiple of the $\ell$ th row of $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]$. Since the latter row is lexicographically positive, the row vector $\left(-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} \mathbf{b},-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} ight)$ increases lexicographically.\par extbf{Part (c).} Since the row vector $\left(-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} \mathbf{b},-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} ight)$ increases lexicographically at each iteration, it never returns to a previous value. Since the row vector $\left(-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} \mathbf{b},-\mathbf{c}_{\mathbf{B}}^{\prime} \mathbf{B}^{-1} ight)$ is determined completely by the current basis, no basis can be repeated twice and the revised simplex method must terminate after a finite number of iterations. This concludes the proof of this exercise.\par \end{proof} extbf{Counterexample to the part (b) in the book.} Consider the following linear programming problem: \begin{equation*} \begin{array}{ll} ext {minimize } & -x_1 \ ext {subject to } & 2 x_{1}-x_{2}+x_{3}+s_{1}=10 \ & x_{1}+x_{2}+2 x_{3}+s_{2}=6\ & x_{1}, x_{2}, x_{3}, s_{1}, s_{2} \geq 0 \end{array} \end{equation*} Let $\mathbf{B}$ be the basis matrix corresponding to the variables $s_{1}$ and $s_{2}$. Thus, $$ \mathbf{B}=\left[\begin{array}{cc} 1 & 0 \ 0 & 1 \end{array} ight], \quad\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]=\left[\begin{array}{c|cc} 10 & 1 & 0 \ 6 & 0 & 1 \end{array} ight] $$ Clearly, each row of $\mathbf{B}^{-1}$ is lexicographically positive. The reduced cost corresponding to variable $x_{1}$ is $-1$, so we let $x_{1}$ enter the basis. We obtain $$ \mathbf{u}=\mathbf{B}^{-1} \mathbf{A}_{1}=\left[\begin{array}{l} 2 \ 1 \end{array} ight] $$ By dividing each row of $\left[\mathbf{B}^{-1} \mathbf{b} \mid \mathbf{B}^{-1} ight]$ by the corresponding entry of $\mathbf{u}$, we obtain the matrix $$ \left[\begin{array}{c|cc} 5 & 1 / 2 & 0 \ 6 & 0 & 1 \end{array} ight] $$ The lexicographically smallest row is the first, thus $\ell=1$, and the 1 st basic variable $s_{1}$ exits the basis. The new basis matrix is therefore $$ \bar{\mathbf{B}}=\left[\begin{array}{ll} 2 & 0 \ 1 & 1 \end{array} ight] $$ The inverse of $\bar{\mathbf{B}}$ is $$ \bar{\mathbf{B}}^{-1}=\left[\begin{array}{cc} 1 / 2 & 0 \ -1 / 2 & 1 \end{array} ight] $$ It can be obtained, for example, using elementary row operations: $$ \left[\mathbf{B}^{-1} \mid \mathbf{u} ight]=\left[\begin{array}{ll|l} 1 & 0 & 2 \ 0 & 1 & 1 \end{array} ight] ightarrow\left[\begin{array}{cc|c} 1 / 2 & 0 & 1 \ 0 & 1 & 1 \end{array} ight] \longrightarrow\left[\begin{array}{cc|c} 1 / 2 & 0 & 1 \ -1 / 2 & 1 & 0 \end{array} ight] $$ Note that the second row of $\bar{\mathbf{B}}^{-1}$ is no longer lexicographically positive. This contradicts (b).

Exercise 3.16 (Lexicography and the revised simplex method)

Answers

Comments

Exercise 3.16 (Lexicography and the revised simplex method)

Answers

Comments

Add answer