🤖 machine learning

Input convex neural networks as surrogates in mathematical optimisation

This paper advocates for using input convex neural networks (ICNNs) as surrogates in mathematical optimization, demonstrating that their convex architecture enables tighter relaxations and more efficient branch-and-bound algorithms compared to traditional feedforward networks, thereby improving solve times and scalability for problems with convex or concave underlying responses.

Original authors: Yu Liu, Jan Kronqvist, Fabricio Oliveira

Published 2026-08-11

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Yu Liu, Jan Kronqvist, Fabricio Oliveira

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complicated puzzle, like planning the most efficient route for a delivery truck or mixing the perfect batch of wine. Often, the rules of the game are hidden inside a "black box" — a complex computer program (a neural network) that has learned how the world works by looking at millions of examples. You know what goes in and what comes out, but you don't know the secret math inside. To find the best possible solution, you need to open that black box and fit it into your puzzle. The trouble is, the most common type of black box is a jagged, zig-zagging maze. Trying to find the perfect path through it is like trying to solve a Rubik's cube while blindfolded; it's so hard that computers often give up before they find the answer.

This paper tackles that exact headache. It introduces a special kind of black box called an Input Convex Neural Network (ICNN). Think of this not as a jagged maze, but as a smooth, bowl-shaped slide. Because the shape is so predictable (it only curves one way), computers can slide right to the bottom without getting stuck. The authors show that by using these smooth slides instead of jagged mazes, we can solve these optimization puzzles much faster and with much less computing power. They didn't just guess this would work; they built a new mathematical tool to prove it and tested it on real-world problems like delivering food aid and drilling for oil, finding that their method is often a thousand times faster than the old way.

The Problem: The Jagged Maze vs. The Smooth Slide

In the world of operations research (the science of making the best decisions), we often use neural networks to act as surrogates. A surrogate is like a stand-in actor; it mimics a complex, expensive-to-calculate process so we can make decisions quickly. For years, the standard stand-in has been a Feedforward Neural Network (FNN). Imagine an FNN as a landscape made of thousands of tiny, sharp steps and cliffs. It's incredibly accurate at predicting outcomes, but because it's so jagged, it's a nightmare to optimize. To find the best solution, computers have to turn the problem into a giant list of "yes or no" questions (binary variables), which creates a combinatorial explosion. It's like trying to find the lowest point in a mountain range by checking every single rock individually; as the network gets bigger, the time it takes grows so fast that the computer runs out of time.

The authors argue that if the real-world process we are modeling is naturally smooth and curved (like a bowl or a hill), we shouldn't force a jagged FNN to do the job. Instead, we should use an Input Convex Neural Network (ICNN). An ICNN is a neural network with a strict rule: it is only allowed to curve in one direction. It's like a smooth slide or a perfect bowl. This structural constraint makes the math much easier to handle.

The Discovery: Two Ways to Win

The paper explores two main ways to use these smooth ICNNs to solve optimization problems, and they found that both are superior to the old methods.

1. The "Tighter Squeeze" (ICNN-MIP)
First, the authors looked at what happens if we still use the standard "yes or no" method (Mixed-Integer Programming, or MIP) but swap the jagged FNN for a smooth ICNN. They proved mathematically that the "relaxation" (a simplified version of the problem used to guess the answer) for an ICNN is incredibly tight.

The Analogy: Imagine trying to guess the weight of a watermelon. The FNN method gives you a box that is huge and loose; the watermelon could be anywhere inside. The ICNN method gives you a box that hugs the watermelon perfectly.
The Result: Because the ICNN's box is so tight, the computer doesn't need to check nearly as many possibilities. In their tests, the ICNN version solved problems in a fraction of a second that the FNN version couldn't solve even after an hour. In some cases, the ICNN method found the perfect answer immediately without needing to branch out at all, whereas the FNN method got lost in millions of dead ends.

2. The "Slippery Slide" (ICNN-BB)
Second, and perhaps more exciting, they developed a brand-new algorithm called ICNN-BB. This method completely throws away the "yes or no" questions. Because the ICNN is smooth and convex, the authors realized they could describe the entire network using only simple linear equations (like a straight line) without needing any binary variables.

The Analogy: Instead of climbing a jagged mountain with a rope and grappling hooks (binary variables), you just slide down a smooth, frictionless slide.
The Catch: This slide works perfectly if the problem is set up in a specific way (minimizing the output). If the problem is more complex, the slide might have a small gap where it's not perfectly tight. To fix this, the authors built a "concave envelope" — a safety net that sits on top of the slide to catch any loose ends. They combined the slide (epigraph) and the safety net (concave envelope) to create the strongest possible mathematical description of the network.
The Result: Their new algorithm, ICNN-BB, branches directly on the input variables (the things you are trying to decide) rather than the internal neurons. This is a huge efficiency gain. In their tests, this method was often the fastest, especially when the problem wasn't too complex.

The Real-World Tests

To prove this wasn't just math on paper, the authors tested their ideas on three very different real-world scenarios:

