Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching

Shengyu Feng, Tarun Suresh, Yiming Yang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:30359-30378, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-feng26o, title = {Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching}, author = {Feng, Shengyu and Suresh, Tarun and Yang, Yiming}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {30359--30378}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/feng26o/feng26o.pdf}, url = {https://proceedings.mlr.press/v306/feng26o.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching %A Shengyu Feng %A Tarun Suresh %A Yiming Yang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-feng26o %I PMLR %P 30359--30378 %U https://proceedings.mlr.press/v306/feng26o.html %V 306 %X 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.
APA
Feng, S., Suresh, T. & Yang, Y.. (2026). Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:30359-30378 Available from https://proceedings.mlr.press/v306/feng26o.html.

Related Material