Journal
MATHEMATICAL PROGRAMMING
Volume 124, Issue 1-2, Pages 481-512Publisher
SPRINGER
DOI: 10.1007/s10107-010-0374-6
Keywords
-
Categories
Funding
- NSF [CMMI 0900065, 0856605]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [0856605] Funding Source: National Science Foundation
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [0900065] Funding Source: National Science Foundation
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available