# P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 80 references that are in the map.
- First posted on arXiv 10 Feb 2022.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers](https://mlsanity.com/paper/2011.13824/) (2020)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Partition-based formulations for mixed-integer optimization of trained ReLU neural networks](https://mlsanity.com/paper/2102.04373/) (2021)
- [OMLT: Optimization & Machine Learning Toolkit](https://mlsanity.com/paper/2202.02414/) (2022)
- [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)
- [Semi-supervised clustering methods](https://mlsanity.com/paper/1307.0252/) (2013)
- [Constrained Discrete Black-Box Optimization using Mixed-Integer Programming](https://mlsanity.com/paper/2110.09569/) (2021)
- [Between steps: Intermediate relaxations between big-M and convex hull formulations](https://mlsanity.com/paper/2101.12708/) (2021)
- [Small and Strong Formulations for Unions of Convex Sets from the Cayley Embedding](https://mlsanity.com/paper/1704.03954/) (2017)
- [Convex Mixed-Integer Nonlinear Programs Derived from Generalized Disjunctive Programming using Cones](https://mlsanity.com/paper/2109.09657/) (2021)
- [Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables](https://mlsanity.com/paper/2111.07855/) (2021)

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

- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming](https://mlsanity.com/paper/2505.05261/) (2025)
- [Model-based feature selection for neural networks: A mixed-integer programming approach](https://mlsanity.com/paper/2302.10344/) (2023)
- [An analysis of optimization problems involving ReLU neural networks](https://mlsanity.com/paper/2502.03016/) (2025)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [Input convex neural networks as surrogates in mathematical optimisation](https://mlsanity.com/paper/2608.09707/) (2026)

## Abstract (arXiv)

We develop a class of mixed-integer formulations for disjunctive constraints intermediate to the big-M and convex hull formulations in terms of relaxation strength. The main idea is to capture the best of both the big-M and convex hull formulations: a computationally light formulation with a tight relaxation. The "P-split" formulations are based on a lifted transformation that splits convex additively separable constraints into P partitions and forms the convex hull of the linearized and partitioned disjunction. The "P-split" formulations are derived for disjunctive constraints with convex constraints within each disjunct, and we generalize the results for the case with nonconvex constraints within the disjuncts. We analyze the continuous relaxation of the P-split formulations and show that, under certain assumptions, the formulations form a hierarchy starting from a big-M equivalent and converging to the convex hull. We computationally compare the P-split formulations against big-M and convex hull formulations on 344 test instances. The test problems include K-means clustering, semi-supervised clustering, P_ball problems, and optimization over trained ReLU neural networks. The computational results show promising potential of the P-split formulations. For many of the test problems, P-split formulations are solved with a similar number of explored nodes as the convex hull formulation, while reducing the solution time by an order of magnitude and outperforming big-M both in time and number of explored nodes.