A geometric way to build strong mixed-integer programming formulations

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.

• Algorithms and Theory