Input convex neural networks as surrogates in mathematical optimisation

This paper studies the use of input convex neural networks (ICNNs) as surrogates within mathematical optimisation problems. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. The authors advocate ICNNs as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages: first, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances; second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, the authors exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains—namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope—which is tractable under input convexity but hard for general ReLU networks. On this basis, they develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability.

The paper makes five main contributions:

1. Structural analysis of ICNN-MIP formulations: The authors characterise exactness properties of the ICNN-MIP LP relaxation (Proposition 1) and compare the resulting relaxation gap with that of FNN-MIP formulations.

2. Formal definition of epigraph embedding validity: They give a precise definition of when the epigraph embedding of an ICNN is a valid reformulation of the original problem (Definition 1) and discuss the problem structures under which validity holds or fails.

3. The strongest continuous relaxation of ICNN surrogates: They construct a concave envelope of the ICNN from vertex evaluations (Proposition 2) and prove that, combined with the epigraph, it yields the convex hull of the ICNN's graph over box domains, the strongest continuous relaxation of the ICNN formulation (Theorem 1). No counterpart is known for general ReLU network formulations.

4. A specialised branch-and-bound (BB) algorithm: Building on this relaxation, they develop ICNN-BB (Algorithm 1), an LP-based BB algorithm for ICNN-embedded optimisation that avoids introducing binary variables. The algorithm branches directly on the input variables rather than on intermediate variables encoding the network, and terminates at the root node whenever the epigraph embedding is valid.

5. Empirical validation on three case studies: They evaluate the proposed approaches across three problems from the literature, confirming tighter MIP relaxations for ICNN-MIP, root-node termination of ICNN-BB when the epigraph embedding is valid, and superior performance of ICNN-BB where the vertex-based envelope remains manageable.

FNNs consist of consecutive layers made up of individual units called neurons, each applying an activation function to a weighted sum of the previous layer's outputs. An FNN with ReLU activations in hidden layers and identity in the output layer can be exactly reformulated as a mixed-integer program (MIP). For each neuron j in hidden layer k, a binary variable δk,j ∈ 0, 1 indicates activation state and a slack variable sk,j ≥ 0 captures the negative part of the pre-activation value. The big-M constants Uk,j and Lk,j are valid upper and lower bounds on the pre-activation value.

ICNNs have a similar structure to FNNs except that during training, layer weights are constrained to be non-negative (except for the first layer), and the activation function must be convex and non-decreasing (satisfied by ReLU). Weighted skip connections from the input layer to each subsequent layer improve representation capacity while preserving convexity. The mapping for each layer is expressed as:

zk+1 = σ(Wk zk + Sk z0 + bk), k = 0,..., K−1

The key distinction is that ICNN inference admits an exact LP representation via an epigraph representation of ReLU activations, replacing layer-wise nonlinear equality constraints with linear inequalities. This LP structure eliminates the need for binary variables.

The general setting embeds a trained network f̂ approximating a black-box function f in a downstream optimisation model:

min h(x,y) s.t. g(x,y) ≤ 0, y = f̂(x), x ∈ X

Two computational routes are available: the MIP formulation (applicable to any ReLU network) and the LP epigraph route (specific to ICNNs). The epigraph representation enforces only y ≥ f̂(x), and exactness stems from the objective penalising overestimation. A general embedding need not penalise such overestimation, so the epigraph embedding constitutes a relaxation that is only equivalent when tight.

The ICNN-MIP formulation is derived with the same big-M structure as FNN-MIP, with the addition of skip connection terms Sk z0 and non-negativity of weights W1:K−1.

Proposition 1 (Exactness of the ICNN-MIP relaxation with fixed input): For every fixed input z̄0 ∈ Z, the minimum output value over the LP relaxation of the ICNN-MIP equals the exact ICNN output obtained from the MIP. Thus, when z0 is fixed, the LP relaxation has zero integrality gap.

The proof uses induction: since W1:K−1 ≥ 0 and ReLU is non-decreasing, every LP-feasible point satisfies zk ≥ z̄k componentwise, so no LP-feasible point can attain an output below the exact ICNN value.

Corollary 1: The LP relaxation of the ICNN-MIP and the epigraph formulation have the same minimum output value for every fixed input, and collecting these pointwise values generates the epigraph of the ICNN surrogate.

Corollary 2: Under direct output minimisation, embedding the ICNN via the LP relaxation gives the same optimal objective value as embedding it via the exact MIP.

For FNN-MIP formulations, no analogous guarantee holds because FNN weights are unrestricted in sign, so the induction argument breaks down. The FNN-MIP relaxation is only guaranteed to provide a lower bound on its own exact MIP optimum. A numerical illustration approximating f(x) = x2 over [−2, 2] shows the FNN-MIP exhibits a substantial pointwise relaxation gap while the ICNN-MIP gap is zero throughout.

Definition 1 (validity of the LP epigraph embedding): The epigraph embedding is valid if (i) the two problems have the same optimal objective value, and (ii) the optimal solution satisfies y* = f̂(x*), i.e., the ICNN constraint is active at optimality.

