DDRL: A DIFFUSION-DRIVEN REINFORCEMENT LEARNING APPROACH FOR ENHANCED TSP SOLUTIONS

We sincerely thank you for your detailed review and thoughtful feedback. We appreciate the opportunity to address your concerns regarding the applicability, experimental setup, computational costs, and generalization of DDRL.

1. Applicability of DDRL to Other Combinatorial Optimization Problems

   a) Effectiveness of Images in Representing Graph-Based Problems

   DDRL is fundamentally designed to solve problems that can be defined with a graph structure, such as the Traveling Salesman Problem (TSP). Furthermore, as demonstrated in this paper, DDRL extends beyond basic graph-based concepts to effectively handle various constraint conditions, achieving high performance even in these more complex scenarios. By leveraging diffusion models to incorporate visual features alongside graph structures, DDRL demonstrates the capability to address problems with intricate definitions and constraints more effectively than methods relying solely on graph representations. This flexibility indicates that DDRL is not strictly limited to specific tasks but possesses the adaptability to be applied to a broader range of combinatorial optimization problems.

   b) Inference Speed with Image Representations

   The use of diffusion models inherently involves repeated denoising processes, which can result in noticeable computational costs. However, using image representations provides a significant advantage: the resolution of the image can remain fixed regardless of the number of cities, as long as the resolution allows for clear discrimination. In our approach, the pre-trained diffusion model (prior knowledge) was trained on instances with 50 cities, yet it demonstrated strong performance across instances with city counts ranging from 20 to 200.

   Only graph-based methods have the drawback of computational costs increasing proportionally with the number of cities. In contrast, image-based approaches offer greater flexibility regarding the growth in the number of cities. Moreover, the diffusion step (trajectory length) in DDRL is fixed at 50, as the purpose of the image-based process is not to generate high-quality images but to provide rough guidance for city connections. This design enables DDRL to utilize image-based processes effectively, demonstrating that even with limited resources, it can address relatively large-scale problems. Thus, the use of images in DDRL proves to be a practical and resource-efficient choice.

   c) Impact of Image Resolution

   In DDRL, the image resolution was fixed at 64x64 for all experiments, which was sufficient to differentiate up to 200 cities. The image-level process provides rough connection guidance using prior knowledge (pre-trained diffusion model) and explicitly operates as part of the framework. Simultaneously, the RL framework implicitly conducts detailed optimization at the graph level through the learnable latent vector, which evolves dynamically during the inference process.

   This integrated dual approach allows DDRL to address a wide range of TSP instances, from N=20 to N=200, as well as various constraint conditions. The results demonstrate that the rough guidance at the image level, combined with task-specific optimization at the graph level, effectively generalizes to diverse problem settings while maintaining strong performance. The balance between these processes highlights DDRL’s adaptability and robustness.

2. Use of Outdated Baselines

   To address the concern regarding the use of outdated baselines, we conducted additional experiments using DIFUSCO, which has demonstrated strong performance in recent works. Evaluations were performed on TSP-50 and TSP-100 using DIFUSCO’s publicly available weights, with the same dataset used in DDRL experiments (each comprising 1280 problems). For TSP-50, DIFUSCO achieved 5.69, while DDRL, after extending epochs and increasing initial samples, also recorded 5.69. Similarly, for TSP-100, both methods achieved 7.78. These additional experiments demonstrate that DDRL matches the performance of DIFUSCO, and as DDRL is based on RL optimization, further refinement could potentially surpass DIFUSCO’s performance. We will provide updated results as additional experiments are conducted.

3. Computational Costs and Scalability

   a) Inference time

   In our experiments, DDRL demonstrated competitive inference times. For a single TSP instance, the inference time was measured as follows:

   • TSP-50: 14.47 seconds
   • TSP-100: 72.77 seconds

   b) Scalability to Larger TSP Instances

   While DDRL focuses on instances up to 200 nodes, the approach is not inherently limited to this range. The RL framework’s flexibility allows it to adapt to larger-scale problems, provided computational resources for the RL optimization are available. For problems exceeding the current scope, future work could explore adaptive resolutions or hybrid representations to enhance scalability further.

There is no rebuttal. I would like to keep my score.

We sincerely thank you for your thoughtful and detailed feedback. Below, we address each of your comments and questions to provide clarification and additional context.

