Volumetric Guidance for Handling Triple Products in Spatial Branch-and-Bound

Abstract

Spatial branch-and-bound (sBB) is the workhorse algorithmic framework used to globally solve mathematical mixed-integer non-linear optimization (MINLO) problems. Formulating a problem using this paradigm allows both the non-linearities of a system and any discrete design choices to be modeled effectively. Because of the generality of this approach, MINLO is used in a wide variety of applications, from chemical engineering problems and network design, to medical applications and problems in the airline industry.

Due in part to their generality (and therefore wide applicability), MINLO problems are very difficult in general, and consequently, the best ways to implement many details of sBB are not wholly understood. In this work, we provide analytic results guiding the implementation of sBB for a simple but frequently occurring function ‘building block’. As opposed to computationally demonstrating that our techniques work only for a particular set of test problems, we analytically establish results that hold for all problems of the given form. In this way, we also demonstrate that analytic results are indeed obtainable for certain sBB implementation decisions.

In particular, we use volume as a geometric measure to compare different convex relaxations for functions involving trilinear monomials (or any three quantities multiplied together). We consider different choices for convexifying the graph of a triple product, and obtain formulae for the volume (in terms of the variable upper and lower bounds) for each of these convexifications. We are then able to order the convexifications with regard to their volume. We also provide computational evidence to support our choice of volume as an effective comparison measure, and show that in the context of triple products, volume is an excellent predictor of the objective function gap. Finally, we use the volume measure to provide guidance regarding branching-point selection in the implementation of sBB.