alt="images"/> and The proof of Theorem 2.2 is based on the statement that only a single currently inactive constraint limits the solution of the p‐LP problem resulting from the substitution of the parametrized line segment joining
2.2 Degeneracy
The properties described in the previous section are based on the assumption that the active set of the LP problem solved at
Primal degeneracy: In this case, the vertex of the optimal solution of the LP is overdefined, i.e. there exist multiple sets such that(2.11) where, based on Eq. (2.3a):(2.12)
Dual degeneracy: If there exists more than one point, which attains the optimal objective function value, then the optimal solution is not unique. Thus, there exist multiple sets with such that(2.13) where . Note that as shown in Figure 2.4, the solution of the problem does not necessarily have to be a vertex, and thus, Eq. (2.12) does not have to hold.
Figure 2.4 Primal and dual degeneracy in linear programming. In (a), primal degeneracy occurs since there are three constraints that are active at the solution, while in (b) dual degeneracy occurs since there is more than one point
While any solution
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
