Mohit Tawarmalani Jean-Philippe P. Richard Kwanghun Chung
Abstract
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.
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.