acceptodds
Under review as a conference paper at ICLR 2027

DCEmbed: Scalable Optimization over Neural Surrogates

Abstract

Neural surrogates can accelerate large-scale optimization by replacing expensive or intractable model components with more efficient learned approximations, but solving the resulting embedded problems can remain prohibitively costly. For instance, standard exact encodings of neural networks with activations allow for the embedded problem to be solved by mixed-integer solvers, but add large numbers of binary variables to accommodate the nonlinearity of the activations, which can render the problem computationally prohibitive. To address this challenge, we propose DCEmbed, a local heuristic for optimization problems with embedded neural surrogates that leverages the difference-of-convex (DC) representation of the neural network and avoids introducing auxiliary activation binaries. Exploiting shared structure within the DC representation of a ReLU neural network, we derive a reduced-size, exact formulation for its convex components that can be embedded in optimization problems using just two linear inequalities and one continuous auxiliary variable per hidden neuron. Using this formulation, the resulting embedded problem can be solved via an iterative penalty convex-concave procedure, where only the concave portions of the neural terms are approximated at each stage. The original objective, constraints, and any discrete decisions are retained exactly, allowing the use of standard convex or mixed-integer optimization solvers to optimize the host and surrogate jointly at each iteration of the procedure. In experiments on synthetic quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming, our method demonstrates substantially faster progress toward high-quality feasible solutions than approaches using exact mixed-integer embeddings. In particular, DCEmbed achieves lower normalized primal integral than the best exact baseline on the resource allocation problem, while in two-stage stochastic programming it reaches the global surrogate optimum faster than Gurobi ML.

Primary area:
optimization
Keywords:
optimization over neural networks, neural surrogates, mixed-integer optimization, constrained optimization, convex-concave procedure

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_v3i8OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the challenge of solving large-scale optimization problems with embedded neural surrogates. The authors propose DCEmbed, which leverages a difference-of-convex (DC) representation of neural networks to avoid introducing additional binary variables for neural activations. The resulting formulation is integrated into a penalty convex-concave procedure (CCP). Experiments are conducted on synthetic quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming. The proposed method demonstrates substantial computational improvements over exact mixed-integer embeddings.

Critical strengths
  1. The paper addresses an important computational bottleneck in large-scale optimization problems involving neural surrogates.

  2. The paper is well written, clearly organized, and easy to follow.

  3. The experimental results are promising and demonstrate substantial computational improvements over the considered baselines.

Critical weaknesses
  1. Limited methodological novelty. The proposed method builds primarily on existing neural network DC decompositions and the established CCP framework. A clearer explanation of the novel contributions beyond these existing techniques would help better establish the significance of the proposed method.

  2. Limited baseline comparisons. The authors discuss several related methods based on DC decomposition in the related work section, but none of them is included in the experimental comparisons. If these methods are not directly applicable to the considered problems, the authors should provide a more detailed discussion of their limitations and explain why DCEmbed is necessary.

Questions for authors
  1. Scalability with respect to integer variables. How does the proposed method scale as the number of original integer decision variables increases? The experiments appear to consider only a fixed number of integer variables for each problem setting. Additional experiments varying this dimension would help establish the scalability of DCEmbed on larger combinatorial optimization problems.

  2. Global optimality guarantees. Exact mixed-integer embeddings can, in principle, provide global optimality certificates through mixed-integer optimization solvers. Does DCEmbed offer any comparable theoretical guarantees or computable optimality bounds? If not, could the authors provide a more detailed discussion of the trade-off between computational efficiency and solution quality, particularly regarding the loss of global optimality guarantees?

  3. Scalability with respect to network size. In Figure 3, PGD appears to outperform DCEmbed as the neural network size increases. Does this suggest a potential limitation in the scalability of DCEmbed with respect to network size? Could the authors provide additional experiments on larger instances where more expressive neural networks are necessary, to better understand how the relative performance of these methods changes with network size?

4 comments

Thank you for reading our paper and for your valuable feedback!

We appreciate your positive assessment of the significance of the computational bottleneck, the clarity of our paper, and the substantial improvements over the baselines.

