Quantifying Double McCormick

Emily Speakman () and Jon Lee ()
Additional contact information
Emily Speakman: University of Michigan, Ann Arbor, Michigan 48109
Jon Lee: University of Michigan, Ann Arbor, Michigan 48109

Mathematics of Operations Research, 2017, vol. 42, issue 4, 1230-1253

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.

Keywords: global optimization; mixed-integer nonlinear programming; spatial branch and bound; convexification; bilinear; trilinear; McCormick inequalities (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0846 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:4:p:1230-1253

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().