LITMIR.BIZ

Figure 2.3 A schematic representation of the connected‐graph theorem, (a) from a geometrical viewpoint, i.e. considering the a geometric interpretation of the feasible parameter space , and (b) from an active set viewpoint, where the dual pivot can be identified in the transition between the active sets associated with the critical regions. Note that although and have the point in common, i.e. “ and are both optimal active sets” (Definition 2.1), it is not possible to pass from to in a single step of the dual simplex algorithm. Thus, and are not connected.

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 and . However, in the case of degeneracy or identical constraints, this may not necessarily be the case. While the case of identical constraints can be handled directly, the issue of degeneracy has to be considered in more detail and is discussed in Chapter 2.2.

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 is unique. This uniqueness can only be guaranteed if the solution of the LP problem is non‐degenerate. In general, degeneracy refers to the situation where the LP problem under consideration has a specific structure, which does not allow for the unique identification of the active set .3 Commonly, the two types of degeneracy encountered are primal and dual degeneracy (see Figure 2.4):