Accelerating Diffusion-based Combinatorial Optimization Solvers by Progressive Distillation
Graph-based diffusion models have shown promising results in terms of generating high-quality solutions to NP-complete (NPC) combinatorial optimization (CO) problems. However, those models are often inefficient in inference, due to the iterative evaluation nature of the denoising diffusion process. This paper proposes to use progressive distillation to speed up the inference by taking fewer steps (e.g., forecasting two steps ahead within a single step) during the denoising process. Our experimental results show that the progressively distilled model can perform inference 16 times faster with only 0.019% degradation in performance on the TSP-50 dataset.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationDenoisingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
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 …
DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
Neural network-based Combinatorial Optimization (CO) methods have shown promising results in solving various NP-complete (NPC) problems without relying on hand-crafted domain knowledge. This paper broadens the current sc…
Combinatorial OptimizationDenoisingTraveling Salesman ProblemGRASP: Accelerating Shortest Path Attacks via Graph Attention
Recent advances in machine learning (ML) have shown promise in aiding and accelerating classical combinatorial optimization algorithms. ML-based speed ups that aim to learn in an end to end manner (i.e., directly output …
Combinatorial OptimizationGraph AttentionDeep Symbolic Optimization for Combinatorial Optimization: Accelerating Node Selection by Discovering Potential Heuristics
Combinatorial optimization (CO) is one of the most fundamental mathematical models in real-world applications. Traditional CO solvers, such as Branch-and-Bound (B&B) solvers, heavily rely on expert-designed heuristics, w…
Combinatorial OptimizationCPUGPUCADO: 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 Learning