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

2021/02/08 by Calvin Tsay, Tsay, Calvin, Jan Kronqvist +5 · 6 citations
Computer Science · #Advanced Neural Network Applications #Adversarial Robustness in Machine Learning #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2102.04373

openalex publication_date 2021/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

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. Specifically, we propose strategies for partitioning variables based on theoretical motivations and validate these strategies using extensive computational experiments. Furthermore, the proposed scheme complements known algorithmic approaches, e.g., optimization-based bound tightening captures dependencies within a partition.

Cited by

• Provably Safe Model Updates
• Decision-Focused Learning for Neural Network-Constrained HVAC Scheduling
• Conformal Mixed-Integer Constraint Learning with Feasibility Guarantees
• Global optimization of graph acquisition functions for neural architecture search
• Integer Reasoning Modulo Different Constants in SMT
• Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate

Related

• Strong mixed-integer programming formulations for trained neural networks
• An analysis of optimization problems involving ReLU neural networks
• Computational Tradeoffs of Optimization-Based Bound Tightening in ReLU Networks
• Convex Formulations for Training Two-Layer ReLU Neural Networks
• Optimizing Objective Functions from Trained ReLU Neural Networks via Sampling