ReLU Networks as Surrogate Models in Mixed-Integer Linear Programs

Abstract

We consider the embedding of piecewise-linear deep neural networks (ReLU networks) as surrogate models in mixed-integer linear programming (MILP) problems. A MILP formulation of ReLU networks has recently been applied by many authors to probe for various model properties subject to input bounds. The formulation is obtained by programming each ReLU operator with a binary variable and applying the big-M method. The efficiency of the formulation hinges on the tightness of the bounds defined by the big-M values. When ReLU networks are embedded in a larger optimization problem, the presence of output bounds can be exploited in bound tightening. To this end, we devise and study several bound tightening procedures that consider both input and output bounds. Our numerical results show that bound tightening may reduce solution times considerably, and that small-sized ReLU networks are suitable as surrogate models in mixed-integer linear programs.

References in corpus (8)

• Deep Learning in Neural Networks: An Overview
• Bayesian Reinforcement Learning: A Survey
• Neural Network with Unbounded Activation Functions is Universal Approximator
• Global Deterministic Optimization with Artificial Neural Networks Embedded
• A Dual Approach to Scalable Verification of Deep Networks
• Towards Fast Computation of Certified Robustness for ReLU Networks
• On the Expressive Power of Deep Neural Networks
• Equivalent and Approximate Transformations of Deep Neural Networks

Cited by in corpus (7)

• On data-driven chance constraint learning for mixed-integer optimization problems
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks
• Optimal training of integer-valued neural networks with mixed integer programming
• Demand Response for Flat Nonlinear MIMO Processes using Dynamic Ramping Constraints
• Global Optimization via Optimal Decision Trees
• Dynamic Ramping for Demand Response of Processes and Energy Systems based on Exact Linearization
• Constrained Discrete Black-Box Optimization using Mixed-Integer Programming