mlsanityData to 7 Oct 2026

Optimization Over Trained Neural Networks: Taking a Relaxing Walk

arXiv 2401.03451 ↗First posted 7 Jan 2024math.OC cs.LGcited by 10

Not on the map. Why?

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.

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

Builds on

52 of 87 references.

References · 52

  1. 2016Error bounds for approximations with deep ReLU networkscited by 567
  2. 2014On the Number of Linear Regions of Deep Neural Networkscited by 378
  3. 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
  4. 2016On the Expressive Power of Deep Neural Networkscited by 302
  5. 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
  6. 2019Algorithms for Verifying Deep Neural Networkscited by 221
  7. 2019Complexity of Linear Regions in Deep Networkscited by 166
  8. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  9. 2019Deep ReLU Networks Have Surprisingly Few Activation Patternscited by 160
  10. 2017Approximating Continuous Functions by ReLU Nets of Minimal Widthcited by 120
  11. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  12. 2019Optimal Sparse Decision Treescited by 104
38 more
  1. 2017Maximum Resilience of Artificial Neural Networkscited by 97
  2. 2013On the number of response regions of deep feed forward networks with piece-wise linear activationscited by 94
  3. 2020Minimum Width for Universal Approximationcited by 92
  4. 2015Representation Benefits of Deep Feedforward Networkscited by 84
  5. 2018Boolean Decision Rules via Column Generationcited by 79
  6. 2018Training for Faster Adversarial Robustness Verification via Inducing ReLU Stabilitycited by 67
  7. 2020MurTree: Optimal Classification Trees via Dynamic Programming and Searchcited by 61
  8. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  9. 2021Partition-based formulations for mixed-integer optimization of trained ReLU neural networkscited by 39
  10. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  11. 2020Lossless Compression of Deep Neural Networkscited by 34
  12. 2022OMLT: Optimization & Machine Learning Toolkitcited by 34
  13. 2021Mixed-Integer Optimization with Constraint Learningcited by 30
  14. 2021Optimization with Constraint Learning: A Framework and Surveycited by 28
  15. 2019JANOS: An Integrated Predictive and Prescriptive Modeling Frameworkcited by 27
  16. 2021Strong Optimal Classification Treescited by 27
  17. 2020BRPO: Batch Residual Policy Optimizationcited by 25
  18. 2020Global Optimization of Objective Functions Represented by ReLU Networkscited by 24
  19. 2018Empirical Bounds on Linear Regions of Deep Rectifier Networkscited by 23
  20. 2020A Scalable MIP-based Method for Learning Optimal Multivariate Decision Treescited by 22
  21. 2021Scaling Up Exact Neural Network Compression by ReLU Stabilitycited by 19
  22. 2022Neur2SP: Neural Two-Stage Stochastic Programmingcited by 16
  23. 2020Neural Networks for Encoding Dynamic Security-Constrained Optimal Power Flowcited by 15
  24. 2018Principled Deep Neural Network Training through Linear Programmingcited by 13
  25. 2022Optimizing Objective Functions from Trained ReLU Neural Networks via Samplingcited by 11
  26. 2021Interpretable and Fair Boolean Rule Sets via Column Generationcited by 10
  27. 2022Optimal Decision Diagrams for Classificationcited by 10
  28. 2023Mixed-Integer Optimisation of Graph Neural Networks for Computer-Aided Molecular Designcited by 9
  29. 2023Getting Away with More Network Pruning: From Sparsity to Geometry and Linear Regionscited by 8
  30. 2022Optimizing Binary Decision Diagrams with MaxSAT for classificationcited by 7
  31. 2020Optimal training of integer-valued neural networks with mixed integer programmingcited by 6
  32. 2023Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networkscited by 6
  33. 2023Alternating mixed-integer programming and neural network training for approximating stochastic two-stage problemscited by 5
  34. 2021Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networkscited by 4
  35. 2022Mixed integer linear optimization formulations for learning optimal binary classification treescited by 4
  36. 2023Taming Binarized Neural Networks and Mixed-Integer Programscited by 4
  37. 2022A Mixed-Integer Programming Approach to Training Dense Neural Networkscited by 3
  38. 2023Structured Pruning of Neural Networks for Constraints Learningcited by 3

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 3; 2025: 3; 2026: 4.

10 papers.

  1. 2024Multi-task Representation Learning for Mixed Integer Linear Programmingcited by 6
  2. 2024Balans: Multi-Armed Bandits-based Adaptive Large Neighborhood Search for Mixed-Integer Programming Problemcited by 4
  3. 2025ParBalans: Parallel Multi-Armed Bandits-based Adaptive Large Neighborhood Searchcited by 1
  4. 2025ID-PaS+ : Identity-Aware Predict-and-Search for General Mixed-Integer Linear Programscited by 1
  5. 2026Relaxation-Informed Training of Neural Network Surrogate Modelscited by 1
  6. 2024Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activationscited by 0
  7. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  8. 2026E-Globe: Scalable ε-Global Verification of Neural Networks via Tight Upper Bounds and Pattern-Aware Branchingcited by 0
  9. 2026Deep Learning for Sequential Decision Making under Uncertainty: Foundations, Frameworks, and Frontierscited by 0
  10. 2026Input convex neural networks as surrogates in mathematical optimisationcited by 0