CADO: Cost-Aware Diffusion Solvers for Combinatorial Optimization through RL fine-tuning

Combinatorial Optimization (CO) problems are essential in various domains, including operational research and computer science, despite their inherent computational challenges. Recent progress in Machine Learning (ML) can be categorized two main approaches: Supervised Learning (SL) and Reinforcement Learning (RL), differentiated by their reliance on high-quality training datasets. While SL methods have successfully mimicked high-quality solutions, RL techniques directly optimize objectives but encounter difficulties with large-scale problems due to sparse rewards and high variance. We propose an RL fine-tuning framework for diffusion-based CO solvers, addressing limitations of existing methods which often ignore cost information and overlook cost variations during post-processing. Our experiments demonstrate that RL fine-tuning significantly improves performance, outperforming traditional diffusion models and proving robust even with suboptimal training data. Our approach also facilitates transfer learning across different CO problem scales.