In order to overcome the degeneracy, the right‐hand side of the constraints as well as the objective function are symbolically perturbed in order to obtain a single, continuous optimizer for the solution of the mp‐LP problem. Note that the problem is not actually perturbed, but only the result of a proposed perturbation is analyzed enabling the formulation of a continuous optimizer.
2.2.3 Connections Between Degeneracy and Optimality Conditions
Lastly, it is important to highlight that the impact of degeneracy on mp‐LP problems goes beyond the derivation of more sophisticated solution strategies. In fact, the presence of primal and dual degeneracy can be directly linked to the optimality conditions required for the calculation of the parametric solution. In the following text, each optimality condition required for the basic sensitivity theorem is revisited with the consideration of the presence of degeneracy.
Second‐order sufficient conditions (SOSC): This condition states that the second derivative of the Lagrange function with respect to the optimization variables has to be positive semi‐definite. For mp‐LP (and convex mp‐QP) problems, this condition is naturally satisfied.
Linear Independence Constraint Qualification (LICQ): This condition states that the matrix in Eq. (2.4a) has to have rank , i.e. there cannot be linearly dependent constraints within the active set. Consider now the case of primal degeneracy, where the number of candidate constraints for the active set , i.e. more than constraints are active at the optimal solution. Clearly, the matrix cannot have full rank, since the maximum rank is as . As a result, the occurrence of primal degeneracy can be viewed as a LICQ violation at the optimal solution.
Strict Complementary Slackness (SCS): This condition states that there cannot exist a constraint such that and . In particular, consider that the Lagrange multiplier can be viewed as a “cost” incurred in the objective function when moving along a given constraint. However, dual degeneracy inherently implies that there are multiple points along the same constraints that have the same optimal objective function and thus, this “cost” is equal to 0 (see Figure 2.4 b). Hence, the presence of dual degeneracy is directly linked to the violation of the SCS property, as dual degeneracy implies that there exists at least one constraint such that and .
2.3 Critical Region Definition
In linear programming (LP), the term “basic solution” is a result of the use of the simplex algorithm and identifies the solution as a vertex of the feasible space, which is uniquely defined by the indices of the constraints that form the vertex. However, with the emergence of interior‐point methods, as well as in the face of degeneracy, it cannot be guaranteed that the solution obtained from an LP solver is a basic solution leading to a full‐dimensional critical region. As the classical definition of the critical region is directly tied to the active set (i.e. the indices of the constraints that form the vertex), alternative definitions of critical regions have been considered.
The main theme is thereby to identify an appropriate invariancy set over the parametric space. The three sets typically considered are the following [5]:
Optimal basis invariancy [6]: This invariancy refers to the classical definition of the critical region as a set of active constraints that form a basic solution. The main issue with this approach occurs in the case of degeneracy (see section 2.2), which might lead to lower‐dimensional or overlapping regions.
Support set invariancy [7–9]: Given the LP problem formulation(2.14) the support set is defined as . The concept of support set invariancy describes the region of the parameter space for which the same support set remains optimal. It can be shown that this eliminates the issue of degeneracy, as the support set is independent of the active constraints.
Optimal partition invariancy [8, 10–12]: The optimal partition is given by the cone, which is spanned from the solution found in the directions of the inactive constraints.
2.4 An Example: Chicago to Topeka
In order to illustrate the concepts developed in this chapter, a classical shipping problem is considered (adapted from [13] and modified for illustrative purposes):
Given a set of plants
In particular, the transport to Chicago and Topeka is considered, and the problem‐specific data is given in Tables 2.1 and 2.2. Note that the freight cost is $90 per 1000 miles and case and the freight loading cost is $25 per case.
Table 2.1 The supply and demand of each plant and market in cases.
| Supply | Demand | ||
|---|---|---|---|
| Seattle | 350 | Chicago | 300 |
| San Diego | 600 | Topeka | 275 |
Table 2.2 The distances between each plant and market in thousands of miles.
| ‐ | Chicago | Topeka |
|---|---|---|
| Seattle | 1.7 | 1.8 |
| San Diego | 1.8 | 1.4 |
2.4.1 The Deterministic Solution
Equivalently to the beginning of this chapter, we first consider the uncertainty‐free case. Then, the overall transportation cost per case is determined by
where
