Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching

• URL: http://arxiv.org/abs/2605.30920v1
• Date: Fri, 29 May 2026 07:04:42 GMT
• Title: Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching
• Abstract summary: In this work, we extend adjoint-based trajectory optimization methods to discrete domains.<n>We propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion.
• Score: 46.08543848104545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion [40.25954048196068]
  This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems.<n>The proposed method relies on a graph-based generative diffusion model that learns the discrete component of mixed-integer optimization problems.<n>The framework named Constrained Graph Diffusion (CGD) is problem-agnostic and can accommodate a broad class of mixed-integer optimization problems.
  arXiv  Detail & Related papers  (2026-08-13T10:46:18Z)
• SPREAD: Sampling-based Pareto front Refinement via Efficient Adaptive Diffusion [0.8594140167290097]
  SPREAD is a generative framework based on Denoising Diffusion Probabilistic Models (DDPMs)<n>It learns a conditional diffusion process over points sampled from the decision space.<n>It refines candidates via a sampling scheme that uses an adaptive multiple gradient descent-inspired update for fast convergence.
  arXiv  Detail & Related papers  (2025-09-25T12:09:37Z)
• Diffusion-Sharpening: Fine-tuning Diffusion Models with Denoising Trajectory Sharpening [56.99266993852532]
  Diffusion-Sharpening is a fine-tuning approach that enhances downstream alignment by optimizing sampling trajectories.<n>Our method demonstrates superior training efficiency with faster convergence, and best inference efficiency without requiring additional NFEs.
  arXiv  Detail & Related papers  (2025-02-17T18:57:26Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  Generative diffusion models are popular in various cross-domain applications.<n>These models hold promise in tackling complex network optimization problems.<n>We propose a new framework for generative diffusion models called Diffusion Model-based Solution Generation.
  arXiv  Detail & Related papers  (2024-08-13T07:56:21Z)
• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  Generative Flow Ant Colony Sampler (GFACS) is a novel meta-heuristic method that hierarchically combines amortized inference and parallel search.<n>Our method first leverages Generative Flow Networks (GFlowNets) to amortize a emphmulti-modal prior distribution over solution space.<n>This prior is updated via parallel search in the spirit of Ant Colony Optimization (ACO) leading to the posterior distribution that generates near-optimal solutions.
  arXiv  Detail & Related papers  (2024-03-11T16:26:06Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  Tree ensembles can be well-suited for black-box optimization tasks such as algorithm tuning and neural architecture search. Two well-known challenges in using tree ensembles for black-box optimization are (i) effectively quantifying model uncertainty for exploration and (ii) optimizing over the piece-wise constant acquisition function. Our framework performs as well as state-of-the-art methods for unconstrained black-box optimization over continuous/discrete features and outperforms competing methods for problems combining mixed-variable feature spaces and known input constraints.
  arXiv  Detail & Related papers  (2022-07-02T16:59:37Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  This paper studies a distributed multi-agent convex optimization problem. We show that the proposed algorithm converges linearly with an improved rate of convergence than the traditional and adaptive gradient-descent methods. We demonstrate our algorithm's superior performance compared to prominent distributed algorithms for solving real logistic regression problems.
  arXiv  Detail & Related papers  (2021-08-19T13:19:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.