Scalable optimization method speeds up solving neural network embedded problems
DCEmbed: Scalable Optimization over Neural Surrogates
Machine Learning
Summary
Optimization problems that include neural networks can be very slow to solve because of how these networks are represented mathematically. The authors developed DCEmbed, a new way to represent neural networks that avoids adding many complicated binary variables. This method breaks down the neural network into simpler parts and uses an iterative procedure to find solutions faster. Experiments show that DCEmbed reaches good solutions much quicker than existing exact methods, especially in resource allocation and two-stage decision problems.
What this means in practice
- •For operations research teams: Solve complex resource allocation problems with embedded neural network models more quickly and efficiently.
- •For supply chain planners: Use faster two-stage stochastic programming that incorporates neural network surrogates for improved decision-making under uncertainty.
Authors
Akshay Sreekumar, Nicolas Christianson, Priya L. Donti, Ellen Vitercik, Ram Rajagopal
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.