Degeneracy¶
The Simplex Pivot Tool is useful for the first exercise.
Fundamental Theorem of Linear Programming¶
For an arbitrary linear program in standard form, the following statements are true:
If there is no optimal solution, then the problem is either infeasible or unbounded.
If a feasible solution exists, then a basic feasible solution exists.
If an optimal solution exists, then a basic optimal solution exists.
Proof of Bland’s Rule¶
Bland’s rule is essentially a Smallest-Subscript Rule i.e. if more than one entering variable or leaving variable can be chosen, always choose the variable with the smallest subscript. Notice that this is very similar to the Largest-Coefficient Largest-Subscript Rule. The only difference besides the subscript selection is that the entering variable no longer needs to have the largest positive coefficient.
The proof in this chapter and [Burb] lacked some essential observations that are covered in [Gab]. The following derivations provide the necessary details to understand the proof in [Bura].
The objective value never decreases during the simplex method.¶
A dictionary is defined as
where \(\mathcal{B}\) and \(\mathcal{N}\) are the basic and nonbasic integer sets satisfying
\(\mathcal{B}\) contains \(m\) elements,
\(\mathcal{B} \cap \mathcal{N} = \emptyset\),
and \(\mathcal{B} \cup \mathcal{N} = \{1, \ldots, n + m\}\).
A dictionary is said to be feasible if \(0 \leq b_i \forall i \in \mathcal{N}\). If a dictionary is feasible, then a basic feasible solution (BFS) exists for the LP such as \(x_i = b_i\) and \(x_j = 0\).
Assume the simplex method is operating with a deterministic pivot rule such as the
- Largest-Coefficient Largest-Subscript Rule
Choice of Entering Variable: Choose \(x_{e}\) so that \(e\) is largest among the variables \(x_{j \in \mathcal{N}}\) such that \(\hat{c}_j = \max \{ \hat{c}_k \colon k \in \mathcal{N} \}\).
Choice of Leaving Variable: Choose \(x_{l}\) so that \(l\) is largest among the variables \(x_{i \in \mathcal{B}}\) such that \(\frac{\hat{b}_i}{\hat{a}_{ie}} = \min \left\{ \frac{\hat{b}_k}{\hat{a}_{ke}} \colon k \in \mathcal{B}, \hat{a}_{ke} > 0 \right\}\).
The pivot step will construct a dictionary for the new basis as follows:
Solve for \(x_e\) in the equation for \(x_l\)
\[x_e = \frac{b_l}{a_{le}} - \sum_{j \in \mathcal{N}'} \frac{a_{lj}}{a_{le}} x_j\]where \(\mathcal{N}' = N \cup \{ l \} \setminus \{ e \}\) and \(a_{ll} = 1\).
Substitute \(x_e\) in the rest of the dictionary:
(4)¶\[\begin{split}\zeta &= \nu + c_e x_e + \sum_{j \in \mathcal{N}'} c_j x_j\\ &= \nu + c_e \frac{b_l}{a_{le}} + \sum_{j \in \mathcal{N}'} \left( c_j - c_e \frac{a_{lj}}{a_{le}} \right) x_j\\ \\ x_i &= b_i - a_{ie} x_e - \sum_{j \in \mathcal{N}'} a_{ij} x_j & \quad & i \in \mathcal{B}\\ &= b_i - a_{ie} \frac{b_l}{a_{le}} + \sum_{j \in \mathcal{N}'} \left( a_{ie} \frac{a_{lj}}{a_{le}} - a_{ij} \right) x_j\end{split}\]
Since the pivots are reversible equality-preserving transformations, each dictionary constructed by the algorithm is still feasible due to the minimum ratio test. The test is not applicable when the set of leaving variables is empty, but the LP is unbounded in that case.
Observe that only the basic variables, \(\zeta\), \(x_e\), and \(x_l\) changed. Since \(c_e > 0\), \(a_{le} > 0\), and \(b_l \geq 0\), the new objective value cannot decrease; it can stay constant if \(b_l = 0\). Once the set of entering variables becomes empty, the current basis is a local optimum because each variable in a feasible solution needs to be nonnegative. Since LPs are convex, a local optimum is the global optimum.
If the simplex method fails to terminate, then it must cycle.¶
Since pivot operations are reversible, the \(n + m \choose m\) unique dictionaries must have identical solution sets. It must also be the case that each basis is associated with a unique dictionary. To see this, let
and
be two dictionaries associated with the same basis \(\mathcal{B}\). Let \(j^{*} \in \mathcal{N}\) and consider the solution obtained by setting \(x_{j^{*}} = t\) and \(x_{j \in \mathcal{N} \setminus j^{*}} = 0\). Since (5) and (6) have identical solution sets,
Notice that as long as the value \(t\) takes on does not violate the constraints, the resulting solution is feasible. Setting \(t = 0\) reveals \(\tilde{\nu} = \hat{\nu}\) and \(\tilde{b}_i = \hat{b}_i \forall i \in \mathcal{B}\). Consequently, setting \(t\) to any positive value restricts \(\tilde{c}_{ij^{*}} = \hat{c}_{ij^{*}}\) and \(\tilde{a}_{ij^{*}} = \hat{a}_{ij^{*}} \forall i \in \mathcal{B}\). Repeating this argument for all \(j \in \mathcal{N}\) demonstrates that (5) and (6) are identical dictionaries; thus, each basis gives rise to a unique dictionary.
Since there are a finite number of unique bases, the simplex method cannot deterministically pivot indefinitely unless there exists a repeating sequence of dictionaries i.e. a cycle.
The simplex algorithms can only cycle in the presence of degeneracy.¶
Let \(D_1, D_2, \ldots, D_N\) denote the cycle of dictionaries in question with the corresponding \(\zeta_1, \zeta_2, \ldots, \zeta_N\). By the definition of a cycle, \(\zeta_1 = \zeta_{N + 1}\). Since the pivoting rule seeks to maximize the objective function in a nondecreasing manner,
Therefore, \(\zeta_i = \zeta_j\) for \(1 \leq i < j \leq N\). Consequently, \(b_l = 0\), \(x_l = 0\), and \(x_e = 0\). Thus, each of the pivots taking \(D_i\) to \(D_j\) is necessarily degenerate for \(1 \leq i < j \leq N\), and each of the dictionaries \(D_1, D_2, \ldots, D_N\) must be degenerate.
Notice that the previous degeneracy conditions can be defined more explicitly as
A dictionary is degenerate if one or more of the basic variables is set to zero.
A pivot is degenerate if one of the ratios in the calculation of the leaving variable is \(+\infty\) i.e. if the numerator is positive and the denominator vanishes.
Exercise 3.1¶
Initial feasible solution:
Choose \(x_1\) and \(w_2\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(x_3\) and \(w_3\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
The last dictionary is optimal, so dropping the perturbations results in
Exercise 3.2¶
Initial feasible solution:
Choose \(x_1\) and \(w_1\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(x_2\) and \(w_2\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(x_3\) and \(x_1\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(x_4\) and \(x_2\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(w_1\) and \(x_3\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(x_1\) and \(x_4\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Choose \(x_3\) and \(w_3\) as the entering and leaving variable respectively where
Update the current dictionary’s feasible solution to
Pivot dictionary to
Exercise 3.3¶
The previous exercises already gave enough practice.
Exercise 3.4¶
Rewriting the standard form LP with slack variables yields
If all \(c_j \leq 0\) (i.e. the set of entering variables is empty), the BFS is optimal. Suppose there exists some \(x_{e \in \mathcal{N}}\) such that \(c_e > 0\).
If all \(a_{ie} \leq 0\) (i.e. the set of leaving variables is empty), \(x_e\) can be chosen to be arbitrarily large without violating the constraints, which makes the problem feasible but unbounded. Further suppose there exists some \(x_{l \in \mathcal{B}}\) such that \(a_{le} > 0\).
Pivoting according to Bland’s rule would set
where \(\mathcal{N}' = N \cup \{ l \} \setminus \{ e \}\) and \(a_{ll} = 1\). From inspection, the initial BFS is optimal when subsequent pivots and dictionaries are degenerate.
Suppose the pivots and dictionaries are nondegenerate. There must exist a pivot that serves as the transition from degenerate to nondegenerate. Let \(x_e\) and \(x_l\) respectively denote the entering and leaving variable for that pivot. Recall that a nondegenerate pivot means \(\zeta_t < \zeta_{t + 1}\) and a nondegenerate dictionary requires \(x_i > 0\) for all \(i \in \mathcal{B}\). This means \(c_e x_e > 0\) and \(-a_{ie} x_e > 0\). As a consequence of \(c_e > 0\), \(x_e > 0\) and \(a_{ie} < 0\). Since all the nonbasic variables had a value of zero on iteration \(t\) and the simplex algorithm will assign \(x_l = 0\) on iteration \(t + 1\), \(x_e = 0\). Thus, the subsequent pivots and dictionaries are necessarily degenerate.
Exercise 3.5¶
Graphing the feasible region shows that the LP is unbounded.
[1]:
from sympy import symbols
from sympy import plot_implicit, And
x1, x2 = symbols('x_1 x_2')
c1 = -2 * x1 <= -5
c2 = And(c1, x1 >= 0)
plot_implicit(c2, (x1, -1, 10), (x2, -10, 10),
title='Feasible Region', xlabel='$x_1$', ylabel='$x_2$');
<Figure size 640x480 with 1 Axes>
Exercise 3.6¶
Remember that the pivot step changes only the basic variables, \(\zeta\), \(x_e\), and \(x_l\). Since the non-basic variables still take on the value of zero and \(\zeta\) is irrelevant for this proof, (4) simplifies to
When \(a_{ie} \leq 0\), \(x_i \geq b_i \geq 0\). Assuming the initial dictionary is nondegenerate, \(x_i \geq b_i > 0\).
When \(a_{ie} > 0\), the minimum ratio test requires
Assuming there is never a tie for the choice of leaving variable, \(b_i > a_{ie} \frac{b_l}{a_{le}}\). Therefore, a pivot step gives a nondegenerate dictionary if it starts with a nondegenerate dictionary and has no tie for leaving variable. Since the simplex method can only cycle in the presence of degeneracy, this LP cannot have a cycle.
Exercise 3.7¶
(a)¶
(b)¶
(c)¶
References
- Bura
Jim Burke. Does the simplex algorithm work? https://www.math.washington.edu/ burke/crs/407/notes/section3.pdf. Section 3.1 accessed on 2016-11-01.
- Burb
Jim Burke. Solving lps: the simplex algorithm of george dantzig. https://www.math.washington.edu/ burke/crs/407/notes/section2.pdf. Section 2.3 accessed on 2016-11-01.
- Gab
Hal Gabow. Csci 5654: linear programming notes. https://www.cs.colorado.edu/ hal/565notes.pdf. Page 31 accessed on 2016-11-01.