Humanitarian Food Aid: They modeled a system to deliver food to people in need, trying to minimize cost while meeting nutritional and taste requirements. The "taste" part was the black box.
- The Outcome: The ICNN methods were incredibly fast. The standard FNN method crashed and burned, taking over an hour and failing to find a solution for larger networks. The ICNN methods solved the same problems in less than a second. Even better, the ICNN-BB method was so accurate that it stopped immediately at the very first step, proving the "slide" was perfect for this problem.
Oil Well Routing: This involved deciding how to route oil from wells to processing facilities, a problem full of tricky physics and binary choices (open or close a pipe).
- The Outcome: Here, the ICNN methods still won, but the race was closer. The ICNN-MIP method solved problems that the FNN method couldn't touch. The ICNN-BB method was the fastest on smaller versions but slowed down on the largest ones because the "safety net" (the concave envelope) got too complicated to calculate when there were too many variables. This showed a clear limit: ICNN-BB is amazing for low-to-medium complexity, but the "safety net" gets heavy if the problem gets too big.
Wine Blending: A winemaker trying to mix grapes from different suppliers to create the best-tasting wine at the lowest cost.
- The Outcome: Similar to the oil problem, the ICNN methods were significantly faster and more reliable than the FNN method. The ICNN-BB method was the champion for small batches, but as the number of blends increased, the computational cost of the "safety net" grew, eventually making the standard ICNN-MIP method a better choice.

The Bottom Line

The paper concludes that Input Convex Neural Networks are the new default choice for optimization problems where the underlying relationship is smooth or curved. They offer a "two-tier" advantage:

If you use them with standard solvers (ICNN-MIP), you get a much tighter, more efficient search than before.
If you use them with their new specialized algorithm (ICNN-BB), you can often solve the problem without any binary variables at all, leading to massive speedups.

However, the authors are careful to note that this isn't a magic bullet for everything. The ICNN-BB method hits a wall when the number of input variables gets too high (like in the wine blending test with 55 dimensions), because calculating the "safety net" becomes too expensive. But for a vast range of problems, this approach turns a computationally impossible nightmare into a quick, smooth slide. The authors suggest that in the future, we might see even smarter ways to build these safety nets or mix convex and non-convex networks to get the best of both worlds.

Technical Summary: Input Convex Neural Networks as Surrogates in Mathematical Optimisation

Problem Statement

Embedding trained neural networks (NNs) as surrogates within mathematical optimisation problems is a standard practice in operations research, particularly when the underlying physical models are inaccessible or computationally prohibitive. The prevailing approach utilizes Feedforward Neural Networks (FNNs) with Rectified Linear Unit (ReLU) activations. While FNNs offer universal approximation capabilities, their piecewise-linear structure requires an exact Mixed-Integer Programming (MIP) reformulation for global optimisation. This reformulation introduces a binary variable for every ReLU unit, leading to a computational burden that scales linearly with network size. Furthermore, the continuous linear programming (LP) relaxation of standard FNN-MIP formulations is often weak, resulting in large search trees and poor scalability for larger networks.

This paper investigates Input Convex Neural Networks (ICNNs) as an alternative surrogate architecture. ICNNs are constrained to produce outputs that are convex with respect to their inputs. The authors address two primary gaps in the literature:

The lack of rigorous analysis regarding the validity of the LP-based epigraph embedding for ICNNs in general optimisation settings (beyond direct minimisation).
The absence of a comparative analysis of the tightness of LP relaxations between ICNN-MIP and standard FNN-MIP formulations.

Methodology

1. Structural Analysis of ICNN-MIP

The authors first derive an MIP formulation for ICNNs (ICNN-MIP) analogous to standard FNN-MIPs but incorporating the specific architectural constraints of ICNNs (non-negative weights for hidden layers and convex, non-decreasing activation functions).

Exactness of Relaxation: They prove that for any fixed input, the LP relaxation of the ICNN-MIP formulation recovers the exact network output. Consequently, when the optimisation problem involves the direct minimisation of the ICNN output, the LP relaxation is exact (zero integrality gap).
Comparison with FNN: In contrast, standard FNN-MIP relaxations can underestimate the network output due to unrestricted weight signs, leading to a non-zero integrality gap. The authors demonstrate that the structural properties of ICNNs inherently yield tighter LP relaxations than their FNN counterparts, even in general embedding scenarios where the output is not directly minimised.

2. Epigraph Embedding and Validity

The paper formalises the conditions under which the epigraph embedding (an LP-based reformulation replacing ReLU units with linear inequalities $y \geq \hat{f}(x)$ ) constitutes a valid reformulation of the original problem.

Validity Definition: The embedding is valid if the optimal solution satisfies the equality constraint $y = \hat{f}(x)$ and yields the same objective value as the original problem.
Limitation: The epigraph embedding is only exact when the problem structure penalises overestimation of the surrogate output (e.g., direct minimisation). In general cases where the surrogate output appears in constraints or terms that reward larger values, the epigraph relaxation may admit solutions where $y > \hat{f}(x)$ , rendering it an invalid reformulation.

3. Strongest Continuous Relaxation (Convex Hull)

To address cases where the epigraph embedding is not valid, the authors construct the strongest continuous relaxation of the ICNN graph over a box domain.

Concave Envelope: They derive a concave envelope of the ICNN output by computing convex combinations of the network's values at the vertices of the input box.
Convex Hull Construction: By combining the epigraph (lower bound) and the concave envelope (upper bound), they prove that the resulting feasible region is exactly the convex hull of the ICNN's graph. This construction is tractable for ICNNs (requiring $2^n$ vertex evaluations where $n$ is the input dimension) but is generally intractable for non-convex FNNs.

4. ICNN-BB Algorithm

Based on the convex hull relaxation, the authors develop ICNN-BB, a specialised branch-and-bound algorithm:

Branching Strategy: Unlike MIP-based approaches that branch on intermediate binary activation variables, ICNN-BB branches directly on the input variables.
Procedure: The algorithm starts with the epigraph embedding at the root node. If the solution is not exact (gap exceeds tolerance), it branches on the input variable with the widest interval, tightening the box domain and re-evaluating the concave envelope at the new vertices.
Termination: The algorithm terminates at the root node if the epigraph embedding is valid; otherwise, it converges to the global optimum as the box domains shrink and the envelope tightens.

Key Contributions

Structural Characterisation: Proved that the LP relaxation of ICNN-MIP formulations has a zero integrality gap for fixed inputs and direct output minimisation, offering a theoretical advantage over FNN-MIP.
Formal Validity Conditions: Defined precise conditions under which the LP epigraph embedding is a valid reformulation, identifying scenarios where it fails (e.g., when overestimation is not penalised).
Convex Hull Construction: Demonstrated that the convex hull of an ICNN's graph over a box domain can be explicitly constructed via the intersection of the epigraph and a vertex-based concave envelope, a property not available for general ReLU networks.
Specialised Algorithm: Developed ICNN-BB, an LP-based branch-and-bound method that avoids binary variables entirely, branching on inputs and exploiting the convex hull relaxation for convergence.
Empirical Validation: Validated the approach across three distinct case studies (humanitarian food aid, oil well routing, and wine blending), comparing ICNN-BB, ICNN-MIP, and FNN-MIP.

Experimental Results

Case 1: Humanitarian Food Aid

Setup: Optimising food basket procurement with a palatability surrogate.
Findings: ICNNs matched FNN accuracy. FNN-MIP failed to solve larger instances within the time limit due to weak relaxations. ICNN-MIP solved all instances at the root node (zero branching) for both HiGHS and Gurobi. ICNN-BB was the fastest, solving all instances in under 0.1 seconds at the root node, confirming the epigraph embedding was valid for this problem.

Case 2: Oil Well Routing

Setup: Maximising oil flow with surrogates for well performance and riser pressure drop, involving combinatorial routing decisions.
Findings: ICNN-MIP consistently required fewer nodes and solved faster than FNN-MIP across all solvers. ICNN-BB outperformed ICNN-MIP significantly when using the open-source solver HiGHS (3–8x fewer nodes, 3–4x faster). However, with the commercial solver Gurobi, the overhead of updating the concave envelope in ICNN-BB sometimes outweighed the benefit of a smaller search tree, making ICNN-MIP faster for larger instances. This highlights a solver-dependent trade-off.

Case 3: Wine Blending

Setup: Minimising cost of grape blends with surrogates for quality prediction, varying the number of blends and input dimensions.
Findings: ICNN-MIP showed superior scalability over FNN-MIP in terms of node count. ICNN-BB was highly efficient for small-to-moderate input dimensions (solving in fractions of a second). However, for high-dimensional inputs (55 dimensions in the largest instance), the exponential growth of the vertex set ( $2^n$ ) in the concave envelope construction overwhelmed the algorithm, causing ICNN-BB to fail to find a feasible solution within the time limit, whereas MIP formulations remained tractable.

Significance and Claims

The paper claims that ICNNs offer a structurally superior alternative to FNNs for optimisation problems where the underlying response is approximately convex or concave.

Tighter Relaxations: The convex architecture inherently provides tighter LP relaxations, reducing the need for branching in MIP formulations.
Exact LP Reformulation: When the problem structure allows, ICNNs admit exact LP reformulations without binary variables, enabling the use of efficient LP solvers.
Scalability Frontier: The authors identify the input dimensionality as the practical scalability frontier for the proposed ICNN-BB algorithm. While it offers substantial speedups for low-to-moderate dimensions by eliminating binary variables, the exponential cost of vertex enumeration limits its applicability to high-dimensional problems without further approximation techniques.

The work suggests that ICNNs should be the default surrogate choice when the underlying function exhibits convexity or concavity, provided the input dimension is manageable for the proposed branch-and-bound approach or the problem structure permits a valid epigraph embedding.