# A geometric way to build strong mixed-integer programming formulations

arXiv: https://arxiv.org/abs/1811.10409 · HTML: https://mlsanity.com/paper/1811.10409/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2018.

## Built on by (most cited first, 3 of 3)

- [Mixed integer linear optimization formulations for learning optimal binary classification trees](https://mlsanity.com/paper/2206.04857/) (2022)
- [Computation of Least Trimmed Squares: A Branch-and-Bound framework with Hyperplane Arrangement Enhancements](https://mlsanity.com/paper/2604.11584/) (2026)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

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.