2608.09707-Input convex neural networks as surrogates in mathematical optimisation

Introduction to the show: ident: Paper Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Input convex neural networks as surrogates in mathematical optimisation".

Jane: The paper was written by Yu Liu, Jan Kronqvist and Fabricio Oliveira from .

Tom: Stay tuned as we take you through the paper and discuss its implications.

Paper summary: Tom: We're getting started with a paper that's been making the rounds in the operations research community. It takes a hard look at how we embed trained neural networks inside optimisation models, and it makes the case that the network architecture itself should be part of your modelling decision. Jane, what's the core argument?

Jane: The core argument is that a special kind of network called an input convex neural network is structurally better suited for surrogates whenever the underlying function looks approximately convex or concave. The standard approach with ReLU feedforward networks needs one binary variable per neuron, which gets expensive fast. ICNNs have non-negative weights, and that convexity lets you relax or even remove those binaries.

Tom: That's a big claim.

Jane: And they back it up with three real case studies. In the food aid problem, the classical FNN formulation hits the 3600 second time limit on the larger networks, while the ICNN solves basically at the root node, in about 0 point 06 seconds.

Lu: There's a precise reason for that. Proposition 1 in the paper shows that when you minimise the ICNN output, the LP relaxation of the MIP formulation is exact. You can relax all the binary activation variables and you still get the true network output. For a standard FNN, that pointwise exactness fails because its weights have mixed signs.

Meng: And the most beautiful part is the relaxation theory. They build a concave envelope of the ICNN from evaluations at the vertices of the input box, and combine it with an epigraph representation. Together those two bounds form the convex hull of the ICNN's graph over that box. That's the strongest continuous relaxation you could possibly get, and no counterpart exists for general ReLU networks.

Jane: So there are really two routes to use. You can plug the ICNN into a standard MIP solver through the ICNN-MIP formulation and benefit from the tighter relaxation. Or you can use their custom branch-and-bound, which branches on the input variables instead of the neuron activations, and often avoids binaries altogether.

Lalam: Stepping back, this changes how people should think about surrogates altogether. The bottleneck in surrogate-based optimisation has moved from training the network to encoding it correctly inside the solver. Convexity is a structural handle that makes that encoding tractable, so choosing the architecture becomes part of the optimisation problem, not an afterthought.

Tom: That framing carries through every section, and the highlights page at the front lays out exactly these claims. Let's look at how they phrase it there.

Page 1 of the paper: Tom: So we've got the big picture. This first page is the highlights, and it reads almost like a theorem list. Four bullet points, each one a strong claim about exactness or relaxation strength.

Jane: The one that jumps out at me is the first: ICNN-MIP admits exact LP relaxations when minimising the ICNN output. That's an unconditional structural statement, and the paper proves it as Proposition 1. On this page it's just stated, but it anchors everything else.

Lu: Then the second and third bullets work as a pair. You bound the ICNN from below with the epigraph and from above with the concave envelope, and the combination gives you the convex hull of the ICNN's graph. The phrase they use is "the strongest relaxation," and Theorem 1 later justifies that literally.

Meng: What's remarkable is the asymmetry with general networks. For a standard ReLU network, per-neuron convex hulls are known, but the intersection of those doesn't give you the convex hull of the whole input-output mapping. For an ICNN, the global convex hull is available from vertex evaluations, and the cost scales with the input dimension.

Jane: And the fourth bullet introduces the branch-and-bound that exploits this relaxation. The key detail is that it branches directly on input variables, not on intermediate activation variables. That's a different search space altogether, and it's what lets the algorithm avoid the binary explosion.

Tom: The page also carries the author list — Yu Liu, Jan Kronqvist, and Fabricio Oliveira, across Aalto, KTH, and DTU. And the case studies bullet promises faster, more scalable solutions, demonstrated across food aid, oil well routing, and wine blending.

Lalam: What I like about this page is that it's honest about scope. The phrase "when minimising the ICNN output" in the first bullet already hints at the caveat they develop later: the exactness depends on the objective actually penalising overestimation. If your embedding rewards larger outputs, the epigraph relaxation can be invalid, and that's precisely when the envelope and the branching come in.

Jane: So the highlights are a roadmap of the proofs, not just a summary. The next pages build the architecture and show why the LP representation is exact in the first place.

Page 5 of the paper: Tom: Recap: page 1 gave the claims. Now we're at the architecture section, where they show what an ICNN actually is and why inference admits an LP. Jane, what's the key structural constraint?

Jane: Two things. The layer weights are non-negative, except for the first layer, and the activation function must be convex and non-decreasing. ReLU satisfies that. On top of that, they add skip connections from the input layer to every subsequent layer, weighted by matrices S_k, and those improve representation capacity without breaking convexity.

Lu: The convexity argument is elegant. A non-negative weighted sum of convex functions stays convex, and composing that with a convex non-decreasing function preserves convexity. Because the skips are linear in the input, they fit right in as convex functions too. So by induction, the whole network maps inputs to outputs convexly.

Meng: Then comes the LP representation, which is the heart of the computational gain. Instead of writing each ReLU as an equality with a binary variable, they write each layer as a linear inequality, z_{k+1} at least the pre-activation value, and z_k non-negative. No binaries anywhere.

Jane: But there's a subtlety. Those inequalities only enforce that the output is above the true network value. The reason the LP still recovers the exact forward pass is that the objective minimises z_K. At optimality, at least one of those inequalities must be tight, and that pins down the exact ReLU computation.

Tom: So the optimisation objective is doing the work of the activation function. That's clever, but it also sounds fragile.

Jane: It is exactly that fragility that the paper returns to. The exactness is tied to minimising the output. In a general embedding where the output appears in constraints or with different objective signs, the slack in those inequalities can be exploited, and the LP becomes a relaxation instead of an exact reformulation.

Meng: The skip connections deserve attention too. They're what give ICNNs enough expressive power to be competitive surrogates. Without them, the network would struggle to represent functions that aren't purely hierarchical. With them, the paper later shows the accuracy matches standard FNNs on all three case studies.

Lalam: Placing this in context, the LP inference result itself goes back to Amos and colleagues. What this paper adds is a systematic treatment of when that LP representation stays valid once embedded, and what to do when it doesn't. That's the gap in the literature it fills.

Jane: And the next page takes the first step in that direction, proving the exactness of the MIP relaxation for fixed inputs.

Page 9 of the paper: Tom: Quick recap: we've seen the architecture and the LP inference. Now we're on the page where they state Proposition 1. What does it actually establish?

Jane: It establishes that for a fixed input, minimising the output over the LP relaxation of the ICNN-MIP gives exactly the true ICNN output. The MIP formulation is the big-M style encoding with binary activation variables, and Proposition 1 says its integrality gap is zero at every fixed input.

Lu: The proof is a beautiful induction. You take any feasible point of the LP relaxation, and because the weights are non-negative and the ReLU is non-decreasing, you can show that every layer activation is componentwise at least the exact forward-pass activation. So the output can never come in below the true network value.

Meng: And the other direction is trivial, because the exact forward pass with its valid binary pattern is itself feasible in the relaxation. So the minimum is sandwiched exactly at the network output. Negative weights in an FNN break the induction step, which is why FNN-MIP relaxations can underestimate.

Jane: What follows is Corollary 1, which connects this result to the epigraph formulation. The pointwise values of the LP relaxation, collected over the whole input domain, generate the epigraph of the ICNN. So the LP relaxation and the epigraph formulation are essentially the same object.

Tom: And Corollary 2 extends this to the case where you're directly minimising the surrogate output over its input domain. There the LP relaxation is exact too, the binary variables are unnecessary for the optimal value.

Lalam: The bigger picture here is that this gives the first rigorous comparison between ICNN-MIP and FNN-MIP relaxations. The literature had been using ICNN-MIP pragmatically, but nobody had pinned down why it helps. This induction argument is that missing piece, and it's the reason the numerical experiments later show such dramatically smaller search trees.

