Deriving convex hulls through lifting and projection

Trang T. Nguyen, Jean Philippe P. Richard, Mohit Tawarmalani

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

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 x1b1x2b2≥x3 and x1x2b2≤x3, where b1, b2≥ 1. As a consequence, we obtain a closed-form description of the convex hull of the bilinear equality x1x2= x3, 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.

Original languageEnglish (US)
Pages (from-to)377-415
Number of pages39
JournalMathematical Programming
Volume169
Issue number2
DOIs
StatePublished - Jun 1 2018

Bibliographical note

Funding Information:
The authors wish to thank the two referees and an associate editor for their suggestions, which have led to improvements in the presentation and structure of the paper. This work was supported by NSF CMMI Grants 0856605, 0900065, 1234897, and 1235236.

Funding Information:
This work was supported by NSF CMMI Grants 0856605, 0900065, 1234897, and 1235236.

Publisher Copyright:
© 2017, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

Keywords

  • Bilinear sets
  • Convex hull
  • Explicit descriptions
  • Lifting
  • Nonlinear knapsack sets
  • Projection

Fingerprint

Dive into the research topics of 'Deriving convex hulls through lifting and projection'. Together they form a unique fingerprint.

Cite this