DCEmbed: Scalable Optimization over Neural Surrogates

Akshay Sreekumar; Nicolas Christianson; Priya L. Donti; Ellen Vitercik; Ram Rajagopal

math.OCSep 27, 2026

DCEmbed: Scalable Optimization over Neural Surrogates

Authors: Akshay Sreekumar, Nicolas Christianson, Priya L. Donti, Ellen Vitercik, Ram Rajagopal

Organizations: Stanford University Stanford, CA, USA · Johns Hopkins University Baltimore, MD, USA · Massachusetts Institute of Technology Cambridge, MA, USA

Abstract

Neural surrogates can accelerate large-scale optimization by replacing expensive or intractable model components with efficient learned approximations, but solving the resulting embedded problems can remain prohibitively costly. For instance, standard exact encodings of neural networks with ReLU activations allow the 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, we propose DCEmbed, a heuristic for optimization problems with embedded neural surrogates that leverages the difference-of-convex (DC) representation of the network and avoids adding activation binaries. Exploiting shared structure within the DC representation of a ReLU 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, the problem is 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, allowing standard convex or mixed-integer optimization solvers to optimize the host and surrogate jointly at each iteration. In experiments on quadratic programs, mixed-integer resource allocation, and neural two-stage stochastic programming, our method demonstrates much faster progress toward high-quality feasible solutions than approaches using exact mixed-integer embeddings. In particular, DCEmbed achieves $4\times$ 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 $\sim 5\times$ faster than Gurobi ML.

Figures & tables

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Depth	Width	DCEmbed (ours)	Two-path	PGD	Gurobi ML	big-M + OBBT
1	64	$\bm{-0.06527}$	$\bm{-0.06527}$	$-0.05990$	$\bm{-0.06527}$	$\bm{-0.06527}$
2	64	$\bm{-0.06522}$	$\bm{-0.06522}$	$-0.06014$	$0.00000$	$-0.00216$
3	8	$\bm{-0.06531}$	$-0.06529$	$-0.06315$	$\bm{-0.06531}$	$\bm{-0.06531}$
3	16	$\bm{-0.06532}$	$\bm{-0.06532}$	$-0.06203$	$-0.03866$	$\bm{-0.06532}$
3	32	$\bm{-0.06549}$	$-0.06547$	$-0.06267$	$0.00000$	$0.00000$
3	64	$-0.06526$	$\bm{-0.06527}$	$-0.06036$	$0.00000$	$0.00000$

Appendix

Table 1: Synthetic QP objectives (lower is better). Values are averaged over three trials, with zero indicating the initial incumbent objective.

Samples	DCEmbed (ours)	Gurobi ML	big-M + OBBT
25	$\bm{10.00}$	$\bm{10.00}$	$9.33$
50	$\bm{20.33}$	$15.33$	$15.00$
100	$\bm{26.00}$	$17.67$	$13.33$
200	$\bm{26.33}$	$8.33$	$12.67$
400	$\bm{30.33}$	$1.33$	$8.00$
800	$\bm{31.33}$	$0.00$	$4.33$

Appendix

Table 2: Number of potable water samples (higher is better), averaged over three trials.

Scenarios	DCEmbed (ours)	Gurobi ML	big-M	big-M + OBBT
1,728	$\bm{171.5118}$	$\bm{171.5118}$	$\bm{171.5118}$	$\bm{171.5118}$
2,197	$\bm{169.7280}$	$\bm{169.7280}$	$\bm{169.7280}$	$\bm{169.7280}$
2,744	$\bm{169.9166}$	$\bm{169.9166}$	$\bm{169.9166}$	$161.8368$
3,375	$\bm{169.9523}$	$\bm{169.9523}$	$161.5369$	$\bm{169.9523}$
4,096	$\bm{169.1168}$	$\bm{169.1168}$	$161.4644$	$161.4644$
4,913	$\bm{169.4088}$	$\bm{169.4088}$	$161.2606$	$161.2606$

Appendix

Table 3: Neur2SP objective (higher is better), averaged over three trials.

Explore similar work

Aug 10, 2026math.OC

Input convex neural networks as surrogates in mathematical optimisation

