Research Overview

Quantifying Double McCormick

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.

Published online in Mathematics of Operations Research, to view click here.

Volumetric sBB branching-point selection for trilinear monomials

The case of having three or more expressions multiplied together (each expression being possibly complex itself) occurs frequently in global-optimization models. For these “trilinear terms,” we present some analytic results regarding the choice of branching point and branching variable in the context of spatial branch-and-bound. In obtaining the “best” branching point or variable we use n-dimensional volume as a comparison measure and we also compare our results to common practice in software.

Preliminary announcement (4 pages) in the Proceedings of GOW 2016.

Experimental substantiation of using volume for comparing Double McCormick relaxations

In this project, we are performing some computational experiments designed to test our theoretical results.  We experimentally substantiate the relevance of our results to the practice of global optimization, by applying them to difficult box cubic problems (boxcup). In doing so, we find that using the volume formulae, we can accurately predict the quality of a relaxation for boxcups based on the (box) parameters defining the feasible region.

To view the paper on ArXiv click here, (to appear in: the Proceedings of CPAIOR 2017, Springer Lecture Notes in Computer Science series).