 Research Overview: a selection of recent projects

Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes.

Here we introduce an alternative method for computing this convex-hull volume, making use of the rich theory of mixed volumes. This new method leads to a more natural approach for considering extensions of the problem.

To view click here: Speakman_Averkov_MixedVolume.pdf

Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations

This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. However, besides surveying the area, we do give a few new results, and we provide many directions for further work.

To view click here.

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.

To view click here.

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).