Parallel tempering improves solution quality in graph optimization models
Parallel Tempering for Diffusion-Based Combinatorial Optimization
Machine Learning
Summary
Finding the best solution in complex problems like arranging connections on a graph can be very hard and slow. The paper presents a way to improve current AI models that generate many potential solutions by letting these attempts share information during their search. This method helps the best solutions get stronger while allowing weaker attempts to explore new possibilities and avoid getting stuck. This improves results without needing to retrain the AI and only slightly increases computing time.
What this means in practice
- •For network infrastructure planners: Generate higher quality network designs on graph models with improved sampling efficiency using interaction between parallel solution attempts.
- •For supply chain optimization teams: Enhance combinatorial optimization in logistics networks by reallocating computational effort dynamically to better solution paths without retraining models.
Authors
Arman Mielke, Uwe Bauknecht, Thilo Strauss, Mathias Niepert
Abstract
Discrete diffusion models have emerged as a powerful paradigm for solving combinatorial optimization (CO) problems on graphs by learning to sample high-quality solutions. A common inference-time approach is to generate multiple candidate solutions independently and return the best-performing sample, improving solution quality at the expense of an increase in computational cost. In this work, we introduce PT-Denoise, an inference-time procedure that allows these concurrent denoising trajectories to interact through parallel tempering, without requiring retraining or fine-tuning of the underlying denoiser. Our method assigns a temperature to each diffusion process and allows processes to swap temperatures based on their relative performance. This dynamically reallocates promising, low-energy trajectories to colder, more concentrated sampling regimes while allowing higher-energy states to escape local minima through randomized exploration. Experiments on canonical graph-structured CO problems show that our approach consistently improves the quality of the best solution found, while only adding minimal computational overhead.