# Strong mixed-integer programming formulations for trained neural networks

Source: [Strong mixed-integer programming formulations for trained neural networks](<https://www.sota2.com/research/paper/68fa56941e209131ce99ddbf>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-25T14:13:48.735Z

Authors: Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, Juan Pablo Vielma

Published: 2018-11-05T19:19:15.000Z

## Abstract

We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These formulations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or solving decision problems where the objective function is a machine learning model. We present a generic framework, which may be of independent interest, that provides a way to construct sharp or ideal formulations for the maximum of d affine functions over arbitrary polyhedral input domains. We apply this result to derive MIP formulations for a number of the most popular nonlinear operations (e.g. ReLU and max pooling) that are strictly stronger than other approaches from the literature. We corroborate this computationally, showing that our formulations are able to offer substantial improvements in solve time on verification tasks for image classification networks.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1811.01988>)

[PDF](<https://arxiv.org/pdf/1811.01988.pdf>)