Disjunctive programming: Properties of the convex hull of feasible points

In this paper we characterize the convex hull of feasible points for a disj unctive program, a class of problems which subsumes pure and mixed integer programs and many other nonconvex programming problems. Two representations are given for the convex hull of feasible points, each of which provides l inear programming equivalents of the disjunctive program. The first one inv olves a number of new variables proportional to the number of terms in the disjunctive normal form of the logical constraints; the second one involves only the original variables and the facets of the convex hull. Among other results, we give necessary and sufficient conditions for an inequality to define a facet of the convex hull of feasible points. For the class of disj unctive programs that we call facial, we establish a property which makes i t possible to obtain the convex hull of points satisfying n disjunctions, i n a sequence of n steps, where each step generates the convex hull of point s satisfying one disjunction only. 1998 Published by Elsevier Science B.V. All rights reserved.