Optimization Online


Quantifying Double McCormick

Jon Lee (jonxlee***at***umich.edu)
Emily Speakman (eespeakm***at***umich.edu)

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

Category 1: Global Optimization (Theory )

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )


Download: [PDF]

Entry Submitted: 08/12/2015
Entry Accepted: 08/14/2015
Entry Last Modified: 01/24/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society