Emily Speakman (OVGU Magdeburg)
Monday, February 26, 2018 - 14:30
Zuse Institute Berlin
Takustrasse 7, 14195 Berlin, 2006, EG
Spatial branch-and-bound (sBB) is the workhorse algorithmic framework used to globally solve mixed-integer non-linear optimization (MINLO) problems. 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: a trilinear monomial. In particular, we use volume as a geometric measure to compare different convex relaxations for trilinear monomials. We consider different choices for convexifying the graph of a triple product (i.e. f = x1x2x3) over a box domain, 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. In addition, we use the volume measure to provide guidance regarding branching-point selection in the implementation of sBB. This is joint work with Jon Lee (University of Michigan).
submitted by Julia Eichhorn (eichhorn@zib.de)