Google Research

A geometric way to build strong mixed-integer programming formulations

Operations Research Letters, vol. 47 (2019), pp. 601-606

Abstract

We give an explicit geometric way to build ideal mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of the normal directions of all hyperplanes spanned (in a r-dimensional linear space) by a set of directions determined by the extreme points shared among the alternatives. The resulting MIP formulation is ideal, and has exactly r integer variables and 2 x (# of spanning hyperplanes) general inequality constraints. We use this result to derive novel logarithmic-sized ideal MIP formulations for discontinuous piecewise linear functions and the annulus constraint arising in robotics and power systems problems.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work