1. Problem Size

   Recent research has made significant progress in addressing large-scale TSP instances. However, our work focuses on robustness and practical constraint-handling rather than scaling to extremely large problem sizes.

   In our experiments, the prior knowledge (pre-trained diffusion model) was trained on instances with N equals 50, yet it demonstrated effectiveness across a range of N values from 20 to 200 without requiring changes in image resolution. This adaptability suggests that DDRL could potentially handle larger city counts effectively, provided that resolution adjustments are not needed.

   Furthermore, DDRL consistently achieved strong performance on constrained TSP instances up to N equals 200, including real-world-inspired scenarios involving obstacle, path, and cluster constraints. These results highlight DDRL's robustness and its practical applicability in solving diverse and complex TSP problems.

2. Baseline Comparisons

   To address the concern regarding baseline comparisons, we conducted additional experiments using DIFUSCO, a method known for its strong performance in solving TSP. Evaluations were performed on TSP-50 and TSP-100 using DIFUSCO's publicly available weights, with the same dataset used in DDRL experiments (each comprising 1280 problems). For TSP-50, DIFUSCO achieved 5.69, while DDRL, after extending epochs and initial samples, also recorded 5.69. Similarly, for TSP-100, both methods achieved 7.78. These additional experiments demonstrate that DDRL matches DIFUSCO’s performance and, given DDRL's foundation in RL optimization, we anticipate that further refinements could enable DDRL to surpass DIFUSCO’s performance. We will provide updated results as further experiments are conducted.

3. Response to Questions

   3.1 Is the trained model invariant to problem size?

   Yes, DDRL exhibits size invariance within the evaluated range (N = 20 to 200). The pre-trained diffusion model acts as a rough guide, while the RL framework performs task-specific optimization. This separation ensures that the model adapts to varying problem sizes during inference.

   3.2 Could the proposed method guarantee satisfaction of the constraints? How?

   DDRL is well-suited for handling complex constraints for several reasons:

   • Visual Feature Utilization: Constraints such as obstacle (box-shaped areas), path (pre-determined lines), and cluster (differently colored groups) constraints are visually intuitive and are naturally represented at the image level. By leveraging image-based representations, DDRL extracts meaningful visual features that graph-only approaches might miss.
   • Subproblem Decomposition: The multi-step diffusion denoising process allows DDRL to iteratively refine solutions, breaking down challenging problems into manageable subproblems. This flexibility enables DDRL to respond effectively to complex constraints.
   • Guidance and Refinement: Prior knowledge (pre-trained diffusion model) and the initialization trick provide rough guidance for local connections at the image level, establishing a solid foundation for RL optimization. The RL framework then refines these connections into task-specific solutions. This dual-phase process ensures that DDRL transitions smoothly from an initial approximation to a tailored, optimized solution.Empirical results in the paper demonstrate DDRL’s ability to handle various constraint scenarios effectively, showcasing its adaptability and robustness.

   3.3 Could the proposed method solve constrained problems that are not visually intuitive (e.g., PCTSP and CVRP)?

   DDRL is capable of solving problems that are not visually intuitive, as the RL-based optimization process relies on reward-driven optimization. This ensures that the framework can adapt to tasks by optimizing the adjacency matrix to achieve the desired outcomes based on the defined rewards.

   However, since the diffusion model's denoising process leverages visual features to provide rough guidance, the effectiveness of the diffusion model may be limited if the task lacks any visually discernible features. In such cases, while the RL framework can still perform optimization, the contribution of the diffusion model may be diminished, reducing the overall benefit of DDRL’s hybrid approach.

We hope the provided responses address your concerns and offer clarity on the capabilities, motivations, and contributions of DDRL. Your constructive feedback has been invaluable in refining our work, and we greatly appreciate the opportunity to address these critical points. Thank you for your thoughtful review and for engaging with our research.

We apologize for the delay in providing our response. Due to the extended rebuttal period, we took additional time to finalize and confirm the experimental results before submitting our comments.

Thank you for your response. I still believe that the proposed method may have limited practicality, as many real-world constraints are not visually intuitive and cannot be tackled through problem decomposition. An interesting direction, in my opinion, would be to leverage diffusion models to assist or guide the optimization of neural solvers capable of handling complex constraints, rather than proposing a standalone diffusion-based solver. I would like to maintain my score.

We sincerely thank the reviewers for their valuable feedback and insightful comments on our submission. Below, we provide detailed responses to the points raised, aiming to address all concerns and clarify the contributions and methodology of our work.

1. Innovation of the Proposed Approach

   While integration of diffusion models with reinforcement learning for TSP may seem conceptually straightforward, the actual implementation presents several challenges, which DDRL addresses in innovative ways:

   • Connection Between Image and RL: A simple combination of diffusion models and RL frameworks is not trivial. For instance, if the RL framework relied solely on a diffusion-based approach, it would be unclear how to explicitly detect city-to-city connections on the image. DDRL overcomes this by structuring the framework around the diffusion denoising process, which implicitly optimizes the graph structure while explicitly processing image-level guidance.
   • Integrated Pipeline Design: DDRL’s novelty lies in its unified pipeline where the diffusion model’s denoising process is coupled with a learnable latent vector. This latent vector generates the adjacency matrix (graph structure) while also serving as the foundation for the reward design in the MDP environment (see Section 3.2 of the manuscript).

   The integration of image-level guidance and graph-level optimization not only highlights DDRL’s novelty but also ensures its applicability to both fundamental combinatorial optimization problems and practical scenarios involving diverse constraints.

2. additional experiments

   To address the concern about comparisons with state-of-the-art methods, we conducted additional experiments using DIFUSCO, a model recognized for its strong performance. Evaluations were performed on TSP-50 and TSP-100 using DIFUSCO's publicly available weights and the same dataset as DDRL (each comprising 1280 problems). For TSP-50, DIFUSCO achieved 5.69, while DDRL, after extending epochs and initial samples, also recorded 5.69. Similarly, for TSP-100, both methods achieved 7.78, demonstrating that DDRL matches DIFUSCO’s performance and has the potential for further improvement with additional optimization refinements.

3. Fairness of Comparisons for Constrained TSP

   The constrained TSP datasets are novel tasks introduced in this work. Baseline methods, including DDRL, were evaluated under identical conditions without task-specific adaptations or additional training.

   Constraint conditions were incorporated as rules during inference, and no fine-tuning was performed for DDRL or baseline models. This ensures a fair comparison, as all methods were tested on the same datasets with equal assumptions.

   While we recognize that task-specific adaptations could enhance baseline performance, our approach demonstrates DDRL’s inherent robustness and adaptability without requiring additional training for new constraints.

4. trade-off between image resolution and the number of nodes

   In this paper, the image resolution was set to 64x64, and the prior knowledge (pre-trained diffusion model) was trained with N=50. Experimental results demonstrated DDRL's strong performance across a wide range of city counts, from N=20 to N=200. If N increases significantly (e.g., to 10,000 cities), the image resolution would need to increase to maintain distinguishable representations. However, obtaining prior knowledge is a one-time process during the training of the diffusion model, and this pre-trained model can subsequently be utilized for inference across various city counts. Therefore, the actual computational cost during inference is not expected to increase substantially.

   Moreover, the diffusion steps during inference were fixed at 50, aligning with the RL trajectory framework. Since the purpose is not to generate high-quality images but to provide rough guidance for city connections, the increased cost due to higher resolution remains manageable.

   Structurally, DDRL employs the image-level process primarily for rough guidance, while detailed optimization occurs at the graph-level within the RL component. As such, unless unavoidable scenarios arise (e.g., when the number of cities exceeds the pixel count, necessitating higher resolution), the image resolution is largely a controllable factor, ensuring that the computational demands of DDRL remain feasible.

Thank you for your detailed follow-up comments. We appreciate the opportunity to address your concerns in further detail:

1. Are the DDRL results presented in Tables 2-4 obtained from training on basic TSP or constrained TSP?

The training process was conducted on basic TSP. In DDRL, the only training phase involves the acquisition of prior knowledge through a pre-trained diffusion model, trained on instances of N=50 at a 64x64 pixel resolution. For constrained TSPs (as presented in Tables 2-4), constraints were introduced during the test phase by adding specific rules to the solution process. For instance:

• Obstacle constraint: Connections through the obstacle regions were prohibited.
• Path constraint: Specific connections were enforced.
• Cluster constraint: The degree of nodes within a cluster was restricted to 2.

This rule-based approach during testing ensures the method is adaptable to different constraint types without additional model retraining.

2. Regarding the baselines compared in Tables 2-4, especially the attention-based methods, did the authors incorporate the penalty distance into the construction of the attention score? If not, introducing constraints only during the inference stage would naturally make these methods fail, which hinders the fairness of the comparison to some extent.

Both DDRL and the baselines used the same process for constraint handling: training on basic TSP datasets and evaluating on constrained TSP datasets. This uniform setup ensures a fair comparison.

However, DDRL demonstrates superior performance under constrained conditions compared to other baselines for the following reasons:

• During the training phase, DDRL's goal is to learn prior knowledge (pre-trained diffusion model). This enables image-level learning to guide local connections based on the given city positions.

• During the testing phase, DDRL's goal is to tune the latent vector. The latent vector generates an adjacency matrix, and DDRL optimizes the latent vector to minimize the tour length. In this process, the prior knowledge remains fixed, providing rough guidance for city-to-city connections.

Structurally, even without explicit constraint information during the training phase, DDRL’s ability to learn rough guidance at the image level allows it to achieve high-performance TSP solutions during the testing phase through the RL framework. This structural advantage explains why DDRL outperforms other baselines under constrained TSP scenarios.

3. As the authors pointed out, solving large-scale TSPs requires stronger pretrained models to provide prior knowledge. Obtaining these models often demands significant computational resources and datasets. The fact that DDRL relies on extensive interactions with these pretrained models during training and testing might limit its scalability for handling large-scale constrained TSPs.

While larger image sizes may be required to handle increased scales, DDRL remains efficient for the following reasons:

• Reusability of Prior Knowledge:
  Once trained, the diffusion model (prior knowledge) can be applied across various problem sizes without additional retraining, provided the image resolution is sufficient to represent the scale. For example, the model trained on N=50 has been effectively used for N=100 and N=200.

• Parallel Processing Capability:
  Unlike autoregressive models, which decode solutions sequentially, DDRL’s image-based approach allows for parallel processing of all city positions, reducing the computation time.

• Fixed Diffusion Steps:
  The diffusion steps are fixed at T=50. Since DDRL views the diffusion process through the lens of RL trajectories rather than image generation quality, this lower number of steps still achieves robust performance, reducing computational overhead.

4. The baselines compared by the authors are too few and are primarily earlier approaches. I encourage the authors to include more recent and diverse baselines in future versions.

Thank you for the suggestion. We will reflect this in future work.

Thank you again for your time and detailed comments, which have helped us refine and strengthen our work.

Best regards,
The Authors

We sincerely appreciate your thoughtful feedback and the opportunity to address the points raised in your review. Below, we provide detailed responses to each comment to clarify our contributions and the rationale behind the proposed DDRL methodology.

1. Comparisons with State-of-the-Art Methods

   To address the comparison with recent state-of-the-art methods, we conducted additional experiments using DIFUSCO, known for its strong performance. Evaluations were performed on TSP-50 and TSP-100 using DIFUSCO's publicly available weights, with the same dataset used in DDRL experiments (each comprising 1280 problems). For TSP-50, DIFUSCO achieved 5.69, while DDRL, after extending epochs and initial samples, also recorded 5.69. Similarly, for TSP-100, both methods achieved 7.78. These additional experiments confirm that DDRL matches DIFUSCO’s performance and, being based on RL optimization, has the potential to further surpass DIFUSCO with additional refinement. We will provide updated results as further experiments are conducted.

2. Empirical Evidence Supporting Image-Based Diffusion Models

   It is important to clarify that DDRL is better described as a hybrid image-graph approach rather than a purely image-based method.

   In DDRL, the pre-trained diffusion model (leveraged as prior knowledge) and the initialization trick provide a rough guide for local connections at the image level. These components serve as the image-based contribution, capturing visually intuitive structures like obstacles, paths, and clusters. However, the task-specific optimization is carried out through the RL framework, which operates at a graph level to refine these initial connections into detailed adjacency matrices that optimize the given problem. This hybrid nature allows DDRL to combine the strengths of image and graph representations effectively.

   By integrating image guidance for local connectivity with RL-driven graph optimization, DDRL achieves robust performance under diverse and visually complex constraint scenarios. This combination enables DDRL to handle visually intuitive constraints that traditional graph-only methods struggle with, as shown in our experimental results.

3. Motivation for DDRL's Methodology

   While discrete diffusion models show strong results for basic TSP tasks, they face challenges in adapting to diverse and constrained problems due to their reliance on supervised learning. DDRL addresses this limitation by combining image-level guidance with graph-level RL optimization.

   The image-level diffusion process provides rough global guidance for city connections, while the RL framework refines these into detailed adjacency matrices tailored to task-specific rewards. This integrated pipeline ensures both scalability and adaptability, allowing DDRL to handle standard TSPs and complex constrained problems, such as obstacles, paths, and clusters.

   Our experimental results show that DDRL outperforms discrete diffusion models in constrained scenarios, demonstrating its strength in addressing practical combinatorial optimization challenges. This flexibility and adaptability underline the motivation and novelty of DDRL, as it bridges the gap between diffusion models and RL for robust optimization.

4. Fairness of Comparisons in Constrained TSP Scenarios

   To address this, it is important to note that the obstacle, path, and cluster constraints represent entirely new datasets, for which no existing methods, including DDRL, have pre-trained models specifically designed.

   In such cases, the constrained scenarios were applied uniformly across all methods, including baseline models and DDRL, without additional training. Constraint conditions were incorporated as rules directly into the inference process for comparison purposes.

   Given that none of the tested methods, including DDRL, were specifically designed or pre-trained for these new tasks, and considering that all evaluations were conducted under the same conditions, we believe the comparison is reasonably fair. This setup ensures that no particular methodology has an inherent advantage or task-specific familiarity, providing a balanced evaluation framework for assessing performance in these novel constrained settings.

Thank you again for your valuable insights and constructive criticism. Your comments have provided us with an opportunity to further strengthen our work and ensure clarity in presenting the contributions of DDRL. We hope our responses adequately address your concerns, and we remain open to further feedback and discussion to enhance the quality of our submission.

Thank you for your insightful questions. Below, we provide detailed responses to each point raised.

1. Doesn't DDRL have a problem that it can generate completely wrong solutions for test inputs that have different distributions from the training data distribution?

   First, in DDRL, the training process occurs only once to obtain prior knowledge (pre-trained diffusion model). The prior knowledge is trained using 64x64 resolution image data from TSP-50 instances and is designed to guide local city connections at the image level. During test time, the RL framework optimizes the policy in a task-specific manner, generating an optimal adjacency matrix tailored to each test input.

   The diffusion denoising process is treated as a one-step action in the RL framework, ensuring that the policy learns to optimize solutions for specific test inputs, independent of the training data distribution. In other words, DDRL performs optimization tailored to each newly defined TSP problem, so differences between the training and test distributions do not directly impact problem-solving.

   Experimental results confirm that DDRL effectively solves TSP instances across diverse test inputs and a wide range of city counts (20–200), demonstrating its robustness to distributional shifts.

2. Doesn't the diffusion step also require high computation cost?

   While increasing the number of diffusion steps can improve quality in traditional generative models, it also raises computational costs. However, in DDRL, the diffusion steps are not used for generating high-quality images but for guiding the adjacency matrix formation at the image level. The diffusion steps correspond to the trajectory length in the multi-step MDP framework and are set to 50 in this work to balance computational efficiency with guidance quality. This approach ensures that DDRL remains computationally efficient while effectively guiding the RL framework to optimize solutions.

3. Why can you say that the proposed method can handle complex constraint conditions well? Is there a logical basis for it?

   DDRL is well-suited for handling complex constraints for several reasons:

   • Visual Feature Utilization: Constraints such as obstacle (box-shaped areas), path (pre-determined lines), and cluster (differently colored groups) constraints are visually intuitive and are naturally represented at the image level. By leveraging image-based representations, DDRL extracts meaningful visual features that graph-only approaches might miss.
   • Subproblem Decomposition: The multi-step diffusion denoising process allows DDRL to iteratively refine solutions, breaking down challenging problems into manageable subproblems. This flexibility enables DDRL to respond effectively to complex constraints.
   • Guidance and Refinement: Prior knowledge (pre-trained diffusion model) and the initialization trick provide rough guidance for local connections at the image level, establishing a solid foundation for RL optimization. The RL framework then refines these connections into task-specific solutions. This dual-phase process ensures that DDRL transitions smoothly from an initial approximation to a tailored, optimized solution. Empirical results in the paper demonstrate DDRL’s ability to handle various constraint scenarios effectively, showcasing its adaptability and robustness.

4. It is expected that RL-based policy learning may not work well for difficult problems with large size and high difficulty. When using RL, it is necessary to provide a logical basis for learning so that the correct and good solution can always be found.

   DDRL addresses the challenges of RL-based policy learning by enhancing convergence stability through prior knowledge and an initialization trick. These components provide a well-structured starting point and guidance, ensuring local connectivity at the image level and directing the RL framework toward promising solution spaces. Such mechanisms contribute significantly to the convergence stability of RL. Experimental results confirm that DDRL consistently outperforms existing methods on large-scale and complex TSP instances, demonstrating its ability to handle difficult problems effectively.

We hope these responses address your concerns and clarify the strengths of the DDRL framework. Thank you for your thoughtful feedback and for allowing us to elaborate on these aspects.