if is a ‐dimensional polytope.
Let and be two adjacent polytopes. Then the facet‐to‐facet property is said to hold if is a facet of both and (see Figure 1.2 for an illustration).
Let be an ‐dimensional polytope. Then, there exists a series of vertices such that(1.25)
Eq. (1.23) is referred to the halfspace (or H) representation, while Eq. (1.25) denotes the vertex (or V) representation. The process of moving from the halfspace to the vertex representation is referred to as vertex enumeration.
The Chebyshev center of a polytope is given as the largest Euclidean ball that lies in a polytope [2]. It can be determined by solving the following linear programming (LP) problem:(1.26) where the solution denotes the radius of the largest Euclidean ball. Based on the solution of problem (1.26), the following conclusions can be drawn:– Problem (1.26) is infeasible: The polytope is empty.– : The polytope is lower‐dimensional.– : The polytope is full‐dimensional.
Figure 1.2 A schematic representation of the differences between two polytopes
1.3.1 Approaches for the Removal of Redundant Constraints
A concept that is very important in multi‐parametric programming is the aspect of redundancy:
Theorem 1.2 ([3])
Consider an
Additionally, a constraint
Remark 1.3
A constraint is called weakly redundant if it is redundant but not strongly redundant, i.e. Eq. (1.27) but not Eq. (1.28) holds. A schematic representation of weakly and strongly redundant constraints is shown in Figure 1.3.
If a polytope
Figure 1.3 A schematic representation of (a) strongly and (b) weakly redundant constraints.
Consider an
Remark 1.4
Here, two of the most common approaches used are reported. The field of the removal of redundant constraints has been widely studied, and its review is beyond the scope of this book. The reader is referred to [3,4] for an interesting treatment of the matter.
1.3.1.1 Lower‐Upper Bound Classification
Given the bounds
(1.29)
where
(1.30)
where
(1.31)
1.3.1.2 Solution of Linear Programming Problem
Consider the following constraint‐specific version of problem (1.26):
where
