{"id":"67329cf4-adf9-4f57-a76c-9746b1e732e5","arxiv_id":"2608.09707","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"ICNN surrogates admit an LP-only embedding whose epigraph plus concave envelope equals the convex hull of the network's graph, enabling a branch-and-bound solver that avoids binary variables.","lead":"The paper shows that input convex neural networks can be embedded into optimization models without binary variables, using an epigraph bound and a concave envelope that together form the tightest possible continuous relaxation of the network. This gives faster, more scalable optimization when the modeled response is convex or concave, with large speedups on small and medium sized input problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Root termination in Case 1 is not proven: the epigraph embedding is degenerate in y, so the paper's flagship no-branch result may be solver-dependent.","rationale":"Proposition 1, Corollary 2, and Theorem 1 are internally correct: for a fixed input the LP relaxation of the ICNN-MIP attains f, and the epigraph plus vertex-based concave envelope projects exactly onto conv(graph f). The mathematical core is sound. The load-bearing weakness is at the interface between theory and algorithm. The BB's root termination is only certified by a post-hoc gap check; the paper's sufficient condition for validity (h and g non-decreasing in y) does not cover food aid, where y is bounded below and absent from the objective, making the root LP degenerate in y. Consequently, the flagship Case-1 result may not be reproducible with different LP solvers or presolve settings, and the generalized claim that ICNN-BB is network-size independent whenever the epigraph is valid is not supported by a checkable certificate. This does not invalidate the theory, but it strengthens the need for the conditional verdict: before accepting the empirical claims, the root solution should be shown to be independent of solver degeneracy, or validity should be verified by comparing against the exact MIP for each case. The reader's dimension concern is real and related: when validity fails, the algorithm's per-node cost is Σ_s 2^{n_s}, and the 5_25 wine instance already demonstrates failure; our concern is that even the 'successful' food-aid case may rest on an unverified, solver-dependent property.","tokens_in":27213,"tokens_out":24118,"duration_ms":218815,"concrete_test":"Solve the Case-1 root problem (19) with the objective augmented by +ε·z_K for ε=10^{-6}, and repeat with ε=0 using both simplex and barrier-with-crossover in Gurobi. If the optimal x*, the reported z_K*, and the relative gap remain identical across all runs and match the exact MIP optimum, the root termination is robust. If the gap changes or z_K* is not the minimal ICNN output at x*, the root termination is solver-dependent and the claim that the epigraph embedding is valid in Case 1 is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised property \"terminates at the root node whenever the epigraph embedding is valid\" depends on the root LP returning y=f(x). ICNN-BB checks this by forward-pass gap (Algorithm 1, line 13), but the root solve itself has no mechanism to prefer y=f(x) when y does not enter the objective. Definition 1's validity requires the optimal solution to satisfy y=f(x), yet the paper's only sufficient condition (h and g non-decreasing in y) fails exactly in Case 1: the objective (32a) is independent of y and the palatability constraint is y≥0.5, i.e. g(x,y)=0.5−y≤0, which is decreasing in y. In the root relaxation (19), y also has no upper bound, so the LP is degenerate in y and the returned y, hence the reported gap, is solver-dependent. Thus the observed root termination in Tables 2–3 is not a theorem; it may be an artifact of the particular LP solution chosen. This matters because the paper's main practical selling point is exactly this root termination, which is what makes ICNN-BB network-size independent in Case 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies embedding trained input convex neural networks (ICNNs) as surrogates in mathematical optimisation problems. It proves that the LP relaxation of the ICNN-MIP formulation recovers the exact ICNN output for fixed inputs and under direct output minimisation (Proposition 1, Corollaries 1 and 2). It formalises when the epigraph embedding is a valid reformulation (Definition 1), constructs a concave envelope from vertex evaluations (Proposition 2), and proves that adding this envelope to the epigraph yields the convex hull of the ICNN's graph over a box (Theorem 1). On this basis it proposes ICNN-BB, a branch-and-bound algorithm that branches on the surrogate input variables rather than on neural-network activation binaries, and reports three case studies: humanitarian food aid, oil well routing, and wine blending. The theoretical core is largely correct, but the empirical support for several headline practical claims is incomplete, and the algorithm's specification is ambiguous for problem instances with outer integer variables.","tokens_in":27381,"tokens_out":11999,"duration_ms":109502,"significance":"If the results stand, the paper makes a substantial contribution: it provides a tractable construction of the convex hull of the graph of an entire ReLU-based network under input convexity, which is not known for general ReLU networks, and it demonstrates a practical way to avoid binary activation variables for ICNN surrogates. The proofs of Proposition 1, Proposition 2, and Theorem 1 are self-contained and check out, and the manuscript ships reproducibility materials. However, the practical claims of root-node termination and of an LP-only search tree are not fully supported by the theory as written, and the reported experiments therefore need careful re-interpretation before the paper can be accepted.","major_comments":[{"comment":"The root-node termination reported in Tables 2 and 3 is not established by the theory. In the food-aid model the objective (32a) is independent of y and the only y-constraint is the lower bound y >= 0.5 in (32h), so in the root epigraph relaxation (19) y has no upper bound and the LP has many optimal solutions with y > fhat(x). Thus Definition 1(ii) is not satisfied, and the gap check in Algorithm 1 (line 13) is solver-dependent: the algorithm terminates at the root only if the LP solver happens to return an optimal solution with y equal to the ICNN forward-pass value. The paper should either prove that the particular solvers used return such a basic solution for these degenerate LPs, or weaken the claim that ICNN-BB terminates at the root whenever the epigraph embedding is valid, and re-interpret the Case 1 tables accordingly.","section":"Section 4.3, Definition 1, and Case 1 (Eq. (32), Tables 2-3)"},{"comment":"Algorithm 1 is written for the continuous problem (4), but the oil-well routing problem in Case 2 contains binary routing variables y_e in (33l). The paper does not specify how ICNN-BB treats these outer integer variables. If each node subproblem is solved as a mixed-integer program, then the statement in Section 4.3 that the algorithm 'achieves convergence via LP solves throughout the search tree' is inaccurate, and the reported ICNN-BB node counts and per-node times are not directly comparable with those of the MIP baselines unless the inner branching is also reported. The authors should clarify whether outer binaries are handled by an inner MIP solve, by a unified branch-and-bound tree, or by further relaxation, and should report node counts accordingly.","section":"Section 4.3, Algorithm 1, and Case 2 (Eq. (33), Tables 5-6)"},{"comment":"Theorem 1 concerns a single ICNN over its box. In the stacked-surrogate setting used in Case 3, the per-surrogate envelope blocks use independent alpha variables for each surrogate, so the resulting feasible set is the product of per-surrogate hulls rather than the convex hull of the stacked graph. The text should state this explicitly; as written, a reader could infer that Theorem 1 justifies the stacked relaxation as the strongest continuous relaxation of the full multi-surrogate problem.","section":"Section 4.2.2, Theorem 1, and Section 4.3 (stacked surrogates)"},{"comment":"The algorithm's acceptance test in line 14 accepts any relaxation solution with relative gap epsilon <= tau, so the returned point is only approximately feasible for the original constraint y = fhat(x), not exactly feasible. This matters for the reported objectives: in Case 2, for example, the surrogate output enters the objective through (33h), so a one-percent overestimate can inflate the reported oil flow. The paper should state that ICNN-BB returns an approximately feasible solution by design, and should discuss the implications for the numerical comparisons with the exact MIP formulations.","section":"Section 4.3, Algorithm 1 (termination criterion), and Section 5.2-5.4"}],"minor_comments":[{"comment":"The ICNN MSE for the 3_50 network is listed as 9.652e-4, identical to the 2_50 ICNN MSE; if this is not a typo, the duplicate value should be corrected.","section":"Table 1"},{"comment":"The statement that 'the vertex set and LP size grow rapidly with branching depth' is inaccurate: a sub-box of an 11-dimensional box still has 2^11 vertices as long as no coordinate is fixed, so the per-node LP size does not grow with depth. What grows is the number of nodes and hence the total number of vertex evaluations.","section":"Section 5.4.3 (5_25 row)"},{"comment":"The abstract's closing claim that the results support ICNN 'as the default surrogate' is stronger than the experiments warrant, since on the 5_25 wine-blending instance ICNN-BB fails to return a feasible solution and ICNN-MIP is slower than FNN-MIP under Gurobi; the more careful qualification in Section 6 about the input-dimensionality frontier should be reflected in the abstract.","section":"Abstract and Section 6"},{"comment":"The illustrative comparison of FNN and ICNN surrogates for f(x)=x^2 states that the two networks have 'comparable accuracy' but does not report the training or validation errors; adding these numbers would strengthen the point.","section":"Section 3.3"}],"recommendation":"major_revision","confidential_remarks":"The theoretical contribution is real and the proofs of Propositions 1 and 2 and Theorem 1 appear sound. The main risks are overclaiming in the empirical narrative: the root-termination result in Case 1 is solver-dependent under the stated model, and the ICNN-BB algorithm is underspecified for problems with outer integer variables. These issues are fixable within the manuscript's scope, but they require rewriting the relevant claims and possibly re-running or re-presenting the experiments. I would also suggest the authors make explicit that Algorithm 1 returns an approximately feasible solution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The new result here is real: for a trained ICNN over a box, the epigraph plus the vertex-based concave envelope gives the convex hull of the ICNN's graph, and the LP relaxation of the ICNN-MIP is exact for direct output minimization. Proposition 1's induction, Proposition 2's envelope construction, and Theorem 1's convex-hull equality all check out. That is worth a serious referee.\n\nWhat the paper does well: it gives a clean formal account of why ICNN-MIP relaxations are tighter than FNN-MIP relaxations, and it builds a coherent branch-and-bound that branches on input variables rather than activation binaries. The case studies are reproducible (code and data are public), and the low-dimensional speedups are real. Credit where due: the authors do not hide the 5_25 wine failure, and the conclusion correctly notes the exponential vertex cost as the scalability frontier.\n\nNow the soft spots, in proportion. The stress-test note is correct. In Case 1, the palatability constraint y >= 0.5 is the only place y appears, and y is absent from the objective. The root LP is therefore degenerate in y: it has optimal solutions with y > f_hat(x), so Definition 1(ii) is not satisfied for all optimal solutions. The observed root termination means the LP solver happened to return the minimal y, not that the theory guarantees it. This is not fatal, but it changes the claim: root termination is a heuristic observation in Case 1, not a theorem. The fix is easy—add a tie-breaking objective that minimizes y, or prove the solver's returned vertex satisfies y = f_hat(x), or weaken the validity definition to \"there exists an optimal solution\" and then show the algorithm finds it.\n\nSecond, the empirical case for \"ICNN as the default surrogate\" outruns the evidence. There are no repeats and no error bars; the only baseline is big-M FNN-MIP; and the 5_25 wine instance, with 55-dimensional stacked inputs, makes ICNN-BB fail to return any feasible solution. That is a real boundary on the method, and the abstract should say so rather than endorsing ICNN as default.\n\nMinor point: Definition 1 speaks of \"the optimal solution\" without handling multiplicity; the paper should clarify whether validity requires all optimal solutions or just one.\n\nOverall: send it to review. The theoretical core is sound and citable; the empirical claims need repeats, a fix to the root-termination framing, and a more restrained conclusion. This is a solid paper with one over-claimed section, not a paper with a load-bearing flaw.","headline":"Solid theory, over-sold empirics: the convex-hull relaxation is a genuine contribution, but root termination in Case 1 is solver-dependent and 'default surrogate' needs more evidence.","tokens_in":27972,"tokens_out":4253,"would_cite":true,"duration_ms":38719,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"For an input convex neural network over a box, the epigraph together with the concave envelope built from vertex evaluations is exactly the convex hull of the network's graph, giving the strongest continuous relaxation; direct output…","keywords":["input convex neural networks","surrogate modelling","LP relaxation","mixed-integer programming","convex hull","branch-and-bound","concave envelope","epigraph embedding"],"falsifier":"Solve LP (20) at an interior point of a box for any trained ICNN and check whether the resulting value is indeed the least concave function overestimating the network: if a concave overestimator is found that is strictly below the LP value at that point, Theorem 1 fails. The reported 5_25 wine-blending instance, where ICNN-BB explored roughly 72,000 nodes without returning a feasible solution within the 3600 s limit, is the concrete falsifier of the scalability premise.","tokens_in":1700,"feed_emoji":"🧠","tokens_out":3730,"duration_ms":67766,"temperature":0.7,"pith_summary":"Neural networks used as surrogates in optimisation are normally embedded via mixed-integer programs, with one binary variable per ReLU neuron. This paper argues that when the surrogate is an input convex neural network, a network whose output is convex in its inputs, the embedding can be done with plain linear programming. The key result is that over a box domain, the relaxation obtained by sandwiching the network output between its epigraph (lower bound) and a concave envelope built from the 2^n vertex evaluations is exactly the convex hull of the network's graph, the strongest possible continuous relaxation. A branch-and-bound that branches on the input variables then converges without binary variables, and whenever the epigraph embedding is valid it terminates at the root node. If the argument is right, ICNN surrogates can be embedded in optimisation models without the binary activation variables that make large ReLU networks computationally prohibitive.","feed_headline":"Convex neural surrogates turn MIPs into LPs","feed_subtitle":"A vertex-built concave envelope gives the convex hull of an ICNN's graph over a box, so branch-and-bound needs no binary variables.","key_machinery":"The central object is the concave envelope of the ICNN over a box, constructed explicitly as the value function of an LP whose decision variables are the weights of a convex combination of the box's $2^n$ vertices (Proposition 2). This envelope overestimates the convex ICNN, while the epigraph constraints underestimate it; Theorem 1 proves that the two together reproduce the convex hull of the ICNN's graph. The ICNN-BB algorithm carries this machinery across a branch-and-bound tree, branching on input variables and evaluating the ICNN at new vertices as boxes are bisected.","core_discovery":"The central claim is Theorem 1: for a trained ICNN $\\hat{f}$ over a box $X$, the set of points $(x,y)$ satisfying $\\hat{f}(x) \\le y \\le \\bar z(x)$, where $\\bar z$ is the concave envelope obtained by maximising convex combinations of the $2^n$ vertex values of $X$, equals the convex hull of the graph $\\{(x,\\hat{f}(x)) : x \\in X\\}$. Together with the exactness of the LP relaxation under direct output minimisation (Corollary 2), this means an ICNN surrogate can be embedded either as an exact LP when the objective penalises overestimation, or as the tightest possible LP relaxation in general, eliminating binary variables in both cases. The construction is tractable specifically because convexity lets the concave envelope be read off from vertex evaluations; no such characterization is known for general ReLU networks.","pith_inferences":["An a priori validity check for the epigraph embedding is likely to be easy in many practical problems: if the downstream objective and constraints are non-decreasing in the surrogate output, any slack in $y \\ge \\hat{f}(x)$ can be removed, so the LP embedding is exact and no branching is needed.","The convex-hull construction is not tied to the ICNN architecture per se; it should carry over to any convex piecewise-linear or convex Lipschitz function whose values at the $2^n$ vertices are available, which suggests immediate extensions to other convex surrogates such as convex quadratic models or kernel-based convex regressors.","The paper's open direction of sparsified or hierarchical vertex sets translates naturally into a testable trade-off: sampling fewer than $2^n$ vertices yields cheaper but weaker relaxations, and the empirical crossover point at roughly eleven input dimensions in the wine-blending study gives a concrete benchmark for when such approximations would be needed.","The 5_25 wine-blending timeout, with 55 stacked dimensions, indicates that a stacked deployment of many low-dimensional surrogates is more practical than a single high-dimensional surrogate, because vertex enumeration cost is per surrogate rather than over the product domain."],"forward_implications":["For direct output minimisation of an ICNN, the MIP's binary activation variables can be relaxed to continuous ones, so the surrogate embedding becomes an equivalent LP.","Over any box domain, the epigraph plus the vertex-built concave envelope yields the convex hull relaxation of the ICNN's graph, the strongest continuous relaxation available for that surrogate.","The branch-and-bound algorithm branches on the input variables rather than on neuron activations, so its branching dimension is the surrogate's input dimension, not the network's size.","Whenever the epigraph embedding is valid, the algorithm terminates at the root node without branching, making solve time nearly independent of network width in the experiments.","In the food-aid case study, ICNN-MIP and ICNN-BB solved all architectures at the root node, while FNN-MIP timed out on most networks with 50 or more neurons per layer."],"supporting_citations":[{"why":"Introduces the input convex neural network architecture and the epigraph LP representation that the paper builds its LP-based embedding on.","marker":"Amos et al. (2017)"},{"why":"Supplies the big-M mixed-integer formulation for ReLU networks that the paper adapts into the ICNN-MIP formulation and compares against.","marker":"Fischetti & Jo (2018)"},{"why":"Gives the strongest known per-neuron convex hull MIP formulation for trained ReLU networks, which the paper contrasts with its full-graph convex hull result.","marker":"Anderson et al. (2020)"},{"why":"Provides the oil well routing problem and the ReLU surrogate methodology that serves as a baseline case study and as the source of the well and riser datasets.","marker":"Grimstad & Andersson (2019)"},{"why":"Supplies the humanitarian food aid optimisation model with an embedded neural surrogate, used as the first case study.","marker":"Maragno et al. (2023)"},{"why":"Provides the wine blending problem and its surrogate-embedded MIP library, used as the third case study on surrogate input dimensionality.","marker":"Turner et al. (2024)"}],"fun_headline_variants":["ICNN surrogates: exact LP for overestimation","Convex neural nets: vertices give convex hull","No binaries: ICNN surrogate embeds as LP","Tighter LP relaxation from ICNN surrogates","ICNNs: vertex-based convex hull yields LP"],"cache_read_input_tokens":30080,"weakest_assumption_plain":"The practical value of the algorithm rests on the input dimension being small enough that evaluating the network at all $2^n$ vertices of every sub-box remains affordable; the paper's own wine-blending experiment, stacking five 11-dimensional surrogates into 55 dimensions, timed out without returning a feasible solution.","fun_headline_variants_meta":{"raw":{"variants":["ICNN surrogates: exact LP for overestimation","Convex neural nets: vertices give convex hull","No binaries: ICNN surrogate embeds as LP","Tighter LP relaxation from ICNN surrogates","ICNNs: vertex-based convex hull yields LP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001005,"raw_usage":{"total_tokens":4301,"prompt_tokens":1045,"completion_tokens":3256,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":661,"completion_tokens_details":{"reasoning_tokens":3179}},"tokens_in":661,"tokens_out":3256,"duration_ms":21950,"temperature":1.0,"reasoning_tokens":3179,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:12:13.033855+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve LP (20) at an interior point of a box for any trained ICNN and check whether the resulting value is indeed the least concave function overestimating the network: if a concave overestimator is found that is strictly below the LP value at that point, Theorem 1 fails. The reported 5_25 wine-blending instance, where ICNN-BB explored roughly 72,000 nodes without returning a feasible solution within the 3600 s limit, is the concrete falsifier of the scalability premise.","supporting_citations":[{"cited_title":"\\.I ., den Hertog, D., & Fajemisin, A","cited_arxiv_id":null,"evidence_quote":"Supplies the humanitarian food aid optimisation model with an embedded neural surrogate, used as the first case study."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the wine blending problem and its surrogate-embedded MIP library, used as the third case study on surrogate input dimensionality."}],"review_version":1}