用对偶分解让神经网络约束在大规模整数规划中高效运行
Scalable Mixed-Integer Optimization with Neural Constraints via Dual Decomposition
- 将神经网络约束拆解为整数规划与神经网络两部分，分别用合适算法求解
- 在最大测试集上比传统方法快120倍，且计算成本随网络大小线性增长
- 模块化设计，可无缝替换神经网络结构或优化器，适合工业级部署
将深度神经网络嵌入混合整数规划以实现基于学习的约束决策颇具吸引力，但现有单体线性化方法规模膨胀迅速，难以求解。本文提出一种新型对偶分解框架，通过增广拉格朗日乘子松弛耦合等式 u=x，将问题分解为经典整数规划子问题和受约束的神经网络块。前者由分支定界法求解，后者采用一阶优化，保持模型模块化，整数变量数量不随网络深度增加，每轮迭代开销仅随网络规模线性增长。在公开的 extsc{SurrogateLIB} 基准测试中，该方法展现出显著可扩展性、模块化与适应性：最大测试案例速度提升120倍；神经网络子求解器可从对数障碍内点法无代码切换至投影梯度法，目标值不变；将MLP替换为LSTM骨干网络后，仍可在47秒内完成全量优化，无需定制化调整。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。