Partition-based formulations for mixed-integer optimization of trained ReLU neural networks

Understand

This paper introduces a class of mixed-integer formulations for trained ReLU neural networks.

• The approach balances model size and tightness by partitioning node inputs into a number of groups and forming the convex hull over the partitions via disjunctive programming.
• At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node.
• For fewer partitions, we develop smaller relaxations that approximate the convex hull, and show that they outperform existing formulations.