Strong mixed-integer programming formulations for trained neural networks
Authors:
- Ross AndersonRARoss Anderson
- Joey HuchetteJHJoey Huchette
- Will MaWMWill Ma
- Christian TjandraatmadjaCTChristian Tjandraatmadja
- Juan Pablo VielmaJVJuan Pablo Vielma
Preprint
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.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Deterministic Global Optimization with Artificial Neural Networks EmbeddedJournal of Optimization Theory and Applications, 2018
- Strong formulations for quadratic optimization with M-matrices and indicator variablesMathematical Programming, 2018
- Deep neural networks and mixed integer linear optimizationConstraints, 2018
- On handling indicator constraints in mixed integer programmingComputational Optimization and Applications, 2016
- A lagrangian propagator for artificial neural networks in constraint programmingConstraints, 2015
- On mathematical programming with indicator constraintsMathematical Programming, 2015
- Mixed-integer nonlinear programs featuring “on/off” constraintsComputational Optimization and Applications, 2011
- Modeling disjunctive constraints with a logarithmic number of binary variables and constraintsMathematical Programming, 2009
- The Cayley Trick, lifting subdivisions and the Bohne–Dress theorem on zonotopal tilingsJournal of the European Mathematical Society, 2000
- Alternative formulations of mixed integer programsAnnals of Operations Research, 1988