# Between steps: Intermediate relaxations between big-M and convex hull formulations

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 41 references that are in the map.
- First posted on arXiv 29 Jan 2021.

## Builds on (most cited first, 5 of 5)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Lossless Compression of Deep Neural Networks](https://mlsanity.com/paper/2001.00218/) (2020)
- [ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs](https://mlsanity.com/paper/1907.03140/) (2019)
- [Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding](https://mlsanity.com/paper/1704.03954/) (2017)

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

- [Partition-based formulations for mixed-integer optimization of trained ReLU neural networks](https://mlsanity.com/paper/2102.04373/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [OMLT: Optimization & Machine Learning Toolkit](https://mlsanity.com/paper/2202.02414/) (2022)
- [PySCIPOpt-ML: Embedding Trained Machine Learning Models into Mixed-Integer Programs](https://mlsanity.com/paper/2312.08074/) (2023)
- [P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints](https://mlsanity.com/paper/2202.05198/) (2022)
- [Feed-Forward Neural Networks as a Mixed-Integer Program](https://mlsanity.com/paper/2402.06697/) (2024)
- [Model-based feature selection for neural networks: A mixed-integer programming approach](https://mlsanity.com/paper/2302.10344/) (2023)
- [Formal Verification of Markov Processes with Learned Parameters](https://mlsanity.com/paper/2501.15767/) (2025)
- [A cutting plane algorithm for globally solving low dimensional k-means clustering problems](https://mlsanity.com/paper/2402.13595/) (2024)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [Situational-Constrained Sequential Resources Allocation via Reinforcement Learning](https://mlsanity.com/paper/2506.14125/) (2025)

## Abstract (arXiv)

This work develops a class of relaxations in between the big-M and convex hull formulations of disjunctions, drawing advantages from both. The proposed "P-split" formulations split convex additively separable constraints into P partitions and form the convex hull of the partitioned disjuncts. Parameter P represents the trade-off of model size vs. relaxation strength. We examine the novel formulations and prove that, under certain assumptions, the relaxations form a hierarchy starting from a big-M equivalent and converging to the convex hull. We computationally compare the proposed formulations to big-M and convex hull formulations on a test set including: K-means clustering, P_ball problems, and ReLU neural networks. The computational results show that the intermediate P-split formulations can form strong outer approximations of the convex hull with fewer variables and constraints than the extended convex hull formulations, giving significant computational advantages over both the big-M and convex hull.