Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching

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.

Many real-world problems involve finding the best solution from an enormous number of possibilities. Examples include planning delivery routes, scheduling tasks, and designing networks. While recent artificial intelligence systems have shown promise in tackling these problems, most of them require large collections of high-quality example solutions for training. Obtaining such examples can be expensive or even impossible for many practical applications. In this work, we develop a new training method that allows AI systems to learn how to solve combinatorial optimization problems without requiring pre-computed optimal solutions. Instead of learning from examples, our method learns from the outcomes of its own attempts. A key idea is to identify which decisions along the solution-generation process helped or hurt the final result, and then use this information to improve future decisions. This enables the model to better understand how early choices affect long-term outcomes. We evaluate the approach on several challenging optimization tasks, including finding large independent sets in graphs, planning efficient travel routes, and solving vehicle routing problems. Across these tasks, our method consistently outperforms existing unsupervised approaches and often achieves performance comparable to methods trained with expensive supervision. These results suggest that powerful optimization systems can be learned with significantly less human-provided data, potentially making AI-based optimization more broadly applicable in real-world settings.