A geometric way to build strong mixed-integer programming formulations

2018/11/22 by Huchette, Joey, Vielma, Juan Pablo
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1811.10409

Abstract

We give an explicit geometric way to build mixed-integer programming (MIP) formulations for unions of polyhedra. The construction is simply described in terms of spanning hyperplanes in an r-dimensional linear space. The resulting MIP formulation is ideal, and uses 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 structures appearing in robotics and power systems problems.

Related

• Embedding Formulations and Complexity for Unions of Polyhedra
• Lifting Linear Extension Complexity Bounds to the Mixed-Integer Setting
• Mixed Integer Linear Programming Formulation Techniques
• A mixed-integer branching approach for very small formulations of disjunctive constraints
• Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding