# Optimization Over Trained Neural Networks: Taking a Relaxing Walk

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 87 references that are in the map.
- First posted on arXiv 7 Jan 2024.

## Builds on (most cited first, 30 of 52)

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [The Expressive Power of Neural Networks: A View from the Width](https://mlsanity.com/paper/1709.02540/) (2017)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Algorithms for Verifying Deep Neural Networks](https://mlsanity.com/paper/1903.06758/) (2019)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [Deep ReLU Networks Have Surprisingly Few Activation Patterns](https://mlsanity.com/paper/1906.00904/) (2019)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Maximum Resilience of Artificial Neural Networks](https://mlsanity.com/paper/1705.01040/) (2017)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Minimum Width for Universal Approximation](https://mlsanity.com/paper/2006.08859/) (2020)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [Training for Faster Adversarial Robustness Verification via Inducing ReLU Stability](https://mlsanity.com/paper/1809.03008/) (2018)
- [MurTree: Optimal Classification Trees via Dynamic Programming and Search](https://mlsanity.com/paper/2007.12652/) (2020)
- [Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routing](https://mlsanity.com/paper/2010.12001/) (2020)
- [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)
- [Lossless Compression of Deep Neural Networks](https://mlsanity.com/paper/2001.00218/) (2020)
- [Mixed-Integer Optimization with Constraint Learning](https://mlsanity.com/paper/2111.04469/) (2021)
- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Optimization with Constraint Learning: A Framework and Survey](https://mlsanity.com/paper/2110.02121/) (2021)
- [JANOS: An Integrated Predictive and Prescriptive Modeling Framework](https://mlsanity.com/paper/1911.09461/) (2019)
- [BRPO: Batch Residual Policy Optimization](https://mlsanity.com/paper/2002.05522/) (2020)
- [Global Optimization of Objective Functions Represented by ReLU Networks](https://mlsanity.com/paper/2010.03258/) (2020)

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

- [Multi-task Representation Learning for Mixed Integer Linear Programming](https://mlsanity.com/paper/2412.14409/) (2024)
- [Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problem](https://mlsanity.com/paper/2412.14382/) (2024)
- [Relaxation-Informed Training of Neural Network Surrogate Models](https://mlsanity.com/paper/2604.22746/) (2026)
- [ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Search](https://mlsanity.com/paper/2508.06736/) (2025)
- [ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programs](https://mlsanity.com/paper/2512.10211/) (2025)
- [Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activations](https://mlsanity.com/paper/2410.23362/) (2024)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [E-Globe: Scalable ε-Global Verification of Neural Networks via Tight Upper Bounds and Pattern-Aware Branching](https://mlsanity.com/paper/2602.05068/) (2026)
- [Deep Learning for Sequential Decision Making under Uncertainty: Foundations, Frameworks, and Frontiers](https://mlsanity.com/paper/2604.11507/) (2026)
- [Input convex neural networks as surrogates in mathematical optimisation](https://mlsanity.com/paper/2608.09707/) (2026)

## Abstract (arXiv)

Besides training, mathematical optimization is also used in deep learning to model and solve formulations over trained neural networks for purposes such as verification, compression, and optimization with learned constraints. However, solving these formulations soon becomes difficult as the network size grows due to the weak linear relaxation and dense constraint matrix. We have seen improvements in recent years with cutting plane algorithms, reformulations, and an heuristic based on Mixed-Integer Linear Programming (MILP). In this work, we propose a more scalable heuristic based on exploring global and local linear relaxations of the neural network model. Our heuristic is competitive with a state-of-the-art MILP solver and the prior heuristic while producing better solutions with increases in input, depth, and number of neurons.