We address your questions below:

Novelty

DCEmbed’s key contribution is a unified method for optimizing neural surrogate objectives, inequalities, and equalities jointly with a structured host and its original discrete decisions. We turn a neural DC decomposition into a scalable, composable representation within the host. The subproblems add only continuous variables and linear constraints, allowing mature solvers to optimize them without neural activation binaries.

Central to DCEmbed’s heuristic design are the choices of local neural approximations, their representation, and the methods for solving the subproblems. We show that these choices yield a simple and highly effective algorithm.

Viewed as a general framework, DCEmbed has four key components: (i) the DC decomposition, which determines the convex approximation; (ii) the formulation, which determines how that approximation is represented; (iii) CCP; and (iv) the algorithm for solving the subproblems. This framing highlights its applicability across many different problems and how enhancing any component can improve the method.

Baselines

For the mixed-integer benchmarks, we prioritize established embeddings that retain the host constraints and discrete decisions (e.g. big-MM, Gurobi ML). The cited complementarity and verification-based methods do not apply to mixed-integer hosts.

For the continuous QPs, we use PGD as a standard baseline and have improved it with adaptive step sizes and penalty updates. Liu and Dvorkin penalize complementarity violations, but their penalty scheme is derived for a linear neural objective and continuous polyhedral constraints, which would need to be adapted to our QP setting with neural inequality constraints. Verification-based methods require expressing the entire problem within their bounding framework. We’ve clarified these points in the Related Work.

Scaling with original integer decisions

We clarify that the primary purpose of DCEmbed is to avoid the computational complexity of scaling the surrogate itself, but it remains subject to the computational difficulties of the host model (e.g. many original integer decisions). We test this by increasing scale via network size or the number of embeddings added to the problem.

Still, the water experiment provides evidence for your question. Increasing NN from 25 to 800 increases the original binary decisions from 25 to 800, since each sample introduces one yiy_i. The number of neural embeddings also increases with NN, so this examines growth in both the host and embedded problem. DCEmbed achieves lower NPI than the exact embedding baselines, and avoids adding ~89,160 activation binaries that the big-MM OBBT formulation uses at N=800N=800.

Optimality Guarantees

DCEmbed's use of CCP makes it a heuristic without global optimality guarantees. We agree that this is an important distinction from exact mixed-integer settings, which we configure to prioritize finding feasible incumbents. While we briefly mention theoretical guarantees as a future direction in the conclusion, we provide a more explicit discussion in Section 4.1.

Our focus is therefore on applications where finding a strong feasible incumbent quickly is sufficient. This can be appropriate for neural surrogates, since solving the embedded problem to global optimality does not eliminate the surrogate’s approximation error. Using multiple initializations and retaining the best among them can also improve solution quality (Lipp and Boyd, 2016). When optimality is critical, DCEmbed can provide a feasible warm start for an exact method. We also provide empirical evidence for the effectiveness of DCEmbed. InNeur2SP, DCEmbed recovers the embedded optimum, and we have added Appendix D.4 which compares DCEmbed with certified solutions on small QP and water instances.

Scalability with respect to network size

On the continuous QP, DCEmbed achieves better mean final objectives than PGD across all architectures (Appendix D.2), and lower mean NPI on all but the largest networks, where PGD benefits from cheaper iterations. Larger networks introduce more variables and constraints into the CCP subproblems. However, unlike PGD, DCEmbed can accommodate mixed-integer hosts. In this regime, while the subproblems still scale with network size, DCEmbed’s scaling is far more favorable than competing methods because it avoids adding neural activation binaries. In the water and Neur2SP benchmarks, DCEmbed achieves lower mean NPI than the exact baselines across all sizes. Thus, DCEmbed can realize computational benefits in settings that are beyond the scope of PGD.

Thank you for your questions. We are happy to clarify further!

Thank you very much for your detailed response and additional experiments. The clarifications have addressed most of my concerns. However, I still have a remaining concern:

How does DCEmbed scale with the number of original integer decisions independently of the number of neural embeddings? I would appreciate an additional controlled experiment that fixes the number and size of neural embeddings while varying the number of original binary decisions. This would help clarify how DCEmbed scales with the complexity of the underlying mixed-integer optimization problem independently of the neural surrogate. I would be more than happy to raise my score if this question is properly solved.

Thank you for taking the time to read our response. We are glad it addressed most of your concerns!

We address your remaining concern below:

Scaling with original integer decisions

We have added a controlled experiment that fixes the neural component (i.e. the number and size of embeddings) while varying only the number of original binary decisions. To do so, we reuse the QP benchmark’s trained network (d=3d=3, w=64w=64) in a new host problem with a linear objective and linear coupling constraints. A fixed linear mapping maps the host variables to the 150 input coordinates of 30 network embeddings. This allows us to vary the number of binary host variables while keeping the number and size of the neural embeddings exactly the same. We require a subset of k∈{32,64,128,256,512}k\in\{32,64,128,256,512\} host variables to be binary, while the remaining variables are kept continuous in [0,1][0,1]. The full formulation, experimental details, and result plots are provided in Appendix D.5.

To examine the difficulty of the subsequent problems for DCEmbed, we measure the time taken to solve the first CCP subproblem. In the table below, we report the mean time averaged across three trials.

First CCP subproblem. Mean solution time across three trials with the standard 180s budget.

Original binaries kFirst CCP subproblem (s)
324.09
6427.42
128~180 (time limit)
256~180 (time limit)
512~180 (time limit)

As the number of binary decisions in the original problem grows, the CCP subproblems become increasingly difficult to solve, independent of the neural surrogate. For the largest problem sizes, DCEmbed exhausts the solution budget, although it can still find feasible incumbents during that time.

In the table below, we show the mean objective value reached by each method across three trials (higher is better). All methods are given a 180$s$ budget for solving, and start from the same initialization which has an objective value of 0.

Final objective value. Values below are means across three trials; higher is better.

Original binaries kDCEmbedGurobi MLbig-M + OBBT
3250.2720.00032.306
6450.1600.00031.185
12835.8400.00029.633
25634.3130.00011.813
5120.0270.0000.592

Gurobi ML does not improve on the initialization at any problem size. DCEmbed achieves a higher mean final objective value than the big-MM formulation for k=32k=32-k=256k=256 even when its first CCP subproblem hits the time limit. Throughout this sweep, DCEmbed avoids the 5,760 neural activation binaries introduced by the explicit exact formulation. At the largest problem size, DCEmbed finds a worse incumbent than big-MM with OBBT.

These results show that DCEmbed retains substantial benefits at a fixed neural formulation size, but still remains subject to the computational difficulties of the original mixed-integer host problem as the number of binary decisions increases, similar to the other exact methods.

Thank you so much for the followup response. I will raise my score to 3.

Reviewer_euFgOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces DCEmbed, a method for solving optimization problems that include fixed ReLU neural networks in the objective or constraints, including both inequalities and equalities. Building on an existing difference-of-convex (DC) decomposition of ReLU networks, the authors derive affine expressions for the convex components and an exact epigraph formulation that shares auxiliary variables across them. The formulation requires only one continuous variable and two linear inequalities per hidden neuron. It is then incorporated into penalty CCP, while preserving the residual model and its original discrete decisions. Experiments on neural-constrained quadratic programs, mixed-integer water-treatment allocation, and neural two-stage stochastic programming evaluate primal progress against exact mixed-integer embeddings, PGD, and a larger two-path DC formulation.

Critical strengths

The main strength of this paper is its shared epigraph formulation. Rather than simply showing that a ReLU network can be expressed as a DC function, the authors demonstrate how a shared set of hidden variables can represent multiple convex components across objectives and constraints. The theoretical analysis shows that sharing these variables does not introduce additional relaxation into the CCP subproblem, and the two-path ablation provides experimental support for the resulting computational benefits.

Critical weaknesses

