Preference Optimization for Combinatorial Optimization Problems

W2:Inconsistent Y-Axis Scales in Figures

R: We apologize for this oversight. In the revised manuscript, we will update Figures 1 and 4 to have consistent y-axis scales. This will facilitate direct comparison and better illustrate how PO outperforms RL at each epoch.

Q1: Implementation Details of POMO with PO

R: Yes, your understanding is correct. In our implementation of PO with POMO, SAMPLINGSOLUTION() is conducted using POMO's multiple starting points. We do not use the shared baseline from the original POMO method in this setting.

Q2:Additional Training Time Due to Finetuning

R: For TSP, each training epoch takes approximately 9 minutes, while each finetuning epoch with local search takes about 12 minutes. For CVRP, a training epoch takes about 8 minutes, and a finetuning epoch takes around 20 minutes. Since local search is executed on the CPU, it does not introduce additional GPU inference time. The finetuning phase constitutes 5% of the total epochs, adding a manageable overhead to the overall training time.

Q3:Benefit of Local Search Despite Additional Overhead

R: Yes, incorporating local search (LS) during finetuning is beneficial. LS helps alleviate the issue of the neural solver converging to suboptimal policies by introducing higher-quality solutions into the training process. Training for more epochs without LS does not effectively help the model explore better solutions. The additional training time spent on LS is justified by the improved convergence speed and solution quality achieved through finetuning with LS.

Q4:Role of $\alpha$ in Equations (3) and (8)

R: Yes, the $\alpha$ in Equation (8) is the same as the $\alpha$ in Equation (3). It controls the balance between reward maximization and entropy regularization in the reparameterized reward function, linking it to the policy π and ensuring consistency between the equations.

Q5:Setting and Impact of α Values

R: As mentioned in Section 3.3, α controls the strength of policy exploration by weighting the entropy regularization. A larger α encourages more exploration, while a smaller α focuses on exploitation. We used different α values for TSP100 and CVRP100 to account for their differing problem characteristics. The α value does affect learning efficiency; inappropriate values can lead to insufficient exploration or excessive randomness. For other problems, we recommend starting with α values similar to those used in related works and adjusting based on preliminary experiments. We adopt \alpha =1 in FFSP. Adaptive methods for setting α, such as entropy scheduling[4] or automatic tuning[3], can also be employed to find a suitable balance between exploration and exploitation.

References:

[1] Qiu, R., Sun, Z., & Yang, Y. (2022). Dimes: A differentiable meta solver for combinatorial optimization problems. Advances in Neural Information Processing Systems, 35, 25531-25546.
[2] Kwon, Y. D., Kim, J., & Kim, J. (2021). Matrix encoding networks for neural combinatorial optimization. Advances in Neural Information Processing Systems, 34, 5138-5149.
[3] Haarnoja, T., Zhou, A., Abbeel, P., & Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning (pp. 1861-1870). PMLR.
[4] Mnih, V., Badia, A.P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D. & Kavukcuoglu, K.. (2016). Asynchronous Methods for Deep Reinforcement Learning. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:1928-1937.

Once again, we appreciate your positive evaluation and valuable suggestions. We will incorporate the additional experiments and clarifications into the revised manuscript to strengthen our contribution. Please let us know if you have any further questions or suggestions.

We sincerely thank the reviewer for the positive feedback and insightful comments. We address the concerns and questions below.

W1: Limited Experiments on Larger Problem Sizes and Types

In Table 1, experiments were conducted only on TSP100 and CVRP100. The 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 other types of problems beyond routing.

R: To address this concern, we have conducted additional experiments to evaluate PO's effectiveness on larger problem sizes and different types of combinatorial optimization problems. Specifically, we applied PO to the DIMES model on TSP instances with 500, 1,000, and 10,000 nodes. The results, summarized in the table below, show that PO-trained models consistently outperform those trained with REINFORCE across all scales.

Additionally, we tested PO on the Flexible Flow Shop Problem (FFSP) using the MatNet model. As shown below, PO improves performance on FFSP instances with 20, 50, and 100 jobs.

These results demonstrate that PO effectively enhances model performance on larger problem sizes and different COPs beyond routing.

Thank you for providing the results of the large-size TSP experiments and the FFSP experiments. I believe these experiments will help demonstrate the value of this paper. However, I have additional questions regarding the above experimental results:

1. DIMES-MCTS(RL): In the DIMES paper, the length results for TSP500/1000/10000 are 16.87, 23.73, and 74.63 respectively. There is a significant difference between these values and the ones you've provided, and the discrepancy is larger than the difference between DIMES-MCTS(RL) and DIMES-MCTS(PO). Therefore, I think it is difficult to attribute this to experimental error. Could you please explain why the experimental results for DIMES-MCTS(RL) differ from those in the DIMES paper?

2. Combination of AS and MCTS in DIMES: In the case of DIMES, the combination of RL+AS+MCTS yields the best results. However, I noticed that you only conducted experiments applying AS and MCTS individually, not together. Is there a reason why you did not perform experiments applying both AS and MCTS simultaneously?

3. FFSP Experiment Values: Unlike the TSP-DIMES experiments, the experimental values for FFSP are identical to those in the MatNet paper. I would like to know whether you have taken the values directly from the MatNet paper for this experiment.

We sincerely thank you for your thoughtful and constructive feedback. We are pleased that you find our introduction of innovative PO algorithms exciting and recognize the thoroughness of our theoretical foundation. We address your concerns and questions below.

W1: Clarification of Comparison with Multi-Start Strategy of POMO

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.

R: We apologize for any misunderstanding caused by our presentation. To clarify, the multi-start mechanism is an inherent architectural feature of models like POMO and does not conflict with our proposed Preference Optimization (PO) method. PO serves as a novel training framework that replaces the widely used REINFORCE algorithm.

In Table 1, we applied PO to models such as POMO, Sym-NCO, and Pointerformer, all of which incorporate the multi-start mechanism. The results clearly show that PO-trained neural solvers consistently outperform those trained with REINFORCE, demonstrating that PO enhances performance independently of the model architecture. We will ensure this clarification is explicitly stated in the revised manuscript.

W2: Clarification of PO in Later Stages of Training

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.

R: Thank you for highlighting this important aspect. PO enhances both convergence speed and solution quality. In the later stages of training, where REINFORCE suffers from slow convergence due to diminishing reward differences, PO maintains strong learning signals through qualitative preference comparisons. As illustrated in Figure 1a, PO achieves comparable performance to REINFORCE in approximately 60% of the training epochs, demonstrating faster convergence. Additionally, PO-trained models continue to improve in the later stages, achieving better solution quality than REINFORCE, as evidenced by the lower optimality gaps in Table 1. PO operates within the maximum entropy reinforcement learning framework [1][2], promoting exploration and preventing the model from converging to suboptimal policies without introducing additional noise.

Q:Applicability of PO to Other Tasks Where Evaluating Candidate Solutions is Computationally Expensive

R: We appreciate this insightful question. While our experiments focus on routing problems like TSP and CVRP due to their prominence as benchmarks in combinatorial optimization, we agree that PO has the potential to be even more beneficial in tasks where evaluating candidate solutions is computationally expensive and sampling efficiency is critical. To explore its applicability, we have conducted additional experiments applying PO to the Flexible Flow Shop Problem (FFSP) with MatNet[7], which are more representative of real-world applications where evaluating is computationally intensive.

These experiments demonstrate that PO enhances training efficiency and solution quality in these complex tasks, underscoring its broad applicability. In addition, PO has roots in preference-based reinforcement learning (PbRL), which has been successfully applied in scenarios where reward signals are difficult to define or obtain, such as autonomous driving [4], robotic control [5] and LLM alignment [6]. In these real-world tasks, it can be challenging to assign precise numerical scores to solutions, but easier to express preferences between options.

References:

[1] Haarnoja, T., Zhou, A., Abbeel, P., & Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning (pp. 1861-1870). PMLR.
[2] Haarnoja, T., Tang, H., Abbeel, P., & Levine, S. (2017). Reinforcement learning with deep energy-based policies. In International conference on machine learning (pp. 1352-1361). PMLR.    
[3] Haarnoja, T., Zhou, A., Hartikainen, K., Tucker, G., Ha, S., Tan, J., ... & Levine, S. (2018). Soft actor-critic algorithms and applications. arXiv preprint arXiv:1812.05905.
[4] Christiano, P. F., Leike, J., Brown, T., et al. (2017). Deep Reinforcement Learning from Human Preferences. Advances in Neural Information Processing Systems (NeurIPS), 30, 4300–4311.
[5] Sadigh, D., Dragan, A., Sastry, S., & Seshia, S. (2017). Active preference-based learning of reward functions.
[6] Wolf, Yotam, et al. "Fundamental limitations of alignment in large language models." arXiv preprint arXiv:2304.11082 (2023).
[7] Kwon, Yeong-Dae, et al. "Matrix Encoding Networks for Neural Combinatorial Optimization." Advances in Neural Information Processing Systems 34 (2021): 5138-5149.

We appreciate your recognition of the novelty and potential impact of our work. Your feedback has been invaluable in helping us clarify our contributions and improve the manuscript. We will incorporate the suggested clarifications, additional experiments into the revised version. Please let us know if you have any further questions or suggestions.

Q1: Effects of Preference

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?

R: We would like to clarify that Preference Optimization (PO) is proposed as a new optimization framework that replaces the traditional REINFORCE algorithm in RL4CO, not as an additional loss function added to the existing RL objective. PO addresses exploration challenges by mitigating reliance on numerical reward signals, providing a more stable and efficient training process. Our experiments demonstrate that PO consistently improves solution quality and training speed compared to REINFORCE across various models. Regarding optimality guarantees, PO is grounded in the entropy-regularized reinforcement learning framework, aligning with the maximum entropy paradigm (e.g., Soft Actor-Critic [1]). This framework ensures that the optimal policy is preserved, without introducing adverse side effects.

Q2: Obtaining Trajectories for Preference Comparisons Without Effective Local Search

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

R: We apologize for any confusion. The use of local search methods like 2-opt is optional in our framework. In our experiments, all trajectories for preference comparisons are generated by sampling from the parameterized decoder of the end-to-end models. Even without effective local search algorithms, the model can construct preference pairs by comparing the solutions it generates. The 2-opt method was used during the finetuning phase to help the model escape suboptimal policies but is not essential to the PO framework. We will clarify this in the revised manuscript.

Reference:

[1] Haarnoja, T., Zhou, A., Abbeel, P., & Levine, S. (2018). Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning (pp. 1861-1870). PMLR.
[2] Kwon, Yeong-Dae, et al. (2021). "Matrix Encoding Networks for Neural Combinatorial Optimization." Advances in Neural Information Processing Systems 34: 5138-5149.

We hope these responses address your concerns. We appreciate your thoughtful feedback, which has helped us improve our work. Please let us know if you have any further questions.

W: Limited Experiments on Larger Scales and Comparison

The main weakness of this paper is that experiments were limited to TSP-100 and CVRP-100... 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 and DIFUSCO.

R: We appreciate this suggestion and have extended our experiments to larger problem sizes. Specifically, we applied PO to the DIMES model on TSP instances with 500, 1,000, and 10,000 nodes. The results show that PO consistently outperforms REINFORCE:

Regarding DIFUSCO , it follows a supervised learning paradigm using near-optimal solutions, which differs from our RL-based approach that does not rely on expert knowledge. Therefore, a direct comparison may not be appropriate. Additionally, we tested PO on the Flexible Flow Shop Problem (FFSP) using the MatNet [2] model. The results confirm PO's effectiveness across different COPs:

Thank you for your response. I appreciate the effort you have taken to address my concerns, though I still have some doubts regarding certain aspects of the explanation. As is well-known, REINFORCE is the simplest and most basic deep RL algorithm and is not considered strong in terms of stability or sample efficiency. Since REINFORCE has clear limitations as an algorithm, I believe that comparing PO to improved RL algorithms, such as SAC or PPO, would provide a fairer evaluation when comparing RL objectives and PO objectives. Of course, I understand that most RL-based CO algorithms rely on REINFORCE, which makes such comparisons less straightforward. Nonetheless, I remain unconvinced that replacing the RL objective with the PO objective demonstrates a clear advantage, especially when compared to improving the stability and sample efficiency of the RL objective using more advanced algorithms.

Here are my detailed responses to the points raised regarding the significance of PO:

