Compiling ReLU Neural Networks into Mixed Integer Programs

98 concepts67 papers1 proposal

Deep neural networks are incredibly powerful at learning complex patterns from data, but they are notoriously difficult to optimize over. If you want to find the exact input that maximizes a network's output, or prove that a network will never output an unsafe command, standard gradient-based methods fail. They get trapped in local minima and offer no formal guarantees.

However, a key insight has transformed this landscape: many popular neural networks are not completely smooth, non-linear black boxes. Instead, networks using Rectified Linear Unit (ReLU) or binary activations are piecewise linear. By treating each linear segment as a discrete choice, we can reformulate the entire neural network as a Mixed-Integer Program (MIP). This allows us to leverage decades of mathematical optimization research to solve neural network design, verification, and decision-making problems to global optimality.

The Core Mechanism: The Big-M Transformation

How do we turn a non-linear activation function into linear equations? Let's look at a single ReLU neuron. The output $y$ is determined by the input $x$ via $y = \max(0, x)$. This function has two distinct behaviors:

  1. Inactive state: If $x < 0$, then $y = 0$.
  2. Active state: If $x \ge 0$, then $y = x$.

To represent this mathematically without non-linear operators, we introduce a binary indicator variable $z \in \{0, 1\}$, where $z = 1$ implies the neuron is active, and $z = 0$ implies it is inactive. We can enforce this conditional logic using a technique known as the Big-M method.

Assuming we know the lower bound $L$ and upper bound $U$ that the input $x$ can possibly take, we can write the following linear inequalities:

$$y \ge 0$$ $$y \ge x$$ $$y \le x - L(1 - z)$$ $$y \le U z$$

To see why this works, consider the two possible states of $z$:

  • If $z = 0$ (Inactive): The constraints simplify to $y \ge 0$, $y \ge x$, $y \le x - L$, and $y \le 0$. Together, $y \ge 0$ and $y \le 0$ force the output $y = 0$. The remaining constraint $0 \ge x$ ensures this state is only valid when the input is non-positive.
  • If $z = 1$ (Active): The constraints simplify to $y \ge 0$, $y \ge x$, $y \le x$, and $y \le U$. Together, $y \ge x$ and $y \le x$ force the output $y = x$. The constraint $x \ge 0$ ensures this state is only valid when the input is non-negative.

By applying this transformation to every ReLU neuron in a network, as demonstrated by Buser Say et al. in Nonlinear Hybrid Planning with Deep Net Learned Transition Models and Mixed-Integer Linear Programming, the entire forward pass of a deep neural network is compiled into a system of linear constraints and binary variables.

Optimization and Inverse Design

Once a neural network is embedded as a set of MIP constraints, we can optimize through it. Instead of using the network purely for forward prediction, we can treat the network's inputs as decision variables.

This is particularly valuable for inverse design and black-box optimization. In engineering, we often train a neural network surrogate model to predict a design's performance because the underlying physics simulations are too slow. To find the optimal design, Hans-peter Seidel et al. demonstrate in Mixed Integer Neural Inverse Design that reformulating the surrogate network as a MIP allows solvers to find globally optimal designs, even when choosing from discrete material libraries. Similarly, Theodore P. Papalexopoulos et al. leverage this in Constrained Discrete Black-Box Optimization using Mixed-Integer Programming to optimize expensive discrete functions subject to complex combinatorial constraints.

Beyond standalone optimization, this technique enables prescriptive analytics, where neural networks are embedded inside larger operational optimization problems. David Bergman et al. introduced JANOS: An Integrated Predictive and Prescriptive Modeling Framework to automate this integration, allowing decision-makers to optimize real-world actions based on how they influence predictions.

A prime example is found in market design: Jakob Weissteiner et al. show in Deep Learning-Powered Iterative Combinatorial Auctions that reformulating a neural network preference model into a MIP allows solvers to exactly determine the most economically efficient allocation of resources in large-scale auctions.

Formal Verification and Safety Guarantees

Because MIP solvers provide mathematical proofs of global optimality, this reformulation serves as a powerful tool for formal verification. Instead of testing a network on millions of random inputs and hoping it doesn't fail, we can mathematically prove its properties.

For example, understanding a network's sensitivity to small perturbations is crucial for evaluating its robustness. Matt Jordan et al. developed LipMIP in Exactly Computing the Local Lipschitz Constant of ReLU Networks, which uses a MIP framework to compute the exact local Lipschitz constant of a network, revealing that traditional heuristic estimators often wildly miscalculate network stability.

In robotics and control systems, ensuring that a learned dynamic model never violates safety boundaries is paramount. Tianhao Wei et al. show in Safe Control with Neural Network Dynamic Models that encoding neural network dynamics as MIP constraints allows online control loops to find inputs that are mathematically guaranteed to prevent safety violations. If a pre-trained controller is found to be unsafe, Siyu Zhou demonstrates in Safe Robot Learning in Assistive Devices through Neural Network Repair that the network can be formally "repaired" by solving a Mixed-Integer Quadratic Program (MIQP) that enforces safety boundaries while minimizing performance loss.

Taming Discrete Architectures

The MIP approach is not limited to continuous networks with ReLU activations; it is uniquely suited for discrete architectures like Binarized Neural Networks (BNNs). BNNs use sign-based activations ($\pm 1$), making them highly efficient but incredibly difficult to analyze or train using standard gradient descent due to their non-differentiable nature.

By reformulating these discrete operations into linear inequalities, standard optimization tools can easily process them. Christopher Lazarus et al. demonstrate in A Mixed Integer Programming Approach for Verifying Properties of Binarized Neural Networks that the discrete nature of BNNs actually allows MIP verification runtimes to be 10x to 20x faster than full-precision networks, making formal certification highly practical.

Overcoming the Computational Bottleneck

While compiling a neural network into a MIP grants the power of exact global optimization, it comes with a significant catch: computational complexity. Every ReLU neuron or binary activation adds a binary variable to the optimization problem. Since mixed-integer programming is NP-hard, the search space grows exponentially with the size of the network.

The efficiency of the Big-M formulation heavily depends on the tightness of the bounds ($L$ and $U$). If the bounds are too loose, the linear relaxation of the MIP is weak, forcing the solver to explore an enormous branch-and-bound tree. To combat this, Siyu Zhou utilizes interval arithmetic to compute tight bounds for coefficients, drastically reducing solving times.

Alternatively, when exact solutions are too slow for real-time applications, the authors of Real-time safe control of neural network dynamic models with sound approximation show that one can relax the strict MIP constraints using Bernstein polynomial over-approximations. This transforms the expensive discrete problem into a smooth quadratic program that can be solved orders of magnitude faster while maintaining strict safety bounds.

Key Foundational Work

Measuring Neural Net Robustness with Constraints (2016) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 75 papers
  2. Version 1 · 2026-10-04 · 138 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_mixed_integer_programming_reformulation_c0f7426b,
  title = {mixed-integer programming reformulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixed-integer-programming-reformulation/rdr_c0f7426b087b4e3abbf5e4f74ce4744e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_mixed_integer_programming_reformulation_c0f7426b_v2,
  title = {mixed-integer programming reformulation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mixed-integer-programming-reformulation/rdr_c0f7426b087b4e3abbf5e4f74ce4744e/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake