Scalable Mixed-Integer Optimization with Neural Constraints via Dual Decomposition
This addresses scalability issues in optimization for researchers and practitioners in operations research and machine learning, offering a modular and adaptable solution, though it is incremental as it builds on existing dual-decomposition methods.
The paper tackles the problem of embedding deep neural networks into mixed-integer programs for decision-making with learned constraints, which often becomes intractable due to large linearizations, and introduces a dual-decomposition framework that splits the problem into MIP and NN subproblems, resulting in a 120x speedup on the largest test case compared to an exact Big-M formulation.
Embedding deep neural networks (NNs) into mixed-integer programs (MIPs) is attractive for decision making with learned constraints, yet state-of-the-art monolithic linearisations blow up in size and quickly become intractable. In this paper, we introduce a novel dual-decomposition framework that relaxes the single coupling equality u=x with an augmented Lagrange multiplier and splits the problem into a vanilla MIP and a constrained NN block. Each part is tackled by the solver that suits it best-branch and cut for the MIP subproblem, first-order optimisation for the NN subproblem-so the model remains modular, the number of integer variables never grows with network depth, and the per-iteration cost scales only linearly with the NN size. On the public \textsc{SurrogateLIB} benchmark, our method proves \textbf{scalable}, \textbf{modular}, and \textbf{adaptable}: it runs \(120\times\) faster than an exact Big-M formulation on the largest test case; the NN sub-solver can be swapped from a log-barrier interior step to a projected-gradient routine with no code changes and identical objective value; and swapping the MLP for an LSTM backbone still completes the full optimisation in 47s without any bespoke adaptation.