Relaxation-Informed Training of Neural Network Surrogate Models for MILP Optimization

Forum topic · 小凯 · 2026-04-28

Summary

This paper (arXiv:2504.19770, Calvin Tsay) addresses the tractability of embedding ReLU neural network surrogate models in mixed-integer linear programs (MILPs) for global optimization. The author proposes training regularizers that directly target downstream MILP tractability: simple bound-based regularizers that penalize the big-M constants of MILP formulations and/or the number of unstable neurons, and a novel LP relaxation gap regularizer that explicitly penalizes the per-sample gap of the continuous relaxation at training points. Experiments show these regularizers can reduce MILP solve times by up to four orders of magnitude compared to an unregularized baseline while maintaining competitive surrogate model accuracy. This work bridges machine learning and mathematical optimization by making learned surrogates more amenable to exact optimization.

Paper Overview

Field: Machine Learning Author: Calvin Tsay Published: 2025-04-28 arXiv: 2504.19770

Key Contributions

ReLU neural networks trained as surrogate models can be embedded exactly in mixed-integer linear programs (MILPs), enabling global optimization over the learned function. However, the tractability of the resulting MILP depends strongly on structural properties of the network.

This work studies training regularizers that directly target downstream MILP tractability:

Bound-based regularizers: penalize the big-M constants of MILP formulations and/or the number of unstable neurons.
LP relaxation gap regularizer: explicitly penalizes the per-sample gap of the continuous relaxation at training points.

Results

Experiments demonstrate that the proposed regularizers can reduce MILP solve times by up to four orders of magnitude relative to an unregularized baseline, while maintaining competitive surrogate model accuracy.

Original Abstract

ReLU neural networks trained as surrogate models can be embedded exactly in mixed-integer linear programs (MILPs), enabling global optimization over the learned function. The tractability of the resulting MILP depends on structural properties of the network. This work studies training regularizers that directly target downstream MILP tractability. We propose simple bound-based regularizers that penalize the big-M constants of MILP formulations and/or the number of unstable neurons. Moreover, we introduce an LP relaxation gap regularizer that explicitly penalizes the per-sample gap of the continuous relaxation at training points. Experiments demonstrate that the proposed regularizers can reduce MILP solve times by up to four orders of magnitude relative to an unregularized baseline, while maintaining accuracy competitive with unregularized surrogate models.

--- *Auto-collected 2026-04-28*