mlsanityData to 7 Oct 2026

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

arXiv 2102.04373 ↗First posted 8 Feb 2021math.OC cs.LG stat.MLcited by 39

Not on the map. Why?

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.

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

Builds on

19 of 45 references.

References · 19

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  3. 2019Minimally distorted Adversarial Examples with a Fast Adaptive Boundary Attackcited by 333
  4. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  5. 2017Formal Verification of Piece-Wise Linear Feed-Forward Neural Networkscited by 241
  6. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 178
  7. 2017Bounding and Counting Linear Regions of Deep Neural Networkscited by 161
  8. 2017EAD: Elastic-Net Attacks to Deep Neural Networks via Adversarial Examplescited by 154
  9. 2017An approach to reachability analysis for feed-forward ReLU neural networkscited by 126
  10. 2018A Dual Approach to Scalable Verification of Deep Networkscited by 125
  11. 2018Strong mixed-integer programming formulations for trained neural networkscited by 115
  12. 2017Maximum Resilience of Artificial Neural Networkscited by 97
7 more
  1. 2019Meta-Learning Acquisition Functions for Transfer Learning in Bayesian Optimizationcited by 70
  2. 2020Enabling certification of verification-agnostic networks via memory-efficient semidefinite programmingcited by 65
  3. 2020The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verificationcited by 50
  4. 2020Lagrangian Decomposition for Neural Network Verificationcited by 35
  5. 2020Lossless Compression of Deep Neural Networkscited by 34
  6. 2019ReLU Networks as Surrogate Models in Mixed-Integer Linear Programscited by 33
  7. 2021Between steps: Intermediate relaxations between big-M and convex hull formulationscited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 7; 2023: 5; 2024: 12; 2025: 4; 2026: 7.

39 papers.

Sort:

By area:

  1. 2023When Deep Learning Meets Polyhedral Theory: A Surveycited by 39
  2. 2022OMLT: Optimization & Machine Learning Toolkitcited by 34
  3. 2024Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planescited by 33
  4. 2024Physics-Informed Neural Networks with Hard Linear Equality Constraintscited by 30
  5. 2022Maximizing information from chemical engineering data sets: Applications to machine learningcited by 17
  6. 2024Certified Robustness to Data Poisoning in Gradient-Based Trainingcited by 17
  7. 2022Optimizing Objective Functions from Trained ReLU Neural Networks via Samplingcited by 11
  8. 2024Optimization Over Trained Neural Networks: Taking a Relaxing Walkcited by 10
  9. 2024Verifying message-passing neural networks via topology-based bounds tighteningcited by 10
  10. 2021Modeling Design and Control Problems Involving Neural Network Surrogatescited by 8
  11. 2022P-split formulations: A class of intermediate formulations between big-M and convex hull for disjunctive constraintscited by 7
  12. 2022Piecewise Linear Neural Networks and Deep Learningcited by 7
27 more
  1. 2023Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networkscited by 6
  2. 2024Machine learning for industrial sensing and control: A survey and practical perspectivecited by 6
  3. 2024Certification for Differentially Private Prediction in Gradient-Based Trainingcited by 6
  4. 2024Feed-Forward Neural Networks as a Mixed-Integer Programcited by 4
  5. 2021Local Repair of Neural Networks Using Optimizationcited by 3
  6. 2026Exact Certification of Data-Poisoning Attacks Using Mixed-Integer Programmingcited by 3
  7. 2021Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!cited by 2
  8. 2023Model-based feature selection for neural networks: A mixed-integer programming approachcited by 2
  9. 2024Expressiveness of Multi-Neuron Convex Relaxations in Neural Network Certificationcited by 2
  10. 2025Global optimization of graph acquisition functions for neural architecture searchcited by 2
  11. 2025Provably Safe Model Updatescited by 2
  12. 2021Optimizing over an ensemble of neural networkscited by 1
  13. 2022Constraint Learning to Define Trust Regions in Predictive-Model Embedded Optimizationcited by 1
  14. 2022Multi-Objective Linear Ensembles for Robust and Sparse Training of Few-Bit Neural Networkscited by 1
  15. 2023Physics Informed Piecewise Linear Neural Networks for Process Optimizationcited by 1
  16. 2024SMLE: Safe Machine Learning via Embedded Overapproximationcited by 1
  17. 2026Relaxation-Informed Training of Neural Network Surrogate Modelscited by 1
  18. 2026Characterizing the Discrete Geometry of ReLU Networkscited by 1
  19. 2023Evaluating robustness of support vector machines with the Lagrangian dual approachcited by 0
  20. 2024A constrained optimization approach to improve robustness of neural networkscited by 0
  21. 2024Tightening convex relaxations of trained neural networks: a unified approach for convex and S-shaped activationscited by 0
  22. 2025Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogatecited by 0
  23. 2025Conformal Mixed-Integer Constraint Learning with Feasibility Guaranteescited by 0
  24. 2026An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functionscited by 0
  25. 2026Convex Hybrid Modeling: An Operator-Based Approachcited by 0
  26. 2026Representation Learning for Exact Preimagescited by 0
  27. 2026DCEmbed: Scalable Optimization over Neural Surrogatescited by 0