RODIS: Robust Diffusion Solver to Dataset Quality in Combinatorial Optimization

Abstract

Combinatorial optimization (CO) problems have widespread applications in science and engineering, but they present significant computational challenges. Recent advancements in generative models, particularly diffusion models, have shown promise in bypassing traditional optimization solvers by directly generating near-optimal solutions. However, existing diffusion solvers are highly sensitive to the quality of the training dataset, particularly the number of problem instances for training and the optimality of their labels. Notably, we observe an exponential scaling law between the performance of diffusion-based solvers and the number of near-optimally labeled instances needed. When training instances are scarce or sub-optimally labeled, diffusion-based solvers suffer significant performance degradation. To enhance the robustness of diffusion solvers to dataset quality, we propose a robust diffusion solver for combinatorial optimization capable of learning from sub-optimally labeled instances follows a two-stage generate-then-decode framework, integrating an objective-guided diffusion model, further reinforced by classifier-free guidance, to produce solutions that surpass the optimality of the training dataset. Experiments demonstrate the improved robustness in \myalg compared to the diffusion-based solver baseline, in a range of combinatorial optimization benchmark tasks such as TSP (Traveling Salesman Problem) and MIS (Maximum Independent Set).