My main concern is the limited scope of the experiments. Most of the stronger comparisons are made against exact mixed-integer formulations, while the continuous heuristic baseline uses fixed step-size and penalty parameters. The paper also provides limited evidence on how sensitive the method is to initialization or how well it handles challenging neural equality constraints.

Questions for authors
  1. How does DCEmbed perform against well-tuned PGD with adaptive step sizes and penalty updates, as well as the related complementarity-based DC method, when all methods use the same initialization and are given the same runtime budget?

  2. How consistent are the results across different initializations? In particular, what are the distributions of final objective values, time to the first improved feasible solution, and neural constraint failure rates? How sensitive are these results to the initial penalty, the penalty cap, and the way equality constraints are handled?

  3. For the QP and water-treatment problems, can the authors report certified optimality gaps on smaller instances that can be solved to optimality and validate the solutions using the original constraint functions or independent application-specific criteria? For Neur2SP, how does DCEmbed scale when the dimension of the first-stage decision variables increases, rather than just the number of scenarios?

2 comments

Thank you for your careful reading and for your valuable feedback!

We appreciate your positive assessment of our shared epigraph formulation, its theoretical justification, and the computational benefits shown by our experiments.

We address your questions below:

Baseline methods for continuous benchmark

Following your suggestion, we added Armijo backtracking and adaptive penalty updates to PGD and reran the complete QP benchmark with the same initializations and budget as DCEmbed. We updated Fig.1 and Appendix D.1-D.2. We report mean NPI (lower is better) across three trials. Bold indicates the best result.

DepthWidthDCEmbedOriginal PGDAdaptive PGD
1640.108.674.93
2640.278.224.01
380.093.912.63
3160.135.524.36
3320.244.784.75
3640.727.974.36
31283.608.535.29
325626.637.102.98
4641.488.515.16
5643.035.965.58
6645.955.423.24

Adaptive PGD improves mean NPI over old PGD at every architecture, but the relative ordering of the methods remains unchanged. DCEmbed achieves lower NPI except at the largest width and depth. Across all architectures, DCEmbed achieves better mean final objectives than both PGD baselines (Appendix D.2).

The complementarity method (Liu and Dvorkin, 2025) derives a penalty scheme for a linear neural objective and continuous polyhedral constraints, which would need to be adapted to our setting which has a quadratic objective and neural inequality constraints. We’ve clarified this in the Related Work.

Results across different initializations?

We appreciate the question, since local methods can be sensitive to initialization. We tested one QP and one water instance using the same ten starts across four penalty settings: the default, τ0/10\tau_{0}/10, 10τ010\tau_0, and τmax/100\tau_\textrm{max}/100, where τ\tau is the penalty. The full results are in Appendix D.3. The times below are medians to the first improved feasible solution, and lower objectives are better.

QP (d=3d=3, w=64w=64); objectives scaled by 103.

SettingMean objective ± SDTime (s)Neural failures
Default−75.591 ± 0.1120.730/10
τ0/10\tau_{0}/10−75.559 ± 0.1160.700/10
10τ010\tau_0−75.571 ± 0.1620.700/10
τmax/100\tau_\textrm{max}/100−75.591 ± 0.1120.740/10

Water (N=100N=100); objective counts non-potable samples.

SettingMean objective ± SDTime (s)Neural failures
Default72.7 ± 1.71.410/10
τ0/10\tau_{0}/1067.9 ± 1.81.450/10
10τ010\tau_075.0 ± 1.91.470/10
τmax/100\tau_\textrm{max}/10072.7 ± 1.71.430/10

All 80 runs returned improved, neural feasible solutions. The QP objectives vary little across starts and penalty settings. The water objectives show some variation (on the order of a couple of samples) across starts and are sensitive to τ0\tau_0. Decreasing τ0\tau_0 by 10×10\times improved the mean by ~4.8 samples.This may be because smaller τ0\tau_0 gives the early iterates more flexibility to explore better solutions.

Certified optimality gaps on smaller instances?

Following your suggestion, Appendix D.4 compares three QP instances (d=3d=3, w=8w=8) and three water instances (N=5N=5) against optimal solutions. DCEmbed uses default settings and a 180s budget, while exact methods receive 30 minutes to prove optimality.

DCEmbed matches the QP reference objectives, with a mean relative objective difference of $5.4\times10^{-7}%$. For water, the mean shortfall is 2.33 potable samples. All solutions satisfy the original optimization constraints. In the water case, we used N=5N=5 so that we could certify optimality within the time limit. Our main experiments are much larger, ranging from N=25N=25 to N=800N=800. In practice, certifying optimality is not practical. At N=800N=800, Gurobi ML fails to even make any progress on improving over the initialization. If optimality is critical, DCEmbed can provide a feasible warm start for an exact method.

“For Neur2SP, how does DCEmbed scale with the first-stage dimension?”

We clarify that the primary purpose of DCEmbed is to avoid the computational complexity of scaling the surrogate itself, but it remains subject to the difficulties of the host model (e.g. many first-stage decisions). Like in Neur2SP, we fix the first-stage dimension and increase the number of scenarios, each of which adds a network embedding.

Still, the water experiment in Section 5.2 provides evidence regarding scaling the number of original decisions. Increasing NN from 25 to 800 increases the original binary decisions from 25 to 800, since each sample introduces one yiy_i. The number of neural embeddings also increases with NN, so this examines growth in both the host problem and the embedded model. DCEmbed achieves lower NPI than the exact embedding baselines across these sizes.

Thank you for your questions. We are happy to provide additional clarification!

Thanks for the reply. I have raised my rating score.

Reviewer_PoGVOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper deals with optimization problems involving terms (in the objective function or constraints) that are represented by a ReLU neural network. It combines three ideas:

  • the DC-decomposition of a neural network as difference of two convex neural networks;
  • a representation of the epigraph of a function represented by a convex ReLU-network in terms of linear inequalites;
  • the convex-concave procedure for minimizing a function represented as a difference of two convex functions. This allows to find (local) minima of the overall optimization problem with a convex-concave procedure (Lipp, Boyd 2016) using the reasonably compact explicit problem formulation. This is complemented by computational experiments assessing the quality of solutions using the 'normalized primal integral' (Berthold 2013, Gasse et al 2022). These experiments show for networks with rather small depth (between 1 and 6) that the newly devised method performs better compared to other standard approaches like Gurobi ML and OBBT that resolve the neural network components in a different way.
Critical strengths
  • The paper combines existing ideas to derive a simple optimization procedure for solving the above described optimization problem more efficiently (on the given experiments) than existing -- arguably more technical -- approaches.
Critical weaknesses
  • It is not clear how the convex-concave procedure is applied to the original problem in Section 4.1. As far as I see, for this to work in the described way, the functions \phi_i and \psi_j of the 'residual model' would have to be convex to actually apply CCP here. However, this does not seem to be properly specified or discussed.

  • The paper uses two existing tools (representation of a neural network as difference of two convex neural network, and representation of a convex ReLU-network by a linear program; see e.g. the paper 'Neural Networks and (Virtual) Extended Formulations' by Hertrich&Loho for another paper combining these two ideas in basically the same way) to rewrite an optimization problem involving terms that are represented by a trained ReLU neural network. This allows to apply an existing algorithm to obtain a new approach to solve such an optimization problem. While it is not a big issue that there is basically no new technical contribution, the paper does not put enough effort into actually elaborating the interplay of these existing techniques. As far as I see, one could strengthen the paper by emphasizing this more as a framework such that any improvement in the three components (convex decomposition, LP representation, DC-programming) leads to algorithmic improvements.

Questions for authors
  • What do you consider the main conceptual new insight of the paper?

  • The basic procedure for creating a DC-decomposition of a trained neural network can create numerical blow-ups as values are accumulated and only subtracted at the end. Did you experience this in your experiments?

  • The considered experiments use rather shallow networks and the terms in addition to the neural network component are rather simple (in particular convex, as far as I see). Do you have any insights into the performance for more complicated structures?

2 comments

Thank you for your careful reading of our paper and constructive feedback!

We appreciate your positive recognition of the method’s simplicity and computational performance on the benchmark problems.

