Monday, February 4 2019

12:30pm - 1:30pm

12:30pm - 1:30pm

Operations Research Seminar

Using n-dimensional volume to compare alternative convexification

methods in mixed-integer nonlinear optimization problems

methods in mixed-integer nonlinear optimization problems

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 modelled effectively. Due in part to their generality (and therefore wide applicability), MINLO problems are very difficult in general, and consequently, the best way 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.

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 demonstrate that analytic results are indeed obtainable for certain sBB implementation decisions. In particular, we use volume as a geometric measure to compare alternative convex relaxations. We consider different choices for convexifying the graph of a trilinear monomial, 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 and therefore provide analytic results to guide sBB implementation decisions.

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 demonstrate that analytic results are indeed obtainable for certain sBB implementation decisions. In particular, we use volume as a geometric measure to compare alternative convex relaxations. We consider different choices for convexifying the graph of a trilinear monomial, 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 and therefore provide analytic results to guide sBB implementation decisions.

Speaker: | Emily Speakman |

Affiliation: | Otto-von-Guericke-University Magdeburg |

Location: | SCB 4125 |

Done