Jane: One thing I appreciate is the modesty of the claim. It's exact for fixed inputs and for direct output minimisation. But general embeddings where the output isn't minimised require a different apparatus, and that's exactly where the next pages turn.

Page 13 of the paper: Tom: Where we are: the MIP relaxation is exact when you minimise the ICNN output, and now the paper shifts to general embeddings, where the surrogate output can be coupled with other constraints. What happens there?

Jane: They introduce formulation (19), which is the epigraph embedding: you replace the equality y equals f-hat of x with linear inequalities, the layer-wise constraints from the LP. This is a relaxation of the original problem, because the relation is no longer enforced as equality. The question is whether it's a valid reformulation.

Lu: They formalise validity with two conditions. The relaxed problem must have the same optimal objective value as the original, and at the optimal solution the ICNN constraint must be active, so the relaxation output equals the true network output. If the objective and constraints are non-decreasing in the surrogate output, you can always tighten any slack without hurting feasibility.

Meng: But in practice, verifying that ahead of time is hard. And the paper makes an important observation: this validity issue isn't specific to the epigraph embedding. It also afflicts the LP relaxation of the ICNN-MIP. When the output isn't minimised, the relaxed activation variables can take values that don't correspond to any true forward pass.

Jane: Right, and that's the point where the earlier exactness results stop applying. The paper is honest that the epigraph route only works when the geometry of the outer problem aligns with the surrogate's convexity. Otherwise you need something to bound the ICNN from above as well as from below.

Tom: So the lower bound is the epigraph, and the missing piece is an upper bound. That's exactly the concave envelope they construct next.

Lalam: And this validity question is the conceptual core of the whole paper. Most previous work either assumed the epigraph embedding was fine or ignored the issue entirely. Here they make it precise, give it a name, and then design an algorithm that detects the failure and closes the gap.

Lu: The earlier comparison with FNN-MIP feeds directly into this. The FNN relaxation shows a visible pointwise gap while the ICNN's is zero, and that contrast carries into the general embedding discussion. ICNN-MIP still helps even when exactness is lost.

Jane: So the page ends with the problem statement: construct a concave envelope, then build a branch-and-bound around it. The construction itself is on the next pages.

Page 17 of the paper: Tom: Recap: the epigraph gives a lower bound on the ICNN output, and the missing upper bound is the concave envelope. Now we're on the page where the envelope becomes explicit.

Jane: The construction is remarkably simple. Over a box domain, the ICNN output at any point is bounded above by a convex combination of its values at the box's vertices. So they introduce auxiliary variables alpha that decompose any input x as a convex combination of the 2 to the n vertices, and the envelope value is the corresponding combination of the vertex outputs.

Lu: That's Proposition 2. The proof that it's the true concave envelope is a classic two-part argument: feasibility shows it overestimates the ICNN, and then any other concave overestimator is shown to be at least as loose, because concavity forces it to respect the vertex values.

Meng: Then formulation (26) is the augmented embedding. It sandwiches the output z_K between the epigraph constraint from below and the envelope constraint from above. What I find neat is that you don't need to solve a maximisation to impose the envelope; the existence of the alpha variables with z_K no larger than the corresponding combination of vertex outputs is exactly equivalent to being below the envelope value.

Jane: And Theorem 1, stated on this page, collects everything. The projection of that augmented feasible set onto the input-output space is precisely the convex hull of the ICNN's graph over the box. The epigraph set and the envelope set are both convex, they both contain the graph, and their intersection is exactly the convex hull.

Tom: So this is the strongest continuous relaxation you can obtain by relaxing the ICNN constraint alone. Any convex relaxation must contain the graph, and therefore the convex hull. The word "strongest" is justified.

Lalam: The practical cost is important too. The construction needs a forward pass at every vertex, so the input dimension drives the cost, not the number of neurons. For the food aid problem with 25 inputs, the vertex set becomes enormous, which is why the root node there doesn't build the envelope at all. The algorithm only builds it on sub-boxes when it actually needs to branch.

Jane: And that's the design of Algorithm 1, which is where the paper goes next: use the cheap epigraph at the root, then bring in the envelope locally as you branch.

