mlsanityData to 7 Oct 2026

Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks

arXiv 2312.16699 ↗First posted 27 Dec 2023math.OC cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

The use of Mixed-Integer Linear Programming (MILP) models to represent neural networks with Rectified Linear Unit (ReLU) activations has become increasingly widespread in the last decade. This has enabled the use of MILP technology to test-or stress-their behavior, to adversarially improve their training, and to embed them in optimization models leveraging their predictive power. Many of these MILP models rely on activation bounds. That is, bounds on the input values of each neuron. In this work, we explore the tradeoff between the tightness of these bounds and the computational effort of solving the resulting MILP models. We provide guidelines for implementing these models based on the impact of network structure, regularization, and rounding.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 28 of its 47 references that are in the map. First posted on arXiv 27 Dec 2023.

Builds on

28 of 47 references.

References · 28

  1. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  2. 2016Error bounds for approximations with deep ReLU networkscited by 567
  3. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  4. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  5. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  6. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  7. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 120
  8. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  9. 2020SoK: Certified Robustness for Deep Neural Networkscited by 100
  10. 2017Maximum Resilience of Artificial Neural Networkscited by 97
  11. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  12. 2020Minimum Width for Universal Approximationcited by 92
16 more
  1. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  2. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  3. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  4. 2020Lossless Compression of Deep Neural Networkscited by 34
  5. 2022OMLT: Optimization & Machine Learning Toolkitcited by 34
  6. 2021Mixed-Integer Optimization with Constraint Learningcited by 30
  7. 2021Optimization with Constraint Learning: A Framework and Surveycited by 28
  8. 2019JANOS: An Integrated Predictive and Prescriptive Modeling Frameworkcited by 27
  9. 2020BRPO: Batch Residual Policy Optimizationcited by 25
  10. 2018Empirical Bounds on Linear Regions of Deep Rectifier Networkscited by 23
  11. 2021Scaling Up Exact Neural Network Compression by ReLU Stabilitycited by 19
  12. 2020Neural Networks for Encoding Dynamic Security-Constrained Optimal Power Flowcited by 15
  13. 2018Combinatorial Attacks on Binarized Neural Networkscited by 11
  14. 2022Optimizing Objective Functions from Trained ReLU Neural Networks via Samplingcited by 11
  15. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  16. 2023Structured Pruning of Neural Networks for Constraints Learningcited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 2; 2026: 1.

6 papers.

  1. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
  2. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  3. 2025An analysis of optimization problems involving ReLU neural networkscited by 2
  4. 2026Relaxation-Informed Training of Neural Network Surrogate Modelscited by 1
  5. 2024Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activationscited by 0
  6. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0