Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

Jon Lee, Daphne Skipper, Emily Speakman

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area, we do give a few new results, and we provide many directions for further work.

Original languageEnglish (US)
Pages (from-to)121-140
Number of pages20
JournalMathematical Programming
Issue number1
StatePublished - Jul 1 2018


  • Boolean quadric
  • Facility location
  • Fixed charge
  • Global optimization
  • Mixed-integer nonlinear optimization
  • Monomial
  • Polytope
  • Spatial branch-and-bound
  • Vertex packing
  • Volume

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations'. Together they form a unique fingerprint.

Cite this