- 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
-
The paper addresses an important computational bottleneck in large-scale optimization problems involving neural surrogates.
-
The paper is well written, clearly organized, and easy to follow.
-
The experimental results are promising and demonstrate substantial computational improvements over the considered baselines.
Critical weaknesses
-
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.
-
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
-
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.
-
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?
-
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 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 (, ) 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 host variables to be binary, while the remaining variables are kept continuous in . 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 k | First CCP subproblem (s) |
|---|---|
| 32 | 4.09 |
| 64 | 27.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 k | DCEmbed | Gurobi ML | big-M + OBBT |
|---|---|---|---|
| 32 | 50.272 | 0.000 | 32.306 |
| 64 | 50.160 | 0.000 | 31.185 |
| 128 | 35.840 | 0.000 | 29.633 |
| 256 | 34.313 | 0.000 | 11.813 |
| 512 | 0.027 | 0.000 | 0.592 |
Gurobi ML does not improve on the initialization at any problem size. DCEmbed achieves a higher mean final objective value than the big- formulation for - 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- 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.
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,
DCEmbedhas 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-M, 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
DCEmbedis 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 N from 25 to 800 increases the original binary decisions from 25 to 800, since each sample introduces one yi. The number of neural embeddings also increases with N, so this examines growth in both the host and embedded problem.
DCEmbedachieves lower NPI than the exact embedding baselines, and avoids adding ~89,160 activation binaries that the big-M OBBT formulation uses at N=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,
DCEmbedcan provide a feasible warm start for an exact method. We also provide empirical evidence for the effectiveness ofDCEmbed. InNeur2SP,DCEmbedrecovers the embedded optimum, and we have added Appendix D.4 which comparesDCEmbedwith certified solutions on small QP and water instances.Scalability with respect to network size
On the continuous QP,
DCEmbedachieves 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,DCEmbedcan 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,DCEmbedachieves lower mean NPI than the exact baselines across all sizes. Thus,DCEmbedcan realize computational benefits in settings that are beyond the scope of PGD.Thank you for your questions. We are happy to clarify further!