Page 21 of the paper: Tom: Where we stand: the envelope gives the strongest relaxation on any box. The page we're on now turns that into Algorithm 1, the branch-and-bound procedure. Jane, how does it work?

Jane: The root node solves just the epigraph embedding, which is cheap. Then you take the optimal input, run a forward pass through the ICNN to get the true output, and compare it with the relaxation's output. The relative gap epsilon is their difference divided by the true output's magnitude.

Lu: If that gap is within a tolerance tau, you prune by optimality and update the incumbent. If the epigraph embedding was valid all along, this happens at the root and the algorithm terminates immediately without branching. That's exactly what happens in the food aid case study.

Meng: Otherwise, you branch on the input variable with the widest interval, bisect it at the midpoint, and build the envelope relaxation on each child sub-box. The vertex evaluations of the children are inherited from the parent where possible, though the implementation just recomputes them since forward passes are cheap.

Jane: There are three pruning rules: infeasibility when the subproblem has no solution, bound when the node's objective already matches or exceeds the incumbent, and optimality when the relative gap falls under tau. The traversal is breadth-first.

Tom: What's striking is that branching happens on the input variables, not on the neuron activations. The search tree is over the input dimensions, so its depth is governed by the original decision variables, not by the network width.

Lu: And they mention parallelisation: all subproblems at the same depth are independent, so you can solve them concurrently. That maps naturally onto multi-threaded or distributed solvers.

Jane: Finite termination follows from the fact that the ICNN is continuous and piecewise linear. As you keep halving the box, the concave envelope converges uniformly to the ICNN, and eventually the gap drops below any positive tolerance. The whole search stays LP-based.

Meng: For multiple surrogates, the extension stacks the inputs and treats each surrogate's vertices separately, so the vertex cost grows as a sum rather than a product. The gap is then the worst case across all surrogates.

Lalam: So the algorithm is a careful answer to the validity question from the earlier pages. It doesn't assume the epigraph works; it checks, and only pays for the envelope where the relaxation is genuinely loose. The case studies show where that strategy wins and where it hits its limits.

Tom: Let's look at the first case study then, food aid, and what actually happened in the experiments.

Page 25 of the paper: Tom: Quick recap: we have the algorithm, and now the case studies put it to work. The first one is food aid, and this page reports how the surrogates were trained. Jane, what did they find?

Jane: The problem is from Maragno and colleagues, minimising procurement and transportation costs for a food basket with 25 commodities, where palatability is modelled by the neural network. The dataset has 5000 samples with 25 features and one label, split 80/20. A pre-screening indicated an approximately concave response, so they trained the ICNNs on the negated target.

Lu: They trained ICNN and FNN pairs across six architectures: two or three hidden layers with 10, 50, or 100 neurons. What matters is that the ICNN matches the FNN on validation error. In the 3_10 and 3_50 architectures the ICNN is actually more accurate, for example 8 point 031 versus 12 point 348 times ten

Page 8 of the paper: Tom: Quick recap: we've covered the theory and the first case study, and now we're on the oil well routing page, which is all about training the surrogates.

Jane: Right, and this page is notable because there are nine surrogates, not one. Eight well curves relate pressure to oil flow, and a shared riser model predicts separator pressure from flows and manifold pressure.

Tom: The well data is tiny, only 20 to 26 simulator samples per well. They don't even hold out a validation set, they train on everything.

Jane: That's fine because the data is noiseless, straight from the simulator. The riser dataset is much bigger, around 4000 samples, so there they do a proper train/validation split.

Tom: And the shapes match what you'd expect physically. Well response is concave, so they train on negated targets; riser response is convex, so they train on the original target. They use the same preliminary diagnostic we saw earlier to decide that.

Jane: The accuracy pattern is interesting. On the wells, ICNN and FNN are essentially tied, and sometimes the ICNN is even better. On the riser, the convexity restriction costs an order of magnitude in mean squared error.

Tom: But they argue that's still acceptable because the error is tiny relative to the output scale. The riser pressure predictions remain physically plausible.

