ORIE Colloquium

Juan Pablo VielmaMIT
Nonlinear mixed integer programming formulations

Tuesday, November 28, 2017 - 4:15pm
Rhodes 253

Linear mixed integer programming (MIP) is an indispensable tool in Operations Research. However, it is often useful to additionally incorporate discrete variables into nonlinear models to better represent intricate optimization problems. This leads to nonlinear MIP and in particular to mixed integer convex optimization (MICONV), which results from adding discrete variables to a convex optimization problem. While more restrictive than general nonlinear MIP, MICONV already has a wide range of applications and they can be significantly easier to solve than general nonlinear MIP.

Similar to linear MIP, there are many MICONV formulation techniques and their characteristics can have a strong effect on solve times. Unfortunately, our understanding of MICONV formulations is significantly more limited than that of linear MIP formulations. In this talk we explore two topics on MICONV formulations. The first topic concerns what can be modeled or represented with MICONV and is joint work with Miles Lubin and Ilias Zadik. Here we give necessary and sufficient conditions for MICONV representability under various restrictions. The second part concerns the construction of small and strong MICONV formulations for unions of convex sets. Here we describe a geometric construction technique and consider the algebraic representability of the resultant formulations.