用扩散模型生成整数决策，快速求解复杂优化问题。
Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion
- 基于图结构扩散模型生成整数变量，结合可行性投影保证解可行。
- 在电网调度和投资组合优化中，可行性与解质量显著优于基线方法。
- 无需训练即可适配不同问题，速度比顶尖数值求解器快425倍。
本文提出一种新的学习式方法，用于近似求解混合整数优化问题。这类问题计算复杂，需同时确定离散与连续变量，并满足复杂的组合约束。所提方法采用基于图的生成扩散模型，学习混合整数优化中的离散部分，同时将无训练的可行性投影算子直接融入逆扩散过程，引导中间样本始终趋向可行域。离散变量生成后，剩余问题转化为连续优化，可用现有数值方法高效求解（相较原问题）。该框架名为有约束图扩散（Constrained Graph Diffusion, CGD），具有问题无关性，通过合适的投影算子可适应广泛的混合整数优化问题。我们在交流潮流最优输电切换（ACOPF）和离散投资组合优化上评估了CGD，结果表明其在可行性与解质量上均显著优于学习基线方法，且相比当前最先进的MINLP数值求解器，速度提升高达425倍。
原文摘要 · Abstract (English)
This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems. These problems are computationally challenging, as they require jointly determining discrete and continuous decisions while satisfying complex combinatorial constraints. The proposed method relies on a graph-based generative diffusion model that learns the discrete component of mixed-integer optimization problems while integrating a training-free feasibility projection operator directly into the reverse diffusion process to steer intermediate samples toward the feasible set throughout generation. Once the discrete decisions are generated, the remaining optimization reduces to a continuous problem that can be solved efficiently (relative to the original problem) using existing numerical methods. The resulting framework named Constrained Graph Diffusion (CGD), is problem-agnostic and can accommodate a broad class of mixed-integer optimization problems through suitable projection operators. We evaluate CGD on optimal transmission switching for ACOPF and discrete portfolio optimization, demonstrating substantial improvements in feasibility and solution quality over learning-based baselines while achieving speedups of up to $425\times$ over state-of-the-art numerical solvers for MINLPs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。