# Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2017.

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

- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Low Curvature Activations Reduce Overfitting in Adversarial Training](https://mlsanity.com/paper/2102.07861/) (2021)
- [Efficient Neural Network Analysis with Sum-of-Infeasibilities](https://mlsanity.com/paper/2203.11201/) (2022)
- [Polarity Sampling: Quality and Diversity Control of Pre-Trained Generative Networks via Singular Values](https://mlsanity.com/paper/2203.01993/) (2022)
- [Scalable Verification of GNN-based Job Schedulers](https://mlsanity.com/paper/2203.03153/) (2022)
- [Toward Certified Robustness Against Real-World Distribution Shifts](https://mlsanity.com/paper/2206.03669/) (2022)
- [Learning Security Classifiers with Verified Global Robustness Properties](https://mlsanity.com/paper/2105.11363/) (2021)
- [Traversing the Local Polytopes of ReLU Neural Networks: A Unified Approach for Network Verification](https://mlsanity.com/paper/2111.08922/) (2021)
- [A Unified View of SDP-based Neural Network Verification through Completely Positive Programming](https://mlsanity.com/paper/2203.03034/) (2022)
- [DeepCert: Verification of Contextually Relevant Robustness for Neural Network Image Classifiers](https://mlsanity.com/paper/2103.01629/) (2021)
- [CARE: Certifiably Robust Learning with Reasoning via Variational Inference](https://mlsanity.com/paper/2209.05055/) (2022)
- [Detecting Brittle Decisions for Free: Leveraging Margin Consistency in Deep Robust Classifiers](https://mlsanity.com/paper/2406.18451/) (2024)
- [Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification](https://mlsanity.com/paper/2512.11087/) (2025)
- [Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming](https://mlsanity.com/paper/2102.09663/) (2021)
- [Integer-arithmetic-only Certified Robustness for Quantized Neural Networks](https://mlsanity.com/paper/2108.09413/) (2021)
- [Smoothed Embeddings for Certified Few-Shot Learning](https://mlsanity.com/paper/2202.01186/) (2022)
- [Dynamic Defense Approach for Adversarial Robustness in Deep Neural Networks via Stochastic Ensemble Smoothed Model](https://mlsanity.com/paper/2105.02803/) (2021)
- [Deep Neural Networks pruning via the Structured Perspective Regularization](https://mlsanity.com/paper/2206.14056/) (2022)
- [Certified Defense via Latent Space Randomized Smoothing with Orthogonal Encoders](https://mlsanity.com/paper/2108.00491/) (2021)
- [A Mixed-Integer Programming Approach to Training Dense Neural Networks](https://mlsanity.com/paper/2201.00723/) (2022)
- [A Neural Network Based Choice Model for Assortment Optimization](https://mlsanity.com/paper/2308.05617/) (2023)
- [A Survey of Neural Network Robustness Assessment in Image Recognition](https://mlsanity.com/paper/2404.08285/) (2024)
- [Verifying Inverse Model Neural Networks](https://mlsanity.com/paper/2202.02429/) (2022)
- [DE-CROP: Data-efficient Certified Robustness for Pretrained Classifiers](https://mlsanity.com/paper/2210.08929/) (2022)
- [Applications of 0-1 Neural Networks in Prescription and Prediction](https://mlsanity.com/paper/2402.18851/) (2024)

## Abstract (arXiv)

Deep Neural Networks (DNNs) are very popular these days, and are the subject of a very intense investigation. A DNN is made by layers of internal units (or neurons), each of which computes an affine combination of the output of the units in the previous layer, applies a nonlinear operator, and outputs the corresponding value (also known as activation). A commonly-used nonlinear operator is the so-called rectified linear unit (ReLU), whose output is just the maximum between its input value and zero. In this (and other similar cases like max pooling, where the max operation involves more than one input value), one can model the DNN as a 0-1 Mixed Integer Linear Program (0-1 MILP) where the continuous variables correspond to the output values of each unit, and a binary variable is associated with each ReLU to model its yes/no nature. In this paper we discuss the peculiarity of this kind of 0-1 MILP models, and describe an effective bound-tightening technique intended to ease its solution. We also present possible applications of the 0-1 MILP model arising in feature visualization and in the construction of adversarial examples. Preliminary computational results are reported, aimed at investigating (on small DNNs) the computational performance of a state-of-the-art MILP solver when applied to a known test case, namely, hand-written digit recognition.