{"ID":2842756,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.09186","arxiv_id":"2511.09186","title":"Scalable Mixed-Integer Optimization with Neural Constraints via Dual Decomposition","abstract":"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.","short_abstract":"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 coup...","url_abs":"https://arxiv.org/abs/2511.09186","url_pdf":"https://arxiv.org/pdf/2511.09186v1","authors":"[\"Shuli Zeng\",\"Sijia Zhang\",\"Feng Wu\",\"Shaojie Tang\",\"Xiang-Yang Li\"]","published":"2025-11-12T10:32:25Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\"]","methods":"[]","has_code":false}