Preference Optimization for Combinatorial Optimization Problems

Authors: Guanquan Lin, Mingjun Pan, You-Wei Luo, Zhien Dai, Bin Zhu, Lijun Sun, Chun Yuan
Primary area: optimization
Keywords: Combinatorial Optimization, Reinforcement Learning, Preference-Based Reinforcement Learning

Abstract:
Reinforcement Learning (RL) has emerged as a powerful tool for neural combinatorial optimization, enabling models to learn heuristics that solve complex problems without requiring optimal solutions. Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast combinatorial action spaces, leading to inefficient learning. In this paper, we propose $Preference 
\ Optimization (PO)$, a novel framework that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling, emphasizing the superiority among generated solutions. Methodologically, by reparameterizing the reward function in terms of policy probabilities and utilizing preference models like Bradley-Terry and Thurstone, we formulate an entropy-regularized optimization objective that aligns the policy directly with preferences while avoiding intractable computations. Furthermore, we integrate heuristic local search techniques into the fine-tuning process to generate high-quality preference pairs, helping the policy escape local optima. Empirical results on standard combinatorial optimization benchmarks, such as the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP) and the Flexible Flow Shop Problem (FFSP), demonstrate that our method outperforms traditional RL algorithms, achieving superior sample efficiency and solution quality. Our work offers a simple yet efficient algorithmic advancement in neural combinatorial optimization.

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

Reviews and discussion:
<thread>
creation date:
1730184028731

thread_type:
official_review

<thread_object>
creator: reviewer_1apy

<content>
summary:
This paper proposes a method for training an artificial neural network model to solve combinatorial optimization problems. The authors identify issues with the REINFORCE-based parameter update method, which has been widely used in various existing Neural Combinatorial Optimization studies, and propose Preference Optimization(PO) as a solution. Furthermore, the authors present a method that integrates the proposed PO method with existing local search techniques for training. They apply the proposed method to AM, POMO, Sym-NCO, and Pointerformer, demonstrating better results in TSP and CVRP compared to traditional REINFORCE-based optimization methods. The authors also report strong performance in generalization experiments.

strengths:
- The authors propose Preference Optimization (PO) as an optimization method for Neural Combinatorial Optimization (NCO) models. They demonstrate, through experiments on TSP100 and CVRP100, that applying the proposed PO to existing studies such as AM, POMO, Sym-NCO, and Pointerformer leads to improved model performance.

- The proposed Preference Optimization method in this paper is particularly noteworthy in that it can be applied to various existing NCO studies to enhance their performance. It is expected to be applicable to a wide range of future NCO research.

- In generalization experiments, the model trained with Preference Optimization also outperformed the model trained with the REINFORCE-based optimization method.

- Through experiments such as Advantage Assignment, Consistency, and Trajectory Entropy, the paper effectively analyzes the superiority of the proposed PO method.

- The paper provides a thorough theoretical derivation process for the proposed Preference Optimization method.

- Overall, this paper is well-written.

weaknesses:
- In the Table 1 experiments, PO was applied to four existing studies, but the experiments were conducted only on a single problem size for two routing problems, TSP and CVRP. The experimental conditions are restricted to routing problems and a problem size of 100. This paper does not provide experimental results to verify the effectiveness of Preference Optimization for larger problem sizes or for other types of problems beyond routing.

- The y-axis scales in Figure 1 and Figure 4 are inconsistent, making it difficult to assess the extent to which PO outperforms RL at each epoch stage, particularly regarding improvements on the diminishing reward signal issue.

questions:
- Considering the case of training POMO (with PO) following Algorithm 1, it seems that SAMPLINGSOLUTION() is performed according to POMO’s multiple starting points, and the shared baseline from POMO (Kwon et al., 2020) is not expected to be used. Please confirm whether this understanding is correct.

- According to Appendix D, it appears that the Finetune step in POMO (Finetune) was performed for 5% of the epochs. Please clarify the additional training time (or resources) incurred due to this finetuning process.

- In the case of Local Search, even when considering the training time/resources required due to Local Search overhead, is it still beneficial to perform LS? Alternatively, if training with the same amount of resources, would it be more advantageous to train for more epochs without LS? What are the authors' views on this?

- In Equation (3), $\alpha$ is a parameter that determines the weight of entropy regularization. What does $\alpha$ represent in Equation (8)? Is it the same as in Equation (3)?

- The $\alpha$ values used for TSP100 and CVRP100 experiments are different. Please explain why there are different and how they were set. Does the $\alpha$ value affect the learning efficiency? If there is a change in learning efficiency, how does it vary with changes in the $\alpha$ value? If applying Policy Optimization to problems other than TSP100 and CVRP100, what would be a good way to set the $\alpha$ value? Is there a general range or any reference information that could be helpful for setting the value?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730561751333

thread_type:
official_review

<thread_object>
creator: reviewer_yqjg

<content>
summary:
The authors introduce a method called Preference Optimization (PO), which adapts a preference learning framework commonly applied in large language model (LLM) alignment to improve policy learning in deep neural networks for combinatorial optimization. They demonstrate its effectiveness through two types of vehicle routing problems: the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP).

PO trains the policy neural network with pairs of solutions. Rather than focusing on the qualitative score difference between solutions, PO guides the network to consistently prefer the better option in each pair. This relative comparison enables PO to enhance learning efficiency by emphasizing the ranking of solutions rather than their specific metrics (conventional approach). The authors highlight that this method is especially advantageous in later training stages, where traditional approaches struggle to provide useful feedback as the quality differences between solutions diminish. By maintaining a strong training signal throughout, PO achieves better overall performance.

Experimental results demonstrate that substituting traditional reinforcement learning algorithms, such as REINFORCE, with PO leads to substantial improvements in the solution quality of neural network solvers. Additionally, the authors propose an integrated approach that combines PO with a local search algorithm, yielding further enhancements in solution quality.

strengths:
The introduction of innovative training algorithms like PO for policy neural networks is exciting and likely to stimulate further research in the field.

The theoretical foundation for policy optimization using PO is thorough and informative.

weaknesses:
The authors hint that the pairwise comparison method does not fully outperform the "multi-start" strategy of POMO, with the optimality gap reported in Table 1 appearing to confirm this. Even if the proposed method does not surpass "multi-start," the novelty and value of the preference learning approach are clear. It would, however, be helpful for the authors to include a complete comparison.

The authors reason that PO should bolster neural network training in the later stages, yet the empirical results appear to indicate otherwise. Specifically, PO seems to accelerate convergence during the early stages rather than providing a late-stage advantage, with limited evidence supporting its efficacy in the later phases. It is possible that pairwise learning introduces additional noise to the policy network compared to learning based on a large number of homogeneous solutions, as seen with the "multi-start" approach. Further investigation is necessary to substantiate the authors' claim that PO offers an advantage in the later stages of training.

questions:
Given that routing problems like TSP and CVRP allow for efficient generation and evaluation of a large number of candidate solutions, are they the most suitable applications for PO? Might PO prove more effective in other (more realistic) tasks where evaluating candidate solutions is more computationally expensive, making sampling efficiency a more critical factor?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730707008985

thread_type:
official_review

<thread_object>
creator: reviewer_4hje

<content>
summary:
This paper proposes a preference-based reinforcement learning method to address combinatorial optimization problems characterized by large action spaces, which are difficult to optimize using only reward signals. Unlike conventional reinforcement learning that aims to maximize expected reward, combinatorial optimization focuses on maximizing the expected maximum reward. This results in an inconsistency between the inference and training objectives, highlighting the need for preference-based optimization. The paper emphasizes the efficiency of optimization through pairwise preference comparisons of solution trajectories generated by local search methods such as 2-opt. Experiments on TSP-100 and CVRP-100 demonstrated that auto-regressive neural solvers based on the AM algorithm (e.g., POMO, Sym-NCO) exhibited smaller performance gaps with the preference optimization objective.

strengths:
An interesting aspect of this study is its approach of combining the strengths of local search methods, such as 2-opt, with RL-based neural solvers through preference-based RL. By integrating pairwise preference comparisons between solution trajectories with RL objectives in combinatorial optimization problems, this method demonstrated advantages. Experimental results on TSP-100 and CVRP-100 showed slight improvements in performance.

weaknesses:
The main weakness of this paper is that experiments were limited to TSP-100 and CVRP-100, making the results insufficient for comprehensive validation. For problems with 100 nodes, many neural solvers already achieve small gaps. Including results for larger-scale problems, such as TSP-1000 or real-world settings like TSPLIB, would have strengthened the findings. Another limitation is the lack of comparison with state-of-the-art methods like DIMES [1] and DIFUSCO [2]. Demonstrating the effectiveness of the preference optimization algorithm at larger scales with significant performance gains is necessary.

[1] Qiu et al., "DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems", NeurIPS 2022

[2] Sun & Yang, "DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization", NeurIPS 2023

questions:
1. The addition of a pairwise preference loss function may alter the original RL objective and potentially compromise the model’s optimality guarantee. Are there any side effects associated with incorporating preference?

2. In CO problems where effective local search algorithms like 2-opt for TSP are not available, how are trajectories for preference comparisons obtained?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730707887952

thread_type:
official_review

<thread_object>
creator: reviewer_trec

<content>
summary:
The paper proposes Preference Optimization (PO) framework for neural combinatorial optimization, transforming quantitative reward signals into qualitative preferences. This approach is designed to address issues in RL for combinatorial optimization, such as diminishing reward signals and inefficient exploration. Furthermore, integrating local search in training loop improves the quality of generated solutions without additional inference time. Experiments on benchmarks like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP) show that PO yields better solution quality and sample efficiency than conventional RL algorithms.

strengths:
1, The paper is well-written, with particularly clear and convincing motivation.

2, The authors successfully adapt Preference Optimization (PO) to combinatorial optimization (CO), not only applying it but also providing a persuasive explanation of why PO is well-suited for CO tasks.

3, The experiments and analyses strongly support the claimed advantages of PO, effectively demonstrating its benefits (better solution quality and sample efficiency).

weaknesses:
1, The experiments are limited to TSP-100 and CVRP-100. Given that recent studies often include tests up to TSP-10000, additional experiments on larger instances would strengthen the findings. Performance limited to TSP-100 seems less impactful.

2, The comparison with baseline models is somewhat limited. Are there no models beyond Pointerformer? It would be valuable to see how PO performs against recent SOTA methods.

3, It’s unclear if integrating local search into the training loop is truly beneficial. Running local search for even 1–2 seconds (which seems trivial compared to inference time) could likely yield significant performance improvements. Could the authors provide results with an additional 1–2 seconds of local search (e.g., POMO (LS))?

questions:
1. How is  r_{\theta}  in Equation (8) defined?

2. Can you explain the last paragraph of Section 3.1 in detail? It’s unclear how using PO helps mitigate the inference objective ≠ training objective problem.

3. Could PO be extended to heatmap-based approaches like DIMES?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732296173780

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Revisions

comment:
Dear Reviewers,

We sincerely appreciate the insightful reviews and constructive suggestions from all of you, which have greatly enhanced the quality of our submission. We are encouraged by the positive comments on our theoretical foundation and the practical effectiveness of our algorithm.

In this revised version, we have carefully addressed all feedback and incorporated the suggested changes into the main body, with additional content provided in the appendix due to page limitations. **The changes are highlighted in blue**, and the major modifications are summarized as follows:

**Summary of Changes:**

- **Additional experiments on different types of COPs**: We have included experiments on the Flexible Flow Shop Problem (FFSP) in Section 4.3 and Table 2.
- **Experiments on larger problem sizes**: Results for TSP instances with 500, 1,000, and 10,000 nodes are now included in Appendix F.2.
- **illustration of the PO framework**: Additional explanations and illustrations are provided in Appendix A..
- **Expanded discussion on convergence speed**: We have added a discussion on how PO accelerates convergence speed in Section 4.1.
- **Improved clarity and terminology**: The clarity of the claims and terms w.r.t _symbols_, _objective mismatch_,  _multi start mechanism_, and the _optional fine-tune phase_ are improved in the main body.

We hope that these revisions address your concerns and enhance the clarity and completeness of our paper.
Thank you again for your valuable feedback.
Please feel free to reach out if you have any further questions or require additional information.

Sincerely,

The Authors
</content>
</thread_object>

</thread>


Metareview: