Strong Valid Inequalities for Orthogonal Disjunctions and Polynomial Covering Sets

In this paper, we develop a convexification tool that enables construction of convex hulls for orthogonal disjunctive sets using convex extensions and disjunctive programming techniques. A distinguishing feature of our technique is that, unlike most applications of disjunctive programming, it does not require the introduction of new variables in the relaxation. We develop and apply a toolbox of results that help in checking the technical assumptions under which the convexification tool can be employed. We demonstrate its applicability in integer programming by deriving the intersection cut for mixed-integer polyhedral sets and the convex hull of certain mixed/pure-integer bilinear sets. We then develop a key result that extends the applicability of the convexification tool to relaxing nonconvex inequalities, which are not naturally disjunctive, by providing sufficient conditions for establishing the convex extension property over the non-negative orthant. Then, we illustrate the convexification tool by developing convex hulls for certain polynomial covering sets with non-negative variables. We specialize the results to bilinear covering sets and use them to derive a tight relaxation of the bilinear covering sets over a hypercube. We use the orthogonally disjunctive characterization to show that the derived relaxation is at least as tight as the standard factorable relaxation for the same inequality, and derive necessary and sufficient conditions under which it is strictly tighter. Finally, we present a preliminary computational study on a set of randomly generated bilinear covering sets that indicates that the derived relaxation is substantially tighter than the factorable relaxation.