Embedding trained neural networks as surrogates within optimisation problems is an established practice in operations research. The prevailing approach uses feedforward neural networks (FNNs) with ReLU activations, whose piecewise-linear structure admits an exact but computationally intensive mixed-integer programming (MIP) reformulation as the networks grow. We advocate input convex neural networks (ICNNs) as structurally superior surrogates when the underlying response is approximately convex or concave. The convex architecture offers two computational advantages. First, the ICNN-MIP formulation tends to yield a tighter linear programming (LP) relaxation than its FNN-MIP counterpart, with no integrality gap in favourable instances. Second, ICNNs uniquely admit an LP-based reformulation via epigraph representations of ReLU activations, though this embedding is not always exact. When it is not, we exploit the properties of ICNNs to construct the strongest continuous relaxation over box domains, namely, the convex hull of the ICNN's graph, bounded below by the epigraph and above by the concave envelope; this construction is tractable under input convexity but hard for general ReLU networks. On this basis, we develop a branch-and-bound algorithm that builds this relaxation at each node, branches directly on input variables rather than intermediate variables as in MIP reformulations, and terminates at the root node whenever the epigraph embedding is valid. Case studies on humanitarian food aid, oil well routing, and wine blending show that ICNN surrogates match FNN accuracy and deliver gains in solve time and scalability, supporting ICNN as the default surrogate when the underlying function is convex, concave, or well-approximated as such.

Yu Liu, Jan Kronqvist, Fabricio Oliveira

Department of Mathematics and Systems Analysis, School of Science, Aalto University, Espoo, Finland · Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden · DTU Management, Technical University of Denmark, Lyngby, Denmark

Mixed-Integer Programming Nonconvex Rectified Linear Unit Networks Neural Network Surrogates

Ask PDF

Apr 24, 2026math.OC

Relaxation-Informed Training of Neural Network Surrogate Models

ReLU neural networks trained as surrogate models can be embedded exactly in mixed-integer linear programs (MILPs), enabling global optimization over the learned function. The tractability of the resulting MILP depends on structural properties of the network, i.e., the number of binary variables in associated formulations and the tightness of the continuous LP relaxation. These properties are determined during training, yet standard training objectives (prediction loss with classical weight regularization) offer no mechanism to directly control them. This work studies training regularizers that directly target downstream MILP tractability. Specifically, we propose simple bound-based regularizers that penalize the big-M constants of MILP formulations and/or the number of unstable neurons. Moreover, we introduce an LP relaxation gap regularizer that explicitly penalizes the per-sample gap of the continuous relaxation at training points. We derive its associated gradient and provide an implementation from LP dual variables without custom automatic differentiation tools. We show that combining the above regularizers can approximate the full total derivative of the LP gap with respect to the network parameters, capturing both direct and indirect sensitivities. Experiments on non-convex benchmark functions and a two-stage stochastic programming problem with quantile neural network surrogates demonstrate that the proposed regularizers can reduce MILP solve times by up to four orders of magnitude relative to an unregularized baseline, while maintaining competitive surrogate model accuracy.

Calvin Tsay

Department of Computing, Imperial College London, South Kensington, SW7 2AZ, United Kingdom.

Surrogate Gradient Rectified Linear Unit Networks Mixed-Integer Programming Regularization Surrogate Models Convex Relaxation

Ask PDF

Mar 22, 2026cs.LG

Joint Surrogate Learning of Objectives, Constraints, and Sensitivities for Efficient Multi-objective Optimization of Neural Dynamical Systems

Gaussian process surrogates dominate constrained multi-objective optimization because they are effective in data-scarce regimes, but their cubic scaling in training samples limits their ability to capture shared structure between objectives and constraints as problems grow in dimensionality. We show that deterministic neural network surrogates, equipped with feature tokenization and adaptive output normalization, match or exceed Gaussian process accuracy, while scaling to high-dimensional output spaces and training on all data including infeasible samples. Jointly training a single Feature Tokenizer Transformer to predict objectives, constraint satisfaction, and parameter sensitivities yields a unified gradient that simultaneously improves objective values, steers toward feasibility, and identifies the most influential parameters: a coherent search signal that disjoint per-output models cannot provide. We validate this on biophysical neural optimization problems of increasing complexity. In the hardest regime, with wide, uninformed parameter bounds where random sampling finds zero feasible solutions, descending the surrogate's learned constraint gradient steers the search into the feasible region and recovers near-optimal solutions where standard surrogate optimization and constrained Bayesian optimization find none.

Frithjof Gressmann, Ivan Georgiev Raikov, Seung Hyun Kim +3

Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign, Urbana, IL · The Grainer College of Engineering, University of Illinois Urbana-Champaign, Urbana, IL · Department of Neurosurgery, Stanford University, Stanford, CA +3

Surrogate Gradient Neural Network Optimization Multi-Objective Optimization Constrained Optimization Gaussian Process Neural Dynamics

Ask PDF