Polyhedral annexation in mixed integer and combinatorial programming

Polyhedral annexation is a new approach for generating all valid inequalities in mixed integer and combinatorial programming. These include the facets of the convex hull of feasible integer solutions. The approach is capable of exploiting the characteristics of the feasible solution space in regions both “adjacent to” and “distant from” the linear programming vertex without resorting to specialized notions of group theory, convex analysis or projective geometry. The approach also provides new ways for exploiting the “branching inequalities” of branch and bound.