TY - JOUR
T1 - Strong valid inequalities for orthogonal disjunctions and bilinear covering sets
AU - Tawarmalani, Mohit
AU - Richard, Jean Philippe P.
AU - Chung, Kwanghun
N1 - Copyright:
Copyright 2010 Elsevier B.V., All rights reserved.
PY - 2010/7
Y1 - 2010/7
N2 - In this paper, we derive a closed-form characterization of the convex hull of a generic nonlinear set, when this convex hull is completely determined by orthogonal restrictions of the original set. Although the tools used in this construction include disjunctive programming and convex extensions, our characterization does not introduce additional variables. We develop and apply a toolbox of results to check the technical assumptions under which this convexification tool can be employed. We demonstrate its applicability in integer programming by providing an alternate derivation of the split cut for mixed-integer polyhedral sets and finding the convex hull of certain mixed/pure-integer bilinear sets. We then extend the utility 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. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant. Although we illustrate our results primarily on bilinear covering sets, they also apply to more general polynomial covering sets for which they yield new tight relaxations.
AB - In this paper, we derive a closed-form characterization of the convex hull of a generic nonlinear set, when this convex hull is completely determined by orthogonal restrictions of the original set. Although the tools used in this construction include disjunctive programming and convex extensions, our characterization does not introduce additional variables. We develop and apply a toolbox of results to check the technical assumptions under which this convexification tool can be employed. We demonstrate its applicability in integer programming by providing an alternate derivation of the split cut for mixed-integer polyhedral sets and finding the convex hull of certain mixed/pure-integer bilinear sets. We then extend the utility 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. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant. Although we illustrate our results primarily on bilinear covering sets, they also apply to more general polynomial covering sets for which they yield new tight relaxations.
UR - http://www.scopus.com/inward/record.url?scp=77955171103&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77955171103&partnerID=8YFLogxK
U2 - 10.1007/s10107-010-0374-6
DO - 10.1007/s10107-010-0374-6
M3 - Article
AN - SCOPUS:77955171103
SN - 0025-5610
VL - 124
SP - 481
EP - 512
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -