CADO: Cost-Aware Diffusion Models for Combinatorial Optimization via RL Fine-tuning

Authors: Deunsol Yoon, Hyungseok Song, Kanghoon Lee, Woohyung Lim
Primary area: optimization
Keywords: Combinatorial Optimization, Diffusion Model, RL finetuning

Abstract:
Recent advancements in Machine Learning (ML) have demonstrated significant potential in addressing Combinatorial Optimization (CO) problems through data-driven approaches. Heatmap-based methods, which generate solution heatmaps in a single step and employ an additional decoder to derive solutions for CO tasks, have shown promise due to their scalability for large-scale problems. Traditionally, these complex models are trained using imitation learning with optimal solutions, often leveraging diffusion models. However, our research has identified several limitations inherent in these imitation learning approaches within the context of CO tasks. To overcome these challenges, we propose a 2-phase training framework for diffusion models in CO, incorporating Reinforcement Learning (RL) fine-tuning. Our methodology integrates cost information and the post-process decoder into the training process, thereby enhancing the solver's capacity to generate effective solutions. We conducted extensive experiments on well-studied combinatorial optimization problems, specifically the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS), ranging from small-scale instances to large-scale scenarios. The results demonstrate the significant efficacy of our RL fine-tuning framework, surpassing previous state-of-the-art methods in performance.

Decision: reject
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729527651096

thread_type:
official_review

<thread_object>
creator: reviewer_waxg

<content>
summary:
This paper proposes CADO, a novel Cost-Aware Diffusion solver for combinatorial optimization (CO) tasks that address key limitations in traditional heatmap-based solvers, which typically rely on supervised learning to imitate optimal solutions but neglect cost information and the decoding process. By introducing a reinforcement learning (RL) fine-tuning phase, CADO integrates these elements directly into the training process, improving solution quality and computational efficiency. Applied to CO problems like the Traveling Salesman Problem (TSP) and Maximum Independent Set (MIS), CADO demonstrates superior performance, reducing computational costs by 15-40% and outperforming state-of-the-art solvers across various benchmarks.

strengths:
1. This paper presents an interesting point that lower prediction errors do not always correlate with better solution quality. The introduction of an additional RL fine-tuning process is well-motivated to address the shortcomings of existing SL frameworks.

2. This paper introduces a novel two-phase training framework that combines SL with RL fine-tuning, addressing key limitations of traditional heatmap-based CO solvers.

3. The method design is reasonable, and the experimental results are convincing.

weaknesses:
1. Cost guidance for models through post-training optimization has been explored in previous works, such as gradient search and local search [1,2]. The authors should address the differences between their approach and these methods, and discuss any potential advantages their method offers.

2. The methodology design appears somewhat simplistic, as it essentially applies RL on top of diffusion models. Yet, the strength of the paper, which includes motivation, discussion, and empirical results, helps to offset this limitation.

[1] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. NeurIPS 2023.

[2] DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. NeurIPS 2022.

questions:
1. What is the ratio of the training cost for RL fine-tuning compared to the training of the diffusion model?

2. Can the proposed method be combined with techniques such as gradient search [1] and local search [2], or were the empirical results already based on additional techniques during inference?

3. The paper uses the LoRA fine-tuning method. How would the results compare if full fine-tuning was used? What about the computational cost? And how do the results differ when using other fine-tuning methods?

4. Can this method be adapted to other supervised learning based models?

[1] T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. NeurIPS 2023.

[2] DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. NeurIPS 2022.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730399619340

thread_type:
official_review

<thread_object>
creator: reviewer_qgrc

<content>
summary:
This paper introduces RL finetuning to diffusion model-based combinatorial optimization solvers. The methodology seems to be built based on DIFUSCO and T2T, whereby a pretrained DIFUSCO is taken and fine-tuned with RL; and the decoding strategy in T2T is also considered. The main motivation and expected improvement is a CO solver should not only focus on mimicking the supervision signal but also consider the objective function to be minimized. Experiments on TSP and MIS show a little bit of marginal but solid improvements over state-of-the-arts.

strengths:
* I found it interesting to involve objective function minimization in the training process. Introducing RL in training diffusion models for CO is a novel idea. 
* The improvement over baselines such as T2T and DIFUSCO is solid among the benchmarks considered in this paper.

weaknesses:
* The presentation does not discuss important peer methods properly, especially T2T. This paper is motivated by the fact that DIFUSCO does not consider the objective function and claims its contribution of involving the objective function by reinforcement learning. However, T2T has achieved consistent improvement over DIFUSCO by denoising with the guidance of the objective function (as one can tell from Tables 1,2,3), which the authors fully overlook. I understand the fact that this paper uses a different methodology (reinforcement learning), but T2T should be the most important peer method and the authors should not simply overlook that. Simply mentioning the following in related work is not enough
> (T2T and Sanokowski et al. (2024)) are similar to our work in that they utilized cost information, but those methods require a differentiable cost function
* Given the fact that 1) T2T is under a quite similar motivation, 2) T2T seems very competitive, the experimental improvement over T2T is less significant than the improvement over DIFUSCO, 3) the guided denoising strategy in T2T seems to be used in CADO (this paper)
> L304: We also enhance our method with an optional local search technique inspired by Chen & Tian (2019) and Li et al. (2023) called local rewriting. This involves strategically reintroducing noise followed by a secondary denoising process, allowing us to explore the solution space beyond initial denoising results

    I believe there needs more discussions and ablation studies on the introduced RL methodology: when comparing RL-finetuning (this paper) solely with guided denoising (T2T), which contributes more to the objective score? What is the understanding of faster inference on TSP but slower on MIS?
* Another important point this paper failed to address is its technical contribution: introducing RL to optimize the objective score is straightforward (there are tons of RL for CO related work on this), and fusing RL with diffusion is performed by following Black et al. (2024). What is the technical challenge resolved for the combination of RL, diffusion, and CO?

Typo/misc
* "Figure 5" is a table
* Citation for T2T in the upper half of Table 1 is wrong.

questions:
I like the general idea of introducing RL to DIFUSCO and the solid improvement on TSP (better objective score and inference time) and improvement of objective score on MIS (slower inference, though). Before being fully convinced to suggest an acceptance for this paper, I would love to see more discussions on related work (especially T2T, which is missing in the current manuscript), and more insights among different ways of integrating the objective function into CO-solving.

I would like to suggest the following improvements in future versions & in the rebuttal:
* A dedicated subsection comparing CADO with T2T, focusing on these different approaches to incorporating cost information and their relative performance across various problem sizes and types.
* An ablation study that isolates the effects of RL fine-tuning and guided denoising. Additionally, A detailed analysis of the performance differences between TSP and MIS tasks will be nice, particularly focusing on the trade-offs between solution quality and inference time.
* A subsection to explicitly outline the novel technical challenges they encountered in combining RL, diffusion models, and CO. It will be nice to detail how your approach differs from simply applying existing techniques, and to highlight any innovations in your methodology that address CO-specific challenges.

One more technical question:
* This method is faster than T2T and DIFUSCO in Table 2. What is the methodology that made it possible? Why does it get slower than T2T and DIFUSCO in Table 3?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730441654854

thread_type:
official_review

<thread_object>
creator: reviewer_wkrp

<content>
summary:
In this paper, a cost-aware diffusion solver CADO for combinatorial optimization is proposed, and a fine-tuning framework based on reinforcement learning is proposed for diffusion models in combinatorial optimization. CADO consists of two phases: in the first phase, the diffusion model is trained using a given data set, and in the second phase, the pre-trained diffusion model is fine-tuned using reinforcement learning. Finally, it is applied to the traveling salesman and the maximal independent set problem.

strengths:
1.The experiments are relatively full and complete, comparing multiple methods, and doing a wealth of experiments on different datasets for different problems.
2.Good results were obtained on different datasets.
3.To the best of our knowledge, current techniques using diffusion models as well as RL fine-tuning are not common in combinatorial optimization. This paper  provides a detailed code open source for the implementation of the algorithm, which provides a baseline for subsequent similar studies.

weaknesses:
1.The innovation of the method is relatively low. The method of training and fine-tuning is very simple, which is slightly lacking as the innovation point of this paper. We do not see the authors' approach as a significant change from existing algorithms based on reinforcement learning fine-tuning.
2.The motivation also lists some basic problems in the field of combination optimization. It is not seen that these problems are essentially solved, especially (3.2) and (3.3). Alternatively, the authors do not do a good job of explaining why their approach is necessary to solve these difficult problems. In addition, (3.1) has always been a difficult problem faced by the traveling salesman problem, and there is no obvious groundbreaking. 
3.Overall, after reading the entire article I'm still not sure why the algorithm in the article works. Why they achieved better results compared to other algorithms and why this framework is necessary for combinatorial optimization.

questions:
We will consider revising the evaluation based on the answers to the following questions.
1.Please highlight the core contribution points of the article. The method of supervised learning and fine-tuning is more like a trick than sufficient to support the innovation of the article.
2.Specific method support for motivation. Taking feasible punishment and optimization goal as reinforcement learning reward is a very simple idea in the field of combinatorial optimization. Can this paper give more detailed and specific support for motivation.
3.We would like the authors to better explain why the framework in this paper is useful for the hard cases in combinatorial optimization. And what necessary adjustments the authors have made to the original reinforcement learning approach to ensure its applicability to combinatorial optimization problems. We recognize the validity of the experimental results in the article. But we also believe that a clear statement of the principles that make the algorithm effective is also necessary, especially for problems such as combinatorial optimization.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730608324021

thread_type:
official_review

<thread_object>
creator: reviewer_k7qd

<content>
summary:
This paper proposes a new Cost-Aware Diffusion solver for combinatorial Optimization (CADO) method via RL finetuning. The existing approaches simply imitate the shape of the solution without considering the cost information. In addition, they do not account for the decoding process in the overall network. Lastly, they heavily rely on high-quality training datasets, which are expensive to collect. The proposed method trains a diffusion model with two phases: 1) SL and 2) RL fine-tuning. The proposed method incorporates the cost information and the decoder, which enhance the overall performance with significant efficacy.

strengths:
- The existing three problems and motivations are well described.
- Experiments from small-scale to large-scale problems demonstrate the effectiveness of the proposed method.

weaknesses:
- Figure 1 shows the cost compared to the loss. However, the value difference is really small, which is not impressive. 
- In two-phase training, the first phase is the same as DIFUSCO, and the second phase is just adoption of the existing decoder and RL algorithm. Overall, the method is really simple, and lacks a strong sense of novelty.
- The paper claims that the decoded solution may differ significantly, leading to degraded performance of the solver. Are there any example figures or quantitative results? From the main experimental tables, the performance quality is not significantly degraded, as the paper described.
- From the tables, the performance gap is minimal, making the results less impressive. In addition, it is uncertain whether the cost is significantly lower compared to other methods. In a certain dataset, the proposed method rather underperformed, showing inconsistent results.
- From table 4, it is unclear how sensitive the method is to dataset quality compared to existing algorithms. Moreover, this low-quality dataset setting does not look like a realistic setting.

questions:
- Is the cost really problem? This task (CO) does not require a real-time solution, which means the cost gap between the proposed method and existing methods is not a significant problem.
- The proposed method trains the network with one more stage compared to the existing method. Is it a fair comparison? I wonder why the proposed method requires less time consumption compared to DIFUSCO. Moreover, as the experimental result shows, when DIFUSCO trains one more stage with the same SL, the performance is enhanced. It means the proposed method needs to be compared with other algorithms that run the same number of stages or iterations.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732369455955

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
[Common Response]

comment:
We sincerely thank all reviewers for their thorough examination of our manuscript and their constructive feedback. We particularly appreciate the shared suggestion to strengthen the presentation of our contributions and better articulate the theoretical foundations underlying our algorithm's strong performance. To address this valuable feedback, we have prepared a comprehensive overview of our paper's contributions, which has been incorporated into the revised manuscript. We have attached a detailed list of our revisions below, with changes highlighted in the revised manuscript.

Our paper makes the following key contributions:

**Novel Framework Addressing Limitations in SL-based Heatmap Solvers.**

Our analysis reveals three fundamental issues in existing supervised learning (SL) based heatmap solvers that have been insufficiently addressed in prior works, where the primary focus has been on solution imitation:

- Ignorance of Cost in the Training Process
- Ignorance of Decoders in the Training Process
- Dependency on High-Quality Training Datasets

To address these issues, we propose what is, to our knowledge, the first reinforcement learning (RL) fine-tuning framework for CO that enables SL-based heatmap solvers to consider both decoder behavior and solution costs during training.

**Practical Algorithm Design for Large-scale Heatmap Solvers**.

Despite RL's natural fit for combinatorial optimization through direct cost minimization, scaling it to complex CO problems remains challenging. While RL has succeeded in autoregressive settings with well-defined MDPs, RL-based heatmap solvers like DIMES [1] underperform compared to SL-based methods. Alternative methods incorporating cost information during inference (e.g., MCTS, cost-guided search in T2T [2]) heavily depend on base model quality. 

To bridge this performance gap and enable effective direct RL training of heatmap solvers, we carefully design our algorithm to overcome issues of previous works: 

- A two-stage learning approach that combines SL pretraining and RL fine-tuning, achieving both training stability and performance gains
- A diffusion-based framework that excels as an SL-based heatmap solver while naturally providing a well-defined multi-step MDP through its denoising process, enabling effective RL application
- Novel training stability techniques, including Low Rank Adaptation and selective parameter freezing, to enhance RL fine-tuning reliability

**Comprehensive Empirical Validation**.

Through rigorous experimental analysis newly added in this revision, we systematically demonstrate our motivation, the three limitations of existing SL-based solvers, with quantitative evidence. Our experimental results validate that our proposed algorithms effectively address these limitations. 

Our method consistently achieves superior performance compared to state-of-the-art Neural CO solvers across diverse CO benchmarks, including recent cost-aware approaches such as T2T and DIMES. This comprehensive empirical evaluation substantiates the effectiveness of our technical contributions.

**Conclusion**.

While our framework is built upon simple components, each element is meticulously designed to address critical limitations unique to combinatorial optimization. Our method demonstrates robust state-of-the-art performance across diverse CO benchmarks while maintaining consistent hyperparameters, highlighting its strong generalizability. This combination of architectural simplicity and superior empirical results not only validates our design choices but also suggests promising directions for adaptation to broader CO domains. We believe our contributions provide valuable insights for advancing research in heatmap-based CO solvers.

[1] Qiu, Ruizhong, Zhiqing Sun, and Yiming Yang. "Dimes: A differentiable meta solver for combinatorial optimization problems." *Advances in Neural Information Processing Systems* 35 (2022): 25531-25546.

[2] Li, Yang, et al. "From distribution learning in training to gradient search in testing for combinatorial optimization." *Advances in Neural Information Processing Systems* 36 (2024).

**Paper modification.**

The changes made to the paper are highlighted in blue text.

[modified] Clarified the contribution points at the end of the Introduction.

[modified] Moved the experiment in the Introduction (Figure 1) to the experiments section (Figure 3) for better alignment with the paper's message.

[Added] Briefly explained how the issues raised in Section 4.1 can be addressed using the proposed method.

[modified] Revised the explanation at the end of Section 4.2 to avoid misunderstanding about not using gradient-based guidance.

[Added] Provided a detailed explanation of the differences between T2T and the proposed work in Section 4.2 and Appendix F.

[modified] Moved transfer learning and TSPLIB experiments to the appendix due to space limitations.

[Added] Appendix C.2: Experiments with various fine-tuning methods.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper titled "CADO: Cost-Aware Diffusion Models for Combinatorial Optimization via RL Fine-tuning" introduces CADO, a novel framework that integrates Reinforcement Learning (RL) fine-tuning with diffusion models to address Combinatorial Optimization (CO) problems such as the Traveling Salesman Problem (TSP) and Maximal Independent Set (MIS). The authors propose a two-phase training approach where a diffusion model is first trained using supervised learning (SL) and subsequently fine-tuned with RL to incorporate cost-awareness and improve solution quality. Empirical evaluations demonstrate that CADO achieves superior performance compared to state-of-the-art methods like DIFUSCO and T2T, showcasing reductions in computational costs and enhancements in solution accuracy across various benchmarks.

Despite its promising results, the paper exhibits several critical weaknesses that undermine its suitability for acceptance. The methodological innovations are perceived as incremental, primarily extending existing RL and diffusion model techniques without introducing substantial novel contributions. Comparisons with closely related methods, particularly T2T, are insufficiently addressed, raising concerns about the relative significance of CADO’s improvements. Additionally, the experimental evaluations, while comprehensive, reveal minimal performance gaps and inconsistent results across different datasets, which question the robustness and generalizability of the proposed approach. The reliance on multiple hyperparameters and the lack of clarity in explaining key design choices further obscure the paper’s contributions, making it difficult to assess the true impact and scalability of CADO in diverse CO scenarios.