Parametric simplex method

We now consider a hybrid method that combines the simplex method and the dual simplex method so that we can begin with any basis and avoid solving a problem in standard form in two phases. To that end, we need to introduce a parameter, resulting in the parametric simplex method. The technique is reminiscent of perturbation that we have encountered earlier.

Motivating example

Consider the linear programming problem \((P)\) \(\min \left\{ \mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{A}^\mathsf{T} \mathbf{x} = \mathbf{b},~ \mathbf{x} \geq \mathbf{0}\right\}\) where \(\mathbf{A} = \begin{bmatrix} 2 & 1 & 1 & 1 \\ -5 & -2 & 4 & 1\end{bmatrix}\), \(\mathbf{b} = \begin{bmatrix} 1 \\ 3 \end{bmatrix}\), \(\mathbf{c} = \begin{bmatrix} 2 \\ 1 \\ -3 \\ -2 \end{bmatrix}\). The tableau associated with the basis \(B = \{1,2\}\) is \[\begin{array}{rcrcrcrcrcl} z & & & & & - & (-4)x_3 & - & (-3)x_4 & = & 1 \\ & & x_1 & + & & - & 6x_3 & - & 3x_4 & = & -5 \\ & & & & x_2 & + & 13x_3 & + & 7x_4 & = & 11. \end{array}\] This tableau is neither feasible nor dual feasible.

Let \(\mu \in \mathbb{R}\). We modify the tableau to the following: \[\begin{array}{rcrcrcrcrcl} z & & & & & - & (-4+\mu)x_3 & - & (-3+\mu)x_4 & = & 1 \\ & & x_1 & & & - & 6x_3 & - & 3x_4 & = & -5+\mu \\ & & & & x_2 & + & 13x_3 & + & 7x_4 & = & 11. \end{array}\] When \(\mu = 0\), this tableau is identical to the original. However, it is an optimal tableau if and only if \begin{align*} -4 + \mu & \geq 0, \\ -3 + \mu & \geq 0, \\ -5 + \mu & \geq 0. \end{align*} Simplifying gives \(\mu \geq 5\).

If \(\mu\) is just a bit less than \(5\), the tableau is no longer optimal but is dual feasible. We can therefore pivot according to the dual simplex method with \(x_1\) as the leaving variable. Since \(\min \left \{ \frac{-4+\mu}{6}, \frac{-3+\mu}{3} \right\} = \frac{-4+\mu}{6}\) when \(\mu\) is just less than \(5\), we can have \(x_3\) as the entering variable. The new tableau is \[\begin{array}{rcrcrcrcrcl} z & - & \left(-\frac{2}{3}+\frac{\mu}{6}\right)x_1 & & & & & - & \left(-1+\frac{\mu}{2}\right)x_4 & = & -\frac{7}{3} +\frac{3\mu}{2}-\frac{\mu^2}{6} \\ & & -\frac{1}{6}x_1 & & & + & x_3 & + & \frac{1}{2}x_4 & = & \frac{5}{6}-\frac{\mu}{6} \\ & & \frac{13}{6}x_1 & + & x_2 & & & + & \frac{1}{2}x_4 & = & \frac{1}{6}+\frac{13\mu}{6}. \end{array}\] This tableau is optimal if and only if \begin{align*} -\frac{2}{3} + \frac{\mu}{6} & \geq 0, \\ -1 + \frac{\mu}{2} & \geq 0, \\ \frac{5}{6} - \frac{\mu}{6} & \geq 0, \\ \frac{1}{6} + \frac{13\mu}{6} & \geq 0. \end{align*} Simplifying gives \(4 \leq \mu \leq 5\).

If \(\mu\) is just a bit less than \(4\), the tableau is no longer optimal but is feasible. We can pivot with \(x_1\) as the entering variable and \(x_2\) (the only choice here) as the leaving variable. The new tableau is \[\begin{array}{rcrcrcrcrcl} z & & & - & \left(\frac{4}{13} - \frac{u}{13}\right)x_2 & & & - & \left(-\frac{11}{13}+\frac{6\mu}{13}\right)x_4 & = & -\frac{31}{13}+\frac{11\mu}{13} \\ & & & & \frac{1}{13}x_2 & + & x_3 & + & \frac{7}{13}x_4 & = & \frac{11}{13} \\ & & x_1 & + & \frac{6}{13}x_2 & & & + & \frac{3}{13}x_4 & = & \frac{1}{13} + \mu. \end{array}\] This tableau is optimal if and only if \begin{align*} \frac{4}{13} - \frac{\mu}{13} & \geq 0, \\ -\frac{11}{13} + \frac{6\mu}{13} & \geq 0, \\ \frac{1}{13} + \mu & \geq 0. \end{align*} Simplifying gives \(\frac{11}{6} \leq \mu \leq 4\).

If \(\mu\) is just a bit less than \(\frac{11}{6}\), the tableau is no longer optimal but is feasible. We can pivot with \(x_1\) as the entering variable and \(x_2\) (the only choice here) as the leaving variable. The new tableau is \[\begin{array}{rcrcrcrcrcl} z & & & - & \left(\frac{3}{7} - \frac{\mu}{7}\right)x_2 & - & \left(\frac{11}{7}-\frac{6\mu}{7}\right)x_3 & & & = & -\frac{26}{7}+\frac{11\mu}{7} \\ & & & & \frac{1}{7}x_2 & + & \frac{13}{7}x_3 & + & x_4 & = & \frac{11}{7} \\ & & x_1 & + & \frac{3}{7}x_2 & - & \frac{3}{7}x_3 & & & = & -\frac{2}{7} + \mu. \end{array}\] This tableau is optimal if and only if \begin{align*} \frac{3}{7} - \frac{\mu}{7} & \geq 0, \\ \frac{11}{7} - \frac{6\mu}{7} & \geq 0, \\ -\frac{2}{7} + \mu & \geq 0. \end{align*} Simplifying gives \(\frac{2}{7} \leq \mu \leq \frac{11}{6}\).

If \(\mu\) is just a bit less than \(\frac{2}{7}\), the tableau is no longer optimal but is dual feasible. We can pivot with \(x_1\) as the leaving variable and \(x_3\) (the only choice here) as the entering variable. The new tableau is \[\begin{array}{rcrcrcrcrcl} z & - & \left(\frac{11}{3} - 2\mu\right)x_1 & - & \left(2 - \mu \right)x_2 & - & & & & = & -\frac{8}{3}-\frac{8\mu}{3}+2\mu^2 \\ & & \frac{13}{3}x_1 & + & 2x_2 & & & + & x_4 & = & \frac{1}{3} + \frac{13u}{3} \\ & & -\frac{7}{3}x_1 & - & x_2 & + & x_3 & & & = & \frac{2}{3} - \frac{7\mu}{3}. \end{array}\] This tableau is optimal if and only if \begin{align*} \frac{11}{3} - 2\mu & \geq 0, \\ 2 - \mu & \geq 0, \\ \frac{1}{3} + \frac{13}{3}\mu & \geq 0, \\ \frac{2}{3} - \frac{7\mu}{3} & \geq 0. \end{align*} Simplifying gives \(-\frac{1}{13} \leq \mu \leq \frac{2}{7}\). Note that \(0\) is in the range. Hence, the tableau is optimal with \(\mu = 0\), which is also an optimal tableau for the original problem \((P)\). It follows that \(\mathbf{x} = \begin{bmatrix} 0\\ 0 \\ \frac{1}{3} \\ \frac{2}{3}\end{bmatrix}\) is an optimal soluiton to \((P)\) with optimal value \(-\frac{8}{3}\).

Avoiding degeneracy

In the example above, we were able to make progress by decreasing the value of \(\mu\) by a positive amount. In addition, every time we decreased \(\mu\) below its lower bound by a tiny amount, we ended up with a tableau that is either feasible or dual feasible. However, these observations do not necessarily hold in all cases as illustrated in one of the worked examples below.

We use an idea similar to perturbation for preventing cycling so that degeneracy does not occur; i.e. the value of \(\mu\) decreases by a positive amount after every pivot.

Recall that the tableau for \((P)\) associated with the basis \(B\) is \[\begin{array}{rcrcrcl} z & & & - & (\mathbf{c}_N^\mathsf{T} - \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{array}\] where \(\mathbf{y}^\mathsf{T} = \mathbf{c}^\mathsf{T}_B\mathbf{A}_B^{-1}\).

Let \(\epsilon > 0\). Consider \[\begin{array}{rcrcrcl} z & - & \mu\mathbf{v}_B^\mathsf{T}\mathbf{x}_B & - & (\mathbf{c}_N^\mathsf{T} - \mathbf{y}^\mathsf{T}\mathbf{A}_N + \mu\mathbf{v}_N^\mathsf{T})\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} + \mu \mathbf{u} \end{array}\] where \(\mathbf{u} = \begin{bmatrix} 1 \\ 1 + \epsilon \\ 1 + \epsilon^2 \\ \vdots \\ 1 + \epsilon^{m-1}\end{bmatrix}\) and \(\mathbf{v} \in \mathbb{R}^n\) be such that \(\mathbf{v}_N = \begin{bmatrix} 1+\epsilon^m \\ 1 + \epsilon^{m+1} \\ \vdots \\ 1 + \epsilon^{n-1}\end{bmatrix}\) and \(\mathbf{v}_B = \begin{bmatrix} \epsilon^{n} \\ \epsilon^{n+1} \\ \vdots \\ \epsilon^{n+m-1}\end{bmatrix}\). The tableau associated with \(B\) then has the form \begin{align*} z- (\mathbf{c}^\mathsf{T}_N - \mathbf{y}^\mathsf{T}\mathbf{A}_N +\mu\mathbf{v}_N^\mathsf{T})\mathbf{x}_N & = \gamma \\ \mathbf{x}_B + \mathbf{A}_B^{-1} \mathbf{A}_N\mathbf{x}_N & = \mathbf{A}_B^{-1} \mathbf{b} + \mu \mathbf{u} \end{align*} for some \(\gamma\). Clearly, the tableau is feasible when \(\mu\) is sufficiently large. Now, \begin{align*} & \mathbf{c}^\mathsf{T}_N - \mathbf{y}^\mathsf{T}\mathbf{A}_N + \mu\mathbf{v}_N^\mathsf{T} \\ = \; & \mathbf{c}^\mathsf{T}_N - (\mathbf{c}+\mu\mathbf{v})^\mathsf{T}_B\mathbf{A}_B^{-1}\mathbf{A}_N + \mu\mathbf{v}_N^\mathsf{T} \\ = \; & \mathbf{c}^\mathsf{T}_N - \mathbf{c}^\mathsf{T}_B\mathbf{A}_B^{-1}\mathbf{A}_N - \mu\mathbf{v}^\mathsf{T}_B\mathbf{A}_B^{-1}\mathbf{A}_N + \mu\mathbf{v}_N^\mathsf{T} \\ = \; & \left(\mathbf{c}^\mathsf{T}_N - \mathbf{c}^\mathsf{T}_B\mathbf{A}_B^{-1}\mathbf{A}_N + \mu \begin{bmatrix} 1 \\ \vdots \\ 1\end{bmatrix}^\mathsf{T}\right)- \mu\left(\begin{bmatrix} \epsilon^n \\ \vdots \\ \epsilon^{n+m-1} \end{bmatrix}^\mathsf{T} \mathbf{A}_B^{-1}\mathbf{A}_N - \begin{bmatrix} \epsilon^m \\ \vdots \\ \epsilon^{n-1}\end{bmatrix}^\mathsf{T} \right) \\ = \; & \left(\mathbf{c}^\mathsf{T}_N - \mathbf{c}^\mathsf{T}_B\mathbf{A}_B^{-1}\mathbf{A}_N + \mu \begin{bmatrix} 1 \\ \vdots \\ 1\end{bmatrix}^\mathsf{T}\right)- \mu\epsilon^m\left(\begin{bmatrix} \epsilon^{n-m} \\ \vdots \\ \epsilon^{n-1} \end{bmatrix}^\mathsf{T} \mathbf{A}_B^{-1}\mathbf{A}_N - \begin{bmatrix} \epsilon^0 \\ \vdots \\ \epsilon^{n-m-1}\end{bmatrix}^\mathsf{T} \right) \\ \geq \; & \mathbf{0}^\mathsf{T} \end{align*} when \(\mu\) is sufficiently large and \(\epsilon\) sufficiently small.

In summary, there exist \(\mu\) and \(\epsilon\) sufficiently small such that the tableau is optimal. The algorithm can therefore start with this tableau. It remains to show that for an appropriately chosen \(\epsilon\), whenever \(\mu\) is just below the lower bound for the current tableau to be optimal, the new tableau will be either feasible or dual feasible and that there is a unique choice for the pivot. The details of the proof are left as an exercise.

Remark. Instead of using powers of \(\epsilon\), we can set the entries of \(\mathbf{u}\) and those of \(\mathbf{v}_N\) to be random numbers in, say, the interval \([1,2]\), and the entries of \(\mathbf{v}_B\) to be very small positive random numbers. Then with probability close to 1, degeneracy cannot occur.

Worked examples

1. Consider the following tableau associated with the basis \(\{1,2\}\): \[\begin{array}{rcrcrcrcrcl} z & & & & & - & (-4+2\mu)x_3 & - & (3-\mu)x_4 & = & 3 \\ & & x_1 & & & + & 2x_3 & - & 4x_4 & = & -2+\mu \\ & & & & x_2 & + & 3x_3 & + & x_4 & = & 6 - 3\mu \end{array}\] where \(\mu \in \mathbb{R}\).

   1. Show that the tableau is optimal if and only if \(\mu=2\).

      We need \begin{align*} -4+2\mu & \geq 0, \\ 3 - \mu & \geq 0, \\ -2 + \mu & \geq 0, \\ 6 - 3\mu & \geq 0. \end{align*} Simplifying gives \(\mu = 2\).

   2. Show that if the value of \(\mu\) goes below \(2\) the tableau is neither feasible nor dual feasible.

      It is not feasible since in the \(x_1\)-row, the right-hand side will be negative. It is not dual feasible since in the \(z\)-row, the coefficient of \(x_3\) will be positive.

   3. In any case, do each of the following:

      1. Pivot according to the dual simplex method and obtain a range of values for \(\mu\) so that the resulting tableau is optimal.

         The leaving variable is \(x_1\). Since in the \(x_1\)-row, only \(x_4\) has a negative coefficient, \(x_4\) will be the entering variable. The new tableau is \[\begin{array}{rcrcrcrcrcl} z & - & \left(\frac{3}{4}-\frac{\mu}{4}\right)x_1 & & & - & \left(-\frac{5}{2}+\frac{3\mu}{2}\right)x_3 & & & = & \frac{9}{2} - \frac{5\mu}{4} + \frac{\mu^2}{4} \\ & & -\frac{1}{4}x_1 & & & - & \frac{1}{2}x_3 & + & x_4 & = & \frac{1}{2}-\frac{\mu}{4} \\ & & \frac{1}{4}x_1 & + & x_2 & + & \frac{7}{2}x_3 & & & = & \frac{11}{2}-\frac{11\mu}{4} \end{array}\] where \(\mu \in \mathbb{R}\). The tableaus is optimal if and only if \begin{align*} \frac{3}{4}-\frac{\mu}{4} & \geq 0, \\ -\frac{5}{2}+\frac{3\mu}{2} & \geq 0, \\ \frac{1}{2}-\frac{\mu}{4} & \geq 0, \\ \frac{11}{2}-\frac{11\mu}{4} & \geq 0. \\ \end{align*} Simplifying gives \(\frac{5}{3} \leq \mu \leq 2\). We see that we can make progress and lower \(\mu\) all the way to \(\frac{5}{3}\).

      2. Pivot according to the simplex method and obtain a range of values for \(\mu\) so that the resulting tableau is optimal.

         Since in the \(z\)-row, only \(x_3\) has a positive coefficient when \(\mu\) is less than \(2\). Hence, \(x_3\) is the entering variable. Then \(x_2\) will be the leaving variable. The new tableau is \[\begin{array}{rcrcrcrcrcl} z & & & - & \left(\frac{4}{3}-\frac{2\mu}{3}\right)x_2 & & & - & \left(\frac{13}{3}-\frac{5\mu}{3}\right)x_4 & = & -5 + 8\mu - 2\mu^2 \\ & & x_1 & - & \frac{2}{3}x_2 & & & - & \frac{14}{3}x_4 & = & -6+3\mu \\ & & & & \frac{1}{3}x_2 & + & x_3 & + & \frac{1}{3}x_4 & = & 2-\mu \end{array}\] where \(\mu \in \mathbb{R}\). The tableaus is optimal if and only if \begin{align*} \frac{4}{3}-\frac{2\mu}{3} & \geq 0, \\ \frac{13}{3}-\frac{5\mu}{3} & \geq 0, \\ -6+ 3\mu & \geq 0, \\ 2-\mu & \geq 0. \end{align*} Simplifying gives \(\mu = 2\). Hence, the value of \(\mu\) cannot be decreased.

2. Consider the tableau associated with the basis \(\{1,2\}\) \[\begin{array}{rcrcrcrcl} z & & & & & + & 3x_3 & = & 0 \\ & & x_1 & & & - & 2x_3 & = & -3 \\ & & & & x_2 & + & x_3 & = & 0. \end{array}\]

   1. Transform the tableau into one that incorporates perturbations as described in the section on avoiding degeneracy.

      We start with \[\begin{array}{rcrcrcrcl} z & - & \mu\epsilon^3 x_1 & - & \mu\epsilon^4 x_2 & - & \left(-3 + \mu(1+\epsilon^2)\right)x_3 & = & 0 \\ & & x_1 & & & - & 2x_3 & = & -3 + \mu \\ & & & & x_2 & + & x_3 & = & \mu(1+\epsilon) \end{array}\] where \(\epsilon > 0\) is very small. Eliminating \(x_1\) and \(x_2\) in the \(z\)-row gives the tableau \[\begin{array}{rcrcrcrcl} z & & & & & - & \left(- 3 + \mu (1 + \epsilon^2 + 2\epsilon^3 - \epsilon^4)\right)x_3 & = & -\mu\epsilon^3+\mu^2(\epsilon^3+\epsilon^4+\epsilon^5) \\ & & x_1 & & & - & 2x_3 & = & -3 + \mu \\ & & & & x_2 & + & x_3 & = & \mu(1+\epsilon) \end{array}\]

   2. Let \(\mu\) goes just below the value for which the tableau is optimal and perform a single pivot.

      The tableau in the previous part is optimal if and only if \(\mu\) satisfies \begin{align*} -3 + \mu(1+\epsilon^2+2\epsilon^3-\epsilon^4) & \geq 0, \\ -3 + \mu & \geq 0, \\ \mu(1 + \mu) & \geq 0. \end{align*} Rewriting gives \begin{align*} \mu & \geq \frac{3}{1+\epsilon^2+2\epsilon^3-\epsilon^4}, \\ \mu & \geq 3, \\ \mu & \geq 0. \end{align*} Since \(\epsilon\) is a very small positive number, \(\frac{3}{1+\epsilon^2+2\epsilon^3-\epsilon^4}\) is less than 3. Hence, the system simplifies to \(\mu \geq 3\). We perform a pivot as in the dual simplex method with \(x_1\) as the leaving variable and \(x_3\) as the entering variable to obtain the tableau \[\begin{array}{rcrcrcrcl} z & - & \frac{1}{2}\left(-3+\mu(1+\epsilon^2+2\epsilon^3-\epsilon^4)\right)x_1 & & & & & = & \gamma \\ & & -\frac{1}{2}x_1 & & & + & x_3 & = & \frac{3}{2} - \frac{\mu}{2} \\ & & \frac{1}{2}x_1 & + & x_2 & & & = & -\frac{3}{2}+\mu\left(\frac{3}{2}+\epsilon\right) \end{array}\] where \(\gamma = -\frac{9}{2} +\mu\left(3+\frac{3}{2}\epsilon^2+2\epsilon^3-\frac{3}{2}\epsilon^4\right) +\mu^2\left(-\frac{1}{2}-\frac{\epsilon^2}{2}+\frac{3\epsilon^4}{2} + \epsilon^5\right).\) The tableau is optimal if and only if \[\frac{3}{1+\epsilon^2+2\epsilon^3-\epsilon^4} \leq \mu \leq 3.\] If \(\mu\) goes below the lower bound, then we will have a feasible tableau from which we can perform a pivot with \(x_1\) as the leaving variable and \(x_2\) as the entering variable.

      Exercise. Continue the process till completion.