Deriving convex hulls through lifting and projection

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

Research output: Contribution to journalArticlepeer-review

6 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
Externally publishedYes

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