Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching
This work is significant for researchers and practitioners in combinatorial optimization, offering an unsupervised method to train diffusion solvers, which reduces the reliance on costly near-optimal solution datasets.
This paper tackles combinatorial optimization using diffusion models without requiring supervised training data. It introduces Combinatorial Adjoint Matching (CAM), an unsupervised framework that leverages discrete adjoint dynamics to propagate optimization signals through discrete generative trajectories, outperforming existing unsupervised diffusion baselines and achieving competitive results against supervised and traditional solvers.
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.