Quantifying double McCormick
From MaRDI portal
Publication:4595965
DOI10.1287/MOOR.2017.0846zbMATH Open1386.90121arXiv1508.02966OpenAlexW2951623144MaRDI QIDQ4595965FDOQ4595965
Authors: Emily Speakman, Jon Lee 
Publication date: 7 December 2017
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Abstract: When using the standard McCormick inequalities twice to convexify trilinear monomials, as is often the practice in modeling and software, there is a choice of which variables to group first. For the important case in which the domain is a nonnegative box, we calculate the volume of the resulting relaxation, as a function of the bounds defining the box. In this manner, we precisely quantify the strength of the different possible relaxations defined by all three groupings, in addition to the trilinear hull itself. As a by product, we characterize the best double McCormick relaxation. We wish to emphasize that, in the context of spatial branch-and-bound for factorable formulations, our results do not only apply to variables in the input formulation. Our results apply to monomials that involve auxiliary variables as well. So, our results apply to the product of any three (possibly complicated) expressions in a formulation.
Full work available at URL: https://arxiv.org/abs/1508.02966
Recommendations
- On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
- Experimental validation of volume-based comparison for double-McCormick relaxations
- Some results on the strength of relaxations of multilinear functions
- Trilinear monomials with mixed sign domains: Facets of the convex and concave envelopes
- scientific article; zbMATH DE number 2068068
global optimizationbilinearmixed-integer nonlinear programmingconvexificationspatial branch and boundtrilinearMcCormick inequalities
Cited In (14)
- A new framework to relax composite functions in nonlinear programs
- Gaining or losing perspective
- The convex hull of a quadratic constraint over a polytope
- Volume computation for sparse Boolean quadric relaxations
- On branching-point selection for trilinear monomials in spatial branch-and-bound: the hull relaxation
- A conic relaxation model for searching for the global optimum of network data envelopment analysis
- Experimental validation of volume-based comparison for double-McCormick relaxations
- On linear programming relaxations for solving polynomial programming problems
- Extrapolating curvature lines in rough concept sketches using mixed-integer nonlinear optimization
- Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes
- Error bounds for monomial convexification in polynomial optimization
- Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations
- Using two-dimensional projections for stronger separation and propagation of bilinear terms
- Erratum to: ``Multivariate McCormick relaxations
This page was built for publication: Quantifying double McCormick
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595965)
