Disjunctive programming and relaxations of polyhedra

Abstract

Given a polyhedron L with h facets, whose interior contains no integral points, and a polyhedron P, recent work in integer programming has focused on characterizing the convex hull of P minus the interior of L. We show that to obtain such a characterization it suffices to consider all relaxations of P defined by at most n(h−1) among the inequalities defining P. This extends a result by Andersen, Cornuéjols, and Li.