We address your questions below:

Assumptions on the residual model

It’s true that for the desired convex or mixed-integer convex subproblems, we require Y\mathcal{Y} to be convex, ϕ0\phi_0 and ϕi\phi_i to be convex on Y\mathcal{Y} , and each ψj\psi_j to be affine. We included this at the end of the second paragraph below Problem 14 in Section 4.1, but have now moved this to the start of the paragraph to improve clarity.

“What do you consider the main conceptual new insight of the paper?”

The main conceptual contribution of DCEmbed is a unified method for optimizing neural surrogate objectives, inequalities, and equalities jointly with a structured host and its original discrete decisions. We combine a compact, exact, shared epigraph formulation of the neural DC components with penalty CCP to obtain subproblems that add only continuous variables and linear constraints to the host, allowing mature solvers to optimize the combined model without introducing neural activation binaries.

Thank you for highlighting the work by Hertrich and Loho and suggesting the framework perspective. We have added a citation and discussion of their work, which examines DC decompositions and their epigraph formulations to study extension complexity. In DCEmbed, we utilize the epigraph representation for a specific choice of DC decomposition to make optimization over embedded neural surrogates efficient.

DCEmbed is a heuristic whose design exploits the structure of the embedded optimization problem. Central to this are the choices of local neural approximations, their representation, and the methods used to solve the resulting subproblems. We show that these choices yield a simple and highly effective algorithm.

When viewed as a general framework, DCEmbed has four key components that we exploit: (i) the DC decomposition, which determines the convex approximation; (ii) the formulation, which determines how that approximation is represented in the optimization problem; (iii) CCP; and (iv) the algorithm used to solve the sequence of subproblems. We have added a contribution to explain the interaction between these layers. We agree that this framing highlights the generality and applicability of DCEmbed across a variety of different problems, and emphasizes that enhancing any of these components can improve the whole method.

Numerical blowups from DC Decomposition

This is an important numerical consideration. In our experiments, we do observe accumulation of terms in the DC components, with the effect being more pronounced at the deepest tested depth. While the resulting growth and cancellation can potentially lead to numerical issues in solving the subproblems, in our experiments, we did not encounter any such solver failures. Additionally, our evaluations of the neural objectives and constraints directly use the original network.

“Do you have any insights into the performance for more complicated structures?”

Although the tested networks are modest in depth, our experiments establish that even these sizes prove to be difficult for exact mixed-integer embeddings. The present focus on convex and mixed-integer convex hosts highlights important practical problem classes that are supported by mature solvers. DCEmbed is able to keep such subproblems within their original class by adding only continuous variables and linear inequalities to each subproblem.

For more complicated settings, the key consideration is the difficulty of the resulting subproblems. Deeper networks increase the size of the formulation, which increases the difficulty of each CCP iteration. While DCEmbed avoids additional activation binaries, the cost of solving the bigger subproblems remains a limitation. In the case of nonconvex host problems, approximating the neural terms still leaves the host’s intrinsic nonconvexity in each subproblem. In DCEmbed, the same construction could still be used provided we have access to a solver that can handle the difficulty of the original nonconvexities. This is an example where potential advances in algorithms for the host class directly translate to benefits for DCEmbed. While we do not consider such extensions here, their performance ultimately depends on the host structure and the algorithm for solving the subproblem.

Thank you again for your valuable comments and suggestions. We hope the revisions clarify the contribution, assumptions, and practical considerations of our method. Please let us know if there are additional points you wish to discuss!

I thank the authors for their elaborations. They convinced me to stick with my overall positive score.

Comments on the paper

1 comment
Area_Chair_1Mm2OpenReview ↗

Reminder: Reviewer–Author Discussion

Thank you to the reviewers who have already engaged in the discussion and provided valuable feedback. As the discussion deadline is approaching, I would kindly encourage the remaining reviewers to review the authors' responses and share their follow-up comments, particularly on whether their concerns have been adequately addressed.

Authors are also encouraged to respond promptly to any further questions.

Thank you all for your time and contributions to a constructive discussion.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.