Jane: So the trade-off is real but manageable. You give up some fidelity on one surrogate to gain the structural advantage in optimisation, and the wells, which are the ones that multiply with instance size, don't suffer at all.

Tom: Training times are also short, a few seconds per surrogate, so the whole pipeline stays cheap. The real cost shows up later when you embed these networks in the optimisation model.

Jane: That sets up the real test. This case study has binary routing decisions on top of the surrogates, so the optimisation problem is much harder than the food aid one. The next page shows how the three methods cope as the number of wells grows.

Page 9 of the paper: Tom: Quick recap: we've covered the food aid and oil well case studies, and now we're on the wine blending problem on page 33.

Jane: Wine blending is the third test case, and the first thing that jumps out is the input dimension. Each surrogate takes an 11-dimensional feature vector, so you're dealing with much higher-dimensional inputs than the single-pressure oil wells or the 25-commodity food basket.

Tom: And the training results come before the optimisation results. They pre-screened and found a convex response, so they train the ICNN on the original target, no negation needed.

Jane: That's a nice contrast with the first two cases. Food aid was concave, oil wells had a mix, and now it's convex. The diagnostic works each time.

Tom: The accuracy numbers are almost identical. ICNN gets 0 point 445 validation MSE, FNN gets 0 point 434. That's a tie for practical purposes, and it holds even with 11 inputs and three hidden layers of 20 neurons.

Jane: Training times are also close, 2 point 8 seconds for the ICNN versus 2 point 3 for the FNN. So the convexity restriction just isn't costing you here.

Tom: But the real novelty is the scaling structure. You have n blends, and each blend adds another 11-dimensional surrogate. The supplier count grows as five times n, so the whole model gets bigger in every direction.

Jane: And that's where ICNN-BB's envelope construction starts to feel the strain. Each surrogate has its own 11-dimensional box, and the vertex set grows as 2 to the 11 per blend. When you have five blends, the combined input space is 55-dimensional.

Tom: So this is a genuine stress test for the branch-and-bound, not just another accuracy comparison. The paper says this is the first case where the epigraph embedding isn't immediately valid at the root.

Jane: Right, and that's why the optimisation results on the next page are so telling. They show ICNN-BB winning big on the smaller instances, then hitting a wall at 5_25.

Tom: Let's look at that next, because that wall is exactly where the input dimension overwhelms the envelope construction.

Conclusion: Tom: We've reached the end of this one, so let's pull it together. In one sentence: this paper shows that input convex neural networks give you both a tighter MIP relaxation and a way to eliminate binary variables entirely, with real speedups on three practical problems.

Jane: The theoretical core is genuinely clean. For an ICNN, the LP relaxation of the MIP is exact when you're minimising the output, because the non-negative weights keep the induction argument going. Standard FNNs can't offer that guarantee.

Tom: And when the epigraph embedding isn't valid, they add a concave envelope built from vertex evaluations. Combined with the epigraph, that gives the convex hull of the network's graph — the strongest continuous relaxation you can get, and it only works because of the convex architecture.

Jane: Their branch-and-bound builds on that relaxation and branches on the input variables rather than the activation variables. In the food aid case it stops right at the root because the embedding turned out to be exact. That's a huge practical win.

Tom: The oil well case showed the more realistic scenario — the epigraph isn't valid there, so it does branch. Against HiGHS, ICNN-BB wins convincingly. Against Gurobi, the standard MIP with ICNN is often faster because Gurobi's nodes are so cheap.

Jane: Then the wine blending case exposed the limitation. With five eleven-dimensional surrogates, the vertex enumeration blows up, and ICNN-BB can't keep up. So the method shines at low input dimension, and the MIP route takes over when dimension grows.

Tom: That's a fair place to leave it. You get a solid theoretical structure plus practical guidance on when to use which route. And the code is public, so people can test it on their own surrogates.

Jane: I'd say ICNNs deserve a serious look as a default surrogate any time the underlying function is roughly convex or concave, not just as a niche architecture.

Tom: We'll be back with the next paper on the queue. Thanks for listening, and see you then.