The validity holds when h and g are non-decreasing in y, since any slack in y ≥ f̂(x) can then be removed without worsening the objective or violating feasibility.

Proposition 2 (Concave envelope of the ICNN function): The concave envelope of f̂ over the box X is the value function of an LP using convex combinations of vertex values:

z̄(x) = max Σ αi f̂(x̃i) s.t. Σ αi x̃i = x, Σ αi = 1, αi ≥ 0

The proof shows z̄(x) ≥ f̂(x) for every x ∈ X, z̄(·) is concave, and no concave overestimator is tighter than z̄(·).

Theorem 1 (Strongest continuous relaxation of the ICNN's graph): The projection onto (x,y) of the feasible set defined by the epigraph and envelope constraints equals the convex hull of the graph of f̂ over X:

F = (x, y): x ∈ X, f̂(x) ≤ y ≤ z̄(x) = conv (x, f̂(x)): x ∈ X

This is the strongest continuous relaxation of the original problem obtainable by relaxing the ICNN constraint alone. The construction requires 2n auxiliary variables and ICNN evaluations at all 2n vertices, with cost governed by input dimension n rather than number of neurons.

Algorithm 1 (ICNN-BB) maintains a list of active subproblems, an incumbent objective value, and corresponding solution. Subproblems are explored in breadth-first order. At each iteration:

• A subproblem is selected and solved

• If infeasible, prune by infeasibility

• If h* ≥ h, prune by bound

• If relative gap ϵ ≤ τ, prune by optimality and update incumbent

• Otherwise, branch on the ICNN input variable with widest interval, bisecting at the midpoint

The algorithm branches on input variables directly rather than intermediate binary variables. When the epigraph embedding is valid, the algorithm terminates at the root node without branching. Since the ICNN is continuous and piecewise linear, the concave envelope converges uniformly to f̂ as subproblem domains shrink, ensuring finite termination.

Three case studies were evaluated, comparing FNN-MIP, ICNN-MIP, and ICNN-BB using both HiGHS and Gurobi solvers with 8 threads, 3600 s time limit, and optimality tolerance τ = 0.01.

The humanitarian food aid model minimises transportation and procurement costs for a food basket while adhering to nutritional and palatability standards. The palatability surrogate has 25 input features (commodity amounts).

Training performance: ICNNs match FNNs on validation MSE across six architectures (2 or 3 hidden layers of 10, 50, or 100 neurons). For 3 10 and 3 50 networks, the ICNN is more accurate than its FNN counterpart. ICNN training is roughly 20% slower due to weight projection.

Optimisation results: FNN-MIP scales poorly—even the 2 50 network pushes HiGHS past the 3600 s time limit after exploring roughly 760,000 nodes. ICNN-MIP solves every instance in under 0.15 s at the root node using Gurobi. ICNN-BB terminates at the root node on all architectures within 0.04–0.07 s, confirming the epigraph embedding is exact on this problem. The computational cost of ICNN-BB is largely independent of network size.

The problem maximises total oil collected at separators, with NN surrogates for well performance curves and riser pressure drop functions. The problem combines surrogates with binary well-to-manifold routing decisions. Instances 2 m with m ∈ 6, 7,..., 12 wells were studied.

Training performance: Eight well surrogates show essentially identical accuracy between ICNN and FNN (MSE on the order of 10−5). The riser surrogate shows the ICNN MSE roughly an order of magnitude larger than FNN, but remains acceptable relative to output scale.

Optimisation results: ICNN-MIP's node count is consistently an order of magnitude smaller than FNN-MIP's (up to a factor of sixteen at 2 12). Using HiGHS, ICNN-BB explores three to eight times fewer nodes than ICNN-MIP and solves roughly three to four times faster. Using Gurobi, ICNN-MIP nodes are more than an order of magnitude cheaper than ICNN-BB nodes, so ICNN-MIP solves faster despite exploring more nodes. The algorithmic advantage of ICNN-BB is solver-dependent—pronounced with HiGHS where generic MIP nodes are expensive, attenuated with Gurobi where generic MIP nodes are cheap.

The problem minimises total cost of grapes used in blends while meeting quality thresholds, with an 11-dimensional physicochemical feature vector input to the quality surrogate. Instances n m with n ∈ 1, 2, 3, 4, 5 blends and m = 5n suppliers were studied.

Training performance: The ICNN reaches validation MSE 0.445, essentially matching the FNN's 0.434.

Optimisation results: ICNN-BB is the fastest method on moderate-size instances using HiGHS—on 2 10 and 3 15, it completes in under 0.15 s while both MIP methods require seconds (speedup of one to two orders of magnitude). The 5 25 instance exposes the scalability frontier: with five blends each taking an 11-dimensional input, the concave envelope must be constructed over a 55-dimensional box, and the vertex set and LP size grow rapidly with branching depth. ICNN-BB explores around 72,000 nodes without returning a feasible incumbent. This identifies a concrete crossover point where the exponential growth of the vertex set overwhelms the advantage of LP-based subproblem solves.

The paper concludes that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability. The two-tier advantage consists of tighter MIP relaxations using standard solvers and efficient LP-driven convergence via ICNN-BB. The surrogate's input dimensionality sets the practical scalability frontier of ICNN-BB.

Open directions include: sharpening the validity condition into an a priori diagnostic, developing lower-complexity constructions of the concave envelope (sampled, sparsified, or hierarchical alternatives to 2n vertex enumeration), further algorithmic refinements (specialised branching strategies, variable selection, primal heuristics, parallelisation), replacing the ad hoc convexity diagnostic with a principled check, and relaxing the convexity restriction via partially convex architectures or ICNN and FNN mixtures.

Improvements to AI Systems:

1. Convexity-Aware Surrogate Selection: Implement a pre-training diagnostic that tests whether the underlying black-box function is approximately convex/concave (e.g., via Hessian eigenvalue sampling or monotonicity checks). If convex, automatically train an ICNN instead of a general FNN, enabling the LP-based reformulation and eliminating binary variables in downstream optimization.

2. Hybrid Surrogate Architecture: Build a system that trains both an ICNN and an FNN, compares validation errors, and selects the ICNN when accuracy is within a user-defined tolerance (e.g., 10% relative MSE). This ensures the optimization benefits (tighter relaxations, faster solve times) are captured without sacrificing predictive accuracy.

3. Automatic Epigraph-Validity Detection: Add a post-training check that verifies whether the downstream objective and constraints are non-decreasing in the surrogate output (per Definition 1). If valid, the system automatically uses the LP epigraph embedding (no branching needed); otherwise, it switches to the ICNN-BB algorithm with vertex-based envelopes.

4. Dimension-Aware Solver Selection: Implement a meta-controller that estimates the input dimensionality of the surrogate. For low-dimensional inputs (e.g., n ≤ 10), use ICNN-BB with full vertex enumeration; for high-dimensional inputs (e.g., n > 10), fall back to ICNN-MIP with standard MIP solvers to avoid exponential vertex-set growth, as demonstrated in the wine blending case (5 25 instance).

5. Adaptive Branch-and-Bound with Early Termination: Enhance the ICNN-BB algorithm with a dynamic branching rule that prioritizes input variables with the widest intervals and largest impact on the concave envelope gap (based on local Lipschitz estimates). Add a root-node feasibility check: if the epigraph embedding is valid, terminate immediately without branching, saving computation.

6. Sparse Concave Envelope Approximation: Replace the full 2n vertex enumeration with a sampled or sparsified vertex set (e.g., using low-discrepancy sequences or active-set methods) when n > 10. This maintains a valid relaxation while reducing LP size, extending scalability beyond the current frontier.

7. Solver-Agnostic Node-Cost Prediction: Train a lightweight regression model that predicts the relative cost of LP-based nodes (ICNN-BB) versus MIP-based nodes (ICNN-MIP) for a given problem instance (solver type, network size, input dimension). Use this to automatically choose between ICNN-BB and ICNN-MIP, as the oil well routing case shows solver-dependent advantages.

8. Convexity-Relaxed Architectures: Extend the system to support partially convex networks (e.g., convex in a subset of inputs) or mixtures of ICNN and FNN layers, enabling the LP-based benefits for problems where only some inputs exhibit convexity, broadening applicability beyond fully convex surrogates.

What the Improved AI System Can Do:

• Automatically decide whether to train an ICNN or FNN based on data convexity and accuracy requirements, ensuring optimization-friendly surrogates without manual tuning.

• Solve downstream optimization problems (e.g., resource allocation, blending, routing) with 10–100× faster solve times on moderate-size instances compared to FNN-MIP baselines, as demonstrated in the food aid and wine blending cases.

• Guarantee zero integrality gap and root-node termination when the epigraph embedding is valid, providing exact solutions without branching overhead.

• Scale to high-dimensional surrogate inputs (n > 10) by switching to MIP-based methods or sparse envelope approximations, avoiding the exponential vertex explosion seen in the 5 25 wine blending instance.

• Provide solver-aware recommendations (e.g., use ICNN-BB with HiGHS, ICNN-MIP with Gurobi) to minimize wall-clock time based on predicted node costs.

• Handle mixed-integer downstream problems (e.g., binary routing decisions in oil well placement) while retaining tighter relaxations than FNN-MIP, reducing node counts by up to 16×.

• Offer a principled fallback: when convexity assumptions fail or validity conditions are violated, the system degrades gracefully to standard MIP formulations without user intervention.

Embedding trained neural networks as surrogates within optimisation problems is an established practice in operations research. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. We advocate input convex neural networks (ICNNs) as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages. First, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances. Second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, we exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains, namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope; this construction is tractable under input convexity but hard for general ReLU networks. On this basis, we develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability, supporting ICNN as the default surrogate when the underlying function is convex, concave, or well-approximated as such.