Journal
MATHEMATICAL PROGRAMMING
Volume 169, Issue 2, Pages 377-415Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-017-1138-3
Keywords
Convex hull; Nonlinear knapsack sets; Lifting; Projection; Bilinear sets; Explicit descriptions
Categories
Funding
- NSF CMMI Grants [0856605, 0900065, 1234897, 1235236]
- Directorate For Engineering
- Div Of Civil, Mechanical, & Manufact Inn [0900065] Funding Source: National Science Foundation
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [0856605, 1234897, 1235236] Funding Source: National Science Foundation
Ask authors/readers for more resources
We consider convex hull descriptions for certain sets described by inequality constraints over a hypercube and propose a lifting-and-projection technique to construct them. The general procedure obtains the convex hulls as an intersection of semi-infinite families of linear inequalities, each derived using lifting techniques that are interpreted using convexification tools. We demonstrate that differentiability and concavity of certain perturbation functions help reduce the number of inequalities needed for this characterization. Each family of inequalities yields a few linear/nonlinear constraints fully characterized in the space of the original problem variables, when the projection problems are amenable to a closed-form solution. In particular, we illustrate the complete procedure by constructing the convex hulls of the subsets of a compact hypercube defined by the constraints x(1)(b1) x(2)(b2) >= x(3)and x(1)x(2)(b2) <= x(3), where b(1), b(2) >= 1. As a consequence, we obtain a closed-form description of the convex hull of the bilinear equality x(1)x(2)=x(3), in the presence of variable bounds, as an intersection of a few linear and nonlinear inequalities. This explicit characterization, hitherto unknown, can improve relaxation techniques for factorable functions, which utilize this equality to relax products of functions with known 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