Input convex neural networks as surrogates in mathematical optimisation

In operations research, neural networks are frequently used as surrogate models to approximate complex, black-box functions within larger optimization problems. The standard approach uses feedforward neural networks (FNNs) with ReLU activations, which are typically reformulated as mixed-integer programs (MIPs). However, this approach is computationally expensive because each ReLU unit requires a binary variable, leading to poor scalability as the network size increases.

This paper advocates for Input Convex Neural Networks (ICNNs) as a more efficient alternative. Because ICNNs are architecturally constrained to be convex with respect to their inputs, they offer two distinct computational advantages over standard FNNs:

1. Tighter Relaxations: The ICNN-MIP formulation provides a tighter linear programming (LP) relaxation than the FNN-MIP, often eliminating the integrality gap entirely in favorable instances.
2. LP-based Reformulation: ICNNs uniquely allow for an epigraph-based reformulation that replaces nonlinear ReLU constraints with linear inequalities, potentially bypassing the need for binary variables altogether.

The authors provide a rigorous structural analysis of ICNN-MIP formulations and define the conditions under which the epigraph embedding is valid. A key contribution is the construction of the strongest continuous relaxation for ICNNs over box domains, which combines the epigraph representation with a concave envelope derived from vertex evaluations. This construction is tractable for ICNNs but computationally prohibitive for general ReLU networks. The authors also develop a specialized branch-and-bound algorithm that branches directly on input variables rather than intermediate network variables, significantly improving efficiency. Empirical tests on humanitarian food aid, oil well routing, and wine blending demonstrate that ICNNs match the accuracy of FNNs while offering superior scalability and faster solve times.