# Partition-based formulations for mixed-integer optimization of trained ReLU neural networks

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 8 Feb 2021.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Provable defenses against adversarial examples via the convex outer adversarial polytope](https://mlsanity.com/paper/1711.00851/) (2017)
- [Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attack](https://mlsanity.com/paper/1907.02044/) (2019)
- [Towards Fast Computation of Certified Robustness for ReLU Networks](https://mlsanity.com/paper/1804.09699/) (2018)
- [Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks](https://mlsanity.com/paper/1705.01320/) (2017)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examples](https://mlsanity.com/paper/1709.04114/) (2017)
- [An approach to reachability analysis for feed-forward ReLU neural networks](https://mlsanity.com/paper/1706.07351/) (2017)
- [A Dual Approach to Scalable Verification of Deep Networks](https://mlsanity.com/paper/1803.06567/) (2018)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Maximum Resilience of Artificial Neural Networks](https://mlsanity.com/paper/1705.01040/) (2017)
- [Meta-Learning Acquisition Functions for Transfer Learning in Bayesian Optimization](https://mlsanity.com/paper/1904.02642/) (2019)
- [Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming](https://mlsanity.com/paper/2010.11645/) (2020)
- [The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification](https://mlsanity.com/paper/2006.14076/) (2020)
- [Lagrangian Decomposition for Neural Network Verification](https://mlsanity.com/paper/2002.10410/) (2020)
- [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)
- [Between steps: Intermediate relaxations between big-M and convex hull formulations](https://mlsanity.com/paper/2101.12708/) (2021)

## Built on by (most cited first, 30 of 39)

- [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)
- [Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes](https://mlsanity.com/paper/2501.00200/) (2024)
- [Physics-Informed Neural Networks with Hard Linear Equality Constraints](https://mlsanity.com/paper/2402.07251/) (2024)
- [Certified Robustness to Data Poisoning in Gradient-Based Training](https://mlsanity.com/paper/2406.05670/) (2024)
- [Maximizing information from chemical engineering data sets: Applications to machine learning](https://mlsanity.com/paper/2201.10035/) (2022)
- [Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling](https://mlsanity.com/paper/2205.14189/) (2022)
- [Optimization Over Trained Neural Networks: Taking a Relaxing Walk](https://mlsanity.com/paper/2401.03451/) (2024)
- [Verifying message-passing neural networks via topology-based bounds tightening](https://mlsanity.com/paper/2402.13937/) (2024)
- [Modeling Design and Control Problems Involving Neural Network Surrogates](https://mlsanity.com/paper/2111.10489/) (2021)
- [Machine learning for industrial sensing and control: A survey and practical perspective](https://mlsanity.com/paper/2401.13836/) (2024)
- [P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraints](https://mlsanity.com/paper/2202.05198/) (2022)
- [Piecewise Linear Neural Networks and Deep Learning](https://mlsanity.com/paper/2206.09149/) (2022)
- [Certification for Differentially Private Prediction in Gradient-Based Training](https://mlsanity.com/paper/2406.13433/) (2024)
- [Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks](https://mlsanity.com/paper/2312.16699/) (2023)
- [Feed-Forward Neural Networks as a Mixed-Integer Program](https://mlsanity.com/paper/2402.06697/) (2024)
- [Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programming](https://mlsanity.com/paper/2602.16944/) (2026)
- [Local Repair of Neural Networks Using Optimization](https://mlsanity.com/paper/2109.14041/) (2021)
- [Provably Safe Model Updates](https://mlsanity.com/paper/2512.01899/) (2025)
- [Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!](https://mlsanity.com/paper/2103.00507/) (2021)
- [Model-based feature selection for neural networks: A mixed-integer programming approach](https://mlsanity.com/paper/2302.10344/) (2023)
- [Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certification](https://mlsanity.com/paper/2410.06816/) (2024)
- [Global optimization of graph acquisition functions for neural architecture search](https://mlsanity.com/paper/2505.23640/) (2025)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [Optimizing over an ensemble of neural networks](https://mlsanity.com/paper/2112.07007/) (2021)
- [Constraint Learning to Define Trust Regions in Predictive-Model Embedded Optimization](https://mlsanity.com/paper/2201.04429/) (2022)
- [Multi-Objective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networks](https://mlsanity.com/paper/2212.03659/) (2022)
- [Physics Informed Piecewise Linear Neural Networks for Process Optimization](https://mlsanity.com/paper/2302.00990/) (2023)
- [SMLE: Safe Machine Learning via Embedded Overapproximation](https://mlsanity.com/paper/2409.20517/) (2024)
- [Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees](https://mlsanity.com/paper/2506.03531/) (2025)

## Abstract (arXiv)

This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. The approach balances model size and tightness by partitioning node inputs into a number of groups and forming the convex hull over the partitions via disjunctive programming. At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node. For fewer partitions, we develop smaller relaxations that approximate the convex hull, and show that they outperform existing formulations. Specifically, we propose strategies for partitioning variables based on theoretical motivations and validate these strategies using extensive computational experiments. Furthermore, the proposed scheme complements known algorithmic approaches, e.g., optimization-based bound tightening captures dependencies within a partition.