Efficient Combinatorial Optimization via Heat Diffusion
Combinatorial optimization problems are widespread but inherently challenging due to their discrete nature. The primary limitation of existing methods is that they can only access a small fraction of the solution space at each iteration, resulting in limited efficiency for searching the global optimal. To overcome this challenge, diverging from conventional efforts of expanding the solver's search scope, we focus on enabling information to actively propagate to the solver through heat diffusion. By transforming the target function while preserving its optima, heat diffusion facilitates information flow from distant regions to the solver, providing more efficient navigation. Utilizing heat diffusion, we propose a framework for solving general combinatorial optimization problems. The proposed methodology demonstrates superior performance across a range of the most challenging and widely encountered combinatorial optimizations. Echoing recent advancements in harnessing thermodynamics for generative artificial intelligence, our study further reveals its significant potential in advancing combinatorial optimization.
Code (1)
Tasks
Combinatorial OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimization
Heatmap-based solvers have emerged as a promising paradigm for Combinatorial Optimization (CO). However, we argue that the dominant Supervised Learning (SL) training paradigm suffers from a fundamental objective mismatch…
Reinforcement LearningOmnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization
Bayesian Optimization (BO) has the potential to solve various combinatorial tasks, ranging from materials science to neural architecture search. However, BO requires specialized kernels to effectively model combinatorial…
Neural Architecture SearchTransport, Don't Generate: Deterministic Geometric Flows for Combinatorial Optimization
Recent advances in Neural Combinatorial Optimization (NCO) have been dominated by diffusion models that treat the Euclidean Traveling Salesman Problem (TSP) as a stochastic $N \times N$ heatmap generation task. In this p…
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 …
Reheated Gradient-based Discrete Sampling for Combinatorial Optimization
Recently, gradient-based discrete sampling has emerged as a highly efficient, general-purpose solver for various combinatorial optimization (CO) problems, achieving performance comparable to or surpassing the popular dat…
Combinatorial Optimization