让热图求解器直接优化解的质量，突破传统模仿学习的性能瓶颈。
CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization
- 将扩散去噪过程建模为马尔可夫决策过程，直接优化解的代价。
- 在多个基准上达到当前最优，解决结构模仿与解质量不匹配问题。
- 适合研究组合优化、扩散模型和强化学习交叉应用的学者。
基于热图的求解器已成为组合优化领域的一种有前景范式。然而，我们指出主流监督学习训练范式存在根本性目标错配：最小化模仿损失（如交叉熵）并不能保证解的代价最小化。我们剖析出两个缺陷：解码盲区（忽略不可微的解码过程）和代价盲区（优先结构模仿而非解的质量）。实验证明，这些内在缺陷导致性能出现硬天花板。为此，我们提出CADO（面向优化的成本感知扩散模型），一个简化的强化学习微调框架，将扩散去噪过程视为马尔可夫决策过程，以直接优化解码后解的代价。引入标签中心奖励机制，将真实标签用作无偏基线而非模仿目标，并采用混合微调实现参数高效适配。CADO在多种基准上取得当前最优表现，验证了目标对齐对于释放热图求解器全部潜力的关键作用。
原文摘要 · Abstract (English)
Heatmap-based solvers have emerged as a promising paradigm for Combinatorial Optimization (CO). However, we argue that the dominant Supervised Learning (SL) training paradigm suffers from a fundamental objective mismatch: minimizing imitation loss (e.g., cross-entropy) does not guarantee solution cost minimization. We dissect this mismatch into two deficiencies: Decoder-Blindness (being oblivious to the non-differentiable decoding process) and Cost-Blindness (prioritizing structural imitation over solution quality). We empirically demonstrate that these intrinsic flaws impose a hard performance ceiling. To overcome this limitation, we propose CADO (Cost-Aware Diffusion models for Optimization), a streamlined Reinforcement Learning fine-tuning framework that formulates the diffusion denoising process as an MDP to directly optimize the post-decoded solution cost. We introduce Label-Centered Reward, which repurposes ground-truth labels as unbiased baselines rather than imitation targets, and Hybrid Fine-Tuning for parameter-efficient adaptation. CADO achieves state-of-the-art performance across diverse benchmarks, validating that objective alignment is essential for unlocking the full potential of heatmap-based solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。