无需标注数据，用新方法让扩散模型高效解组合优化问题
Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching
- 将组合优化建模为连续时间马尔可夫链的随机控制问题
- 提出离散伴随动态，实现低方差轨迹级优化信号传播
- 在多个任务上超越无监督基线，接近有监督模型表现
基于扩散的神经求解器在组合优化（CO）中展现出强大潜力，但现有方法通常依赖大量近优解进行监督训练。本文将伴随驱动的轨迹优化方法扩展至离散组合域，将扩散型CO建模为连续时间马尔可夫链上的随机控制问题，并引入离散伴随动力学，实现优化信号在离散生成轨迹中的有效传播。基于此，我们提出组合伴随匹配（CAM），一种面向离散扩散求解器的无监督训练框架，具备结构化且低方差的轨迹级优化信号。实验表明，CAM在多种组合优化问题上持续优于现有无监督扩散基线，性能可与强监督扩散求解器甚至传统求解器相媲美。代码已开源：https://github.com/Shengyu-Feng/CAM。
原文摘要 · Abstract (English)
Diffusion-based neural solvers have shown strong promise for combinatorial optimization (CO), but existing methods typically rely on supervised training with large collections of near-optimal solutions. In this work, we extend adjoint-based trajectory optimization methods to discrete combinatorial domains. We formulate diffusion-based CO as a stochastic control problem over Continuous-Time Markov Chains and introduce discrete adjoint dynamics for propagating optimization signals through discrete generative trajectories. Building on this formulation, we propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion solvers with structured and low-variance trajectory-level optimization signals. Empirically, CAM consistently outperforms existing unsupervised diffusion baselines and achieves performance competitive with strong supervised diffusion solvers and even traditional solvers across diverse combinatorial optimization problems. Our code is available at https://github.com/Shengyu-Feng/CAM.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。