Polyhedral annexation

From Glossary

Jump to: navigation, search

This is a cutting plane approach to find an optimal solution known to lie at an extreme point of a polyhedron, LaTeX: P. The general algorithm is to start at some extreme point and solve the polyhedral annexation problem. This will result in ascertaining that the extreme point is (globally) optimal, or it will generate a recession direction from which a convexity cut is used to exclude the extreme point. The approach generates a sequence of shrinking polyhedra by eliminating the cut region. Its name comes from the idea of annexing a new polyhedron to exclude from the original, homing in on the extreme point solution.


When applied to reverse convex programming, the convex set LaTeX: (S) in the polyhedral annexation problem is the objective level set, LaTeX: \{x: f(x) \le f(x^*)-t\}, where LaTeX: {t} > 0 is an optimality tolerance, and LaTeX: x^* is the best (extreme point) solution so far. The initial polyhedron is the feasible region, so this is an inner approximation strategy.

When applied to mixed integer programming, the original polyhedron is the LP relaxation, and the convex set LaTeX: (S) for the polyhedral annexation problem can vary according to the particular problem (exploiting structure, especially to find facets of the feasible region).

Personal tools