DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems

This paper presents a new approach, DISCO, designed to efficiently solve large-scale combinatorial optimization problems using diffusion models. DISCO addresses two primary challenges in current diffusion solvers: sampling from extensive NP-complete solution spaces and the time-intensive denoising processes. By incorporating solution residues, DISCO focuses on meaningful solution domains, maintaining the multi-modal properties of CO problems while reducing computational overhead. The model also employs an analytically solvable denoising process that significantly cuts down inference time. DISCO demonstrates notable performance improvements on tasks such as the TSP and MIS. The method generalizes well to unseen problem scales through a divide-and-conquer approach, sometimes surpassing models trained specifically for those scales.

Summary This paper introduces DISCO, a diffusion-based solver for combinatorial optimization problems, using denoising diffusion probabilistic models (DDPM) with added solution residues to restrict search space. The forward diffusion process maps ground-truth solutions to a mixture of noise and degraded solutions. The authors also propose an accelerated sampling approach with fewer steps based on decoupled diffusion models (DDM). Experimental results on TSP and MIS demonstrate that the proposed method achieves the improved solution quality and a faster sampling.

The paper introduces DISCO, a diffusion-based solver optimized for large-scale combinatorial optimization (CO) problems, such as the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). Unlike traditional diffusion models, DISCO focuses on constraining the solution space to enhance quality and employs an analytically solvable denoising approach, which speeds up the process. Its twofold strategy—guided sampling and efficient denoising—achieves significantly faster inference times while maintaining high solution accuracy. DISCO's multi-modal search approach also allows it to generalize effectively to unseen problem scales.

The paper presents DISCO, a novel algorithm developed to efficiently address large-scale combinatorial optimization (CO) problems. DISCO effectively manages the multi-modal complexity of CO landscapes, enabling swift solution generation and delivering high-quality results with notably fewer computational steps. Tested on extensive benchmarks, including large-scale Traveling Salesman Problems (TSP) and Maximal Independent Set (MIS), DISCO demonstrates state-of-the-art performance in both solution quality and inference speed.

Thank you to the authors for their detailed responses to my concerns. After carefully reviewing the rebuttal and considering the comments from other reviewers, I have decided to maintain my score. While the work is well-executed, the use of conditional guidance, which is central to the proposed method, is already widely adopted in diffusion models for various tasks. As a result, the novelty of the contribution is somewhat limited.

Dear Chairs and Reviewers,

Hope this message finds you well.

As the discussion period concludes, we present a brief summary of our discussion with the reviewers as an overview for reference. First, we sincerely thank all reviewers for their insightful comments and constructive suggestions. We are encouraged by the positive recognition of our work, including:

• Reviewer PM6T: Acknowledged that DISCO significantly reduces inference times while maintaining high solution accuracy. Praised the clarity of the paper and noted that the multi-modal graph search approach generalizes effectively to unseen problem scales.
• Reviewer Xho3: Highlighted DISCO's superior performance in both solution quality and speed, characterizing it as novel, scalable, and versatile. The empirical results further validated the robustness of DISCO.
• Reviewer AWgu: Recognized the innovative use of residue constraints to guide the generation process, regarding it as novel and reasonable. Emphasized DISCO’s efficiency and effectiveness in solving large-scale TSP problems, along with its strong generalization capabilities to unseen scales.
• Reviewer GPzi: Appreciated the clear structure, well-execution, and readability of the paper, pointing out that DISCO achieves improved solutions with faster sampling.

We have carefully read all the comments and responded to them in detail. All raised concerns have been addressed in our revised manuscript, with the corresponding changes colored in red.

We summarize the main concerns of the reviewers with the corresponding response as follows:

• Novelty of Our Method
  • DISCO’s novelty lies in adopting residue to constrain solution space to a more meaningful region and leveraging multi-modal property in graph search to avoid local optima. Our theoretical analysis, superior performance on large-scale TSP and MIS problems, along with step-wise denoising comparison and generalization experiments on degraded solutions $\mathbf{X}_d$ demonstrate the effectiveness and versatility of our method.
  • DISCO‘s advantages on both edge-based TSP and node-based MIS problems, which stand out as two foundations of CO regarding edge and node decision problems, highlight its potential as an efficient and general-purpose solver for the broader CO domain. To our knowledge, DISCO is the first residue-guided diffusion solver specifically designed for large-scale combinatorial optimization (CO) problems.
• Contribution of Multi-modal Graph Search in Avoiding Local Optima
  • We provide experimental results comparing our algorithm with and without the multi-modal graph search module, focusing on both performance (Length↓ and Gap↓) and computational resource usage (GPU memory and GPU hours). Comparisons show that performance improves as sub-heatmap diversity increases, corroborating the critical role of the multi-modal property in avoiding local optima.
  • We further demonstrate DISCO's overlapping mechanism and effective merging method also help avoid local optima. Experiments show that without overlap, the performance significantly decreases.
• Justifications for DISCO's Multi-modal Property Enhancing Solution Quality
  • By varying the number of noise samples used in the diffusion model's sampling process, we demonstrate that increasing noise samples enhances solution diversity. This effectively leverages the model’s multi-modal property, increasing the likelihood of identifying higher-quality solutions.
• Additional Experiments
  • We compare DISCO against DIFUSCO and T2T with MCTS decoding, showing that DISCO outperforms these methods on all tested scales.
  • Further experiments on smaller-scale TSPs and real-world TSPLIB instances reinforce DISCO’s robustness across diverse problem settings.

Based on the discussion with reviews, we also present a brief summary of our paper as follows:

• Observation: Existing diffusion-based CO solvers overlook the inefficient solution sampling from enormous NPC solution space and the slow reverse process of diffusion models, limiting their applicability to large-scale real-world problems.
• Solution: DISCO addresses these issues by introducing residue-constrained denoising to produce high-quality solutions with fewer steps. It also incorporates a multi-modal graph search mechanism to generalize to unseen problem scales without retraining.
• Results: DISCO significantly reduces inference times while maintaining high solution accuracy, as demonstrated in comparisons on large-scale TSP-5000/8000/10000 against mainstream baselines. Furthermore, DISCO’s multi-modal graph search enables effective generalization to unseen problem scales, even surpassing models trained specifically for those scales.
• Highlights: Designed to solve large-scale CO problems, our work has the following highlights:
  • Residue-constrained solution generation: Residue term can effectively constrain the denoising process, contributing to higher solution quality.
  • Multi-modal graph search: The multi-modal property of the diffusion model enables diverse solution generation, enhancing performance during graph search.

Thanks again for your efforts in the reviewing and discussion. We appreciate all the valuable feedback that helped us to improve our submission.

Sincerely

Authors of Submission 6285

(a) Summarize the scientific claims and findings: The paper claims DISCO achieves faster inference times and higher accuracy on large-scale combinatorial optimization problems like TSP and MIS by introducing residue-constrained denoising and a multi-modal graph search, but reviewers have raised concerns about the novelty and significance of these contributions.

(b) What are the strengths of the paper? The paper is well-written and presents a comprehensive evaluation of DISCO on large-scale TSP and MIS problems, demonstrating its efficiency and generalization ability.

(c) What are the weaknesses of the paper? Despite the authors' claims, reviewers find the novelty and significance of the contributions limited, particularly the use of conditional guidance and the multi-modal graph search, which are already adopted in existing diffusion models.

(d) Provide the most important reasons for your decision to reject. While the paper presents a well-executed approach, the limited novelty and marginal improvements over existing methods do not meet the bar for acceptance at this venue, where significant contributions to the field are expected.

Reject