Scalability & Effectiveness: While the PO objective consistently shows performance improvements over the RL (REINFORCE) objective, as mentioned earlier, the improvement is marginal in large-scale tasks such as TSP1000 and TSP10000 using DIME-MCTS, where the gap decreases from 3.65 to 3.65 and 4.24 to 4.15, respectively. Furthermore, when compared to state-of-the-art supervised learning methods, such as DIFUSCO[1] (1.17 for TSP1000, 2.58 for TSP10000), T2T[2] (0.78 for TSP1000), and FastT2T[3] (0.42 for TSP1000), it becomes difficult to argue that the absolute performance of PO is superior.

Efficiency: As previously mentioned, REINFORCE is well-known for being a highly sample-inefficient algorithm in RL. Thus, even though the PO objective converges 1.5× to 3× faster, this claim is less compelling given the inherent inefficiency of REINFORCE. Additionally, it is necessary to demonstrate the efficiency of PO not just on tasks like TSP100, but on larger problems such as TSP10000, to validate its practical value and scalability.

[1] DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization, NeurIPS 2023

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

[3] Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization, NeurIPS 2024

W3: Clarification of integrating local search into the training loop

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))?

R: Thank you for this insightful suggestion, and we apologize for not clarifying the validation set size earlier. Our validation set contains 10,000 instances, and the inference times reported in Table 1 are the total times to process all instances. We conducted additional experiments applying local search (LS) as a post-processing step during inference. The results are:

Applying LS during inference slightly improves solution quality but significantly increases inference time. In contrast, integrating LS into the training loop (POMO Finetuned) achieves better performance without extra inference time. This demonstrates that incorporating LS into training is beneficial, especially in time-sensitive applications.

Q1: Definition of $\hat{r}_{\theta}$ in Eq. (8)

R: We apologize for the lack of clarity. In Eq. (8), $r_{\theta}$ refers to the reparameterized reward function defined in Eq. (3): $\alpha \log \pi_{\theta}(\tau \mid x) + \alpha \log Z(x)$, where $\pi_{\theta}$ is the policy parameterized by $\theta$.

Q2: How PO helps mitigate the inference objective ≠ training objective problem

R: In combinatorial optimization, the inference objective is to find the best solution, so the model should assign higher probabilities to better solutions. Traditional RL methods optimize the expected reward, relying heavily on numerical reward differences (advantages). As the model improves, these differences diminish, weakening the learning signal. PO mitigates this by using preference-based advantages that are invariant to numerical reward scales, providing consistent learning signals even when reward differences are small. This aligns the training objective more closely with the inference goal of selecting the best solutions.

Q3: Could PO be extended to heatmap-based approaches like DIMES?

R: Yes. We applied PO to the DIMES model, which uses RL to train an encoder for generating heatmaps. Our experiments show that training with PO yields better heatmap representations compared to REINFORCE.

Reference:

[1] Kwon, Yeong-Dae, et al. (2021). "Matrix Encoding Networks for Neural Combinatorial Optimization." Advances in Neural Information Processing Systems 34: 5138-5149. 

We hope these responses address your concerns. We appreciate your feedback and are grateful for the opportunity to improve our work. Please let us know if you have any further questions or suggestions.

We sincerely thank you for your valuable feedback and constructive comments. We address your concerns below.

W1: Limited experiments on larger instances

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.

R: To demonstrate the scalability of our method, we conducted additional experiments on larger TSP instances with 500, 1,000, and 10,000 nodes using the DIMES model. The results show that models trained with Preference Optimization (PO) consistently outperform those trained with REINFORCE:

These results confirm that PO enhances performance on large-scale problems, demonstrating its applicability beyond TSP-100.

W2: Limited comparison with baseline models

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.

R: In addition to the end-to-end RL models (AM, POMO, Sym-NCO, Pointerformer), we have applied PO to the DIMES model, as shown in our response to Weakness 1. Furthermore, we applied PO to the MatNet [1] model for the Flexible Flow Shop Problem (FFSP), a scheduling task. The results on validation sets containing 1,000 instances are as follows:

The results demonstrate that PO effectively improves DIMES and MatNet, indicating its adaptability and effectiveness when integrated with recent SOTA methods.