2.2.1 Primal Degeneracy
Primal degeneracy is caused by the presence of weakly redundant constraints, i.e. constraints that are redundant yet intersect with the feasible parameter space (see Chapter 1.3). In particular, the space where the weakly redundant constraints hold as equality is lower‐dimensional with respect to the overall feasible parameter space. Thus, it is clear that if any weakly redundant constraint is chosen as an element of the active set, then the resulting critical region will be lower‐dimensional.4 As a consequence, from all possible combinations of active sets at a given solution, only one active set
2.2.2 Dual Degeneracy
In general, the effect of primal degeneracy onto the solution of mp‐LP problems is manageable, since it can be detected by solving a single LP problem for each candidate active set combination. However, dual degeneracy is much more challenging as the different active sets may result in full‐dimensional, but overlapping, critical regions. In particular since the optimal solutions
Remark 2.4
Dual degeneracy results from the non‐uniqueness of the optimal solution
However, in order to generate continuous optimizers as well as non‐overlapping critical regions, three different approaches have been developed:
Reformulation to an mp‐QP problem [1]: The key idea is to reformulate the mp‐LP problem (2.2) into an mp‐QP problem (3.2), which yields the same solution at the considered point. Since mp‐QP problems do not encounter dual degeneracy due to the inherently unique nature of their optimizers, the continuity of the optimizer can be guaranteed.
Graph/Cluster evaluation [2,3]: In [2], it was shown that the solution to an mp‐LP problem is given by a connected graph, where the nodes are the different active sets and the connections are given by the application of a single step of the dual simplex algorithm. In addition, [3] considers the dual of the mp‐LP problem as a parametrized vertex problem and identifies clusters of connected vertices equivalent to the connections in [2]. When dual degeneracy occurs, multiple disconnected graphs/clusters can occur, only some of which may represent the continuous solution of the mp‐LP problem across the entire feasible parameter space [3].
Lexicographic perturbation [4]: The problem of dual‐degeneracy only arises because of the specific numerical structure of the objective function and the constraints. 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