Preference Optimization for Combinatorial Optimization Problems

We sincerely thank you for your thoughtful comments, which help us improve our presentation clarity. Below, we address your concerns regarding terminology and methodology.

---

1. Regarding the Claims of Optimality

We apologize for the confusion in Contribution 1 regarding optimal solutions. This term was used to indicate that our model preserves preference relations among candidate solutions—when solution $\tau_1$ is better than $\tau_2$ (the true relation), our model consistently assigns higher (implicit) reward value to $\tau_1$. This property is approximately ensured by preference modeling and shift-invariance. We will revise this description as consistently emphasizing better solutions with relation preservation property and justify this term in method section in detail.

---

2. Rationale of PO

• Background: Reinforcement Learning for Combinatorial Optimization (RL4CO) In the RL4CO paradigm, a neural policy iteratively samples a batch of feasible solutions and updates itself to favor better solutions according to the objective function (e.g., route length, makespan), naturally establishing the preference relationships. Our work focuses on algorithmic improvements for training RL-based policy to enhance solution quality and learning efficiency in RL4CO, which further improve the current REINFORCE-based algorithms that rely on numerical reward; this is one of the reasons for considering PO for COPs.
• Key Challenge: Diminishing Rewards A critical issue in RL4CO is the diminishing reward signal. As solutions approach near-optimal, the numerical differences between their rewards become extremely small (e.g., 0.001), making it difficult for the policy trained with existing RL algorithms to distinguish better solutions from worse ones. The weakened signals cause premature convergence, preventing the policy from finding better solutions. Hopefully, PO can alleviate such issues due to the stability of preference relation, which is also the reason for choosing PO.
• Introducing Preference Optimization To address this, we convert the batch of numeric rewards into pairwise preferences. Even if the reward difference is small, a preference-based approach gives a categorical label: B > A. This binary label can offer a more stable learning signal than the numerical one. Further, the learning process can be briefly summarized as:

1. Sample a batch of feasible solutions from the current policy.
2. Compare them by the objective function (e.g., cost, makespan) and label the better one as "preferred."
3. Update the policy by increasing the probability of generating solutions that are "preferred (winner)" over others (loser) and back to Step 1.

More details are provided in Algorithm 1 in our manuscript.

• Distinction from RLHF

1. Objective vs. Subjective Preferences: In RLHF, human annotators may disagree or change their minds, creating conflicts. In PO, the grounding metric (e.g., route length) is naturally fixed, ensuring consistent and transitive preference signals.
2. Online vs. Offline: RLHF often uses a fixed dataset of human comparisons. In PO, our policy actively samples solutions, which are then compared by the objective function to produce preference labels
3. Entropy vs. KL Regularization: Our approach stems from an entropy-regularized RL objective, encouraging exploration in large discrete spaces. whereas RLHF typically employs KL-divergence to maintain proximity to a pretrained model.

---

3. Explanation of "Fine-Tuning"

In deep learning, fine-tuning typically means continuing to train an already-trained model with specialized data or new techniques to improve or adapt its performance. In our model, we similarly adopt this term to represent a two-stage training framework. Moreover, note that the stage 2 (fine-tune) is optional, and model with stage 1 already admit significant improvements over SOTA baselines; thus, the performance gain is indeed ensured by PO.

In our context: 1. We first train a policy $\pi_\theta$ using PO. 2. Then, we "fine-tune" that policy by incorporating local search into the training loop.

Local search (LS) is a standard technique in CO that makes small changes to a solution with non-degradation guarantee, which is generally fair to introduce this process into solver. The detailed fine-tune process can be summarized as:

1. Take the policy's output $\tau$.
2. Run local search on $\tau$ to get a slightly improved solution $\mathrm{LS}(\tau)$.
3. Update the policy to favor $\mathrm{LS}(\tau)$ and go back to Step 1.

This way, the policy learns from the local search refinements. This is what we refer to as "fine-tuning": continuing to refining the learned policy under the guidance of LS–based preference pairs.

---

We appreciate the opportunity to clarify our work and will revise our manuscript accordingly. Thank you again for your valuable time and feedback and openly welcome any further discussions.

We sincerely thank you for your affirmation on our work, and are grateful for the insightful review and constructive comments. We provide point-to-point responses as follows.

---

1. Math implications behind the proposed PO algorithm

We appreciate this insightful question on the rationale PO model, which can be justified from following aspects.

Transform numerical signals into ranks. First, consider the REINFORCE algorithm:

$$\nabla_{\theta} J(\theta)= \mathbb{E}\_{x \sim \mathcal{D}, \tau \sim \pi{\theta}(\tau \mid x)} \left[\left(r(x, \tau)-b(x)\right) \nabla_{\theta} \log \pi_{\theta}(\tau \mid x)\right].$$

The policy is trained to increase the probability of solutions better than the baseline (where $r(x, \tau)-b(x) > 0$) and decrease the probability of worse solutions (where $r(x, \tau)-b(x) < 0$). This implies that the policy mathematically acts as a ranking model that ranks solutions by their rewards. Besides, explicitly learning the reward with traditional RL algorithms has two key weaknesses:

1. Sensitive to baseline selection;
2. Sensitive to the numerical scale of reward signals.

Transform ranks into preference relations. Based on the math implication, we naturally connect the essential goal (discriminative ranking) with rank model. Since there are many possible solutions in rank, we adopt the preference model to retrieve the rank. Specifically, as long as the training pairs are sufficient, it is clear that the true ranks can be provably recovered by the pair-wise relations. Moreover, preference relations admit appealing properties, i.e., invariant to both baseline choice and the numerical scale of rewards. Thus, the PO-based model for ranks and numerical signals is generally reasonable from the views of methodology and numerical approximation.

The name 'PO'. Note that PO here only means the methodology; thus, a more accurate description could be 'PO-based modeling for COPs'. We would clarify this point in revision.

---

2. Parameter setting

All parameters in baselines were adopted from their official codes, and we only retrained all models from scratch for comparison.

---

3. Choice of $\alpha$ in PO

We selected $\alpha$ through grid search with several training steps and found that the suitable value is both problem-dependent and model-dependent. This is why different $\alpha$ values are adopted for different problems and models.

---

4. Graph embedding and decoder

We utilize the same graph embedding and decoder as in the original works. We will include a comprehensive summary in the revision.

---

5. Generalization of PO

Methodologically, as PO is a general algorithmic improvement that can be applied to RL-based solvers, it could inherit the advantages of baselines and enhance them. To empirically validate this, we adopt it to the baselines, i.e., ELG[r1], that are specifically designed for generalization. The results on TSPLib and CVRPLib demonstrate this capability:

TSPLib:

CVRPLib-Set-X:

Therefore, these findings verify that PO is also effect in enhancing the generalization ability of RL-based solvers. We will incorporate them into revision.

---

Q1: Yes, the test set differs from the training set. Training data is generated on-the-fly while test data uses different seeds.

---

Q2: Fine-tuning is applied after policy convergence with PO, when standard training would not improve performance. Fine-tuning iterations are additional to non-fine-tuning iterations. We will clarify this in revision.

---

Q3: As PO provides a general algorithmic improvement over REINFORCE variants, integrating it with generalizable RL methods is natural. This includes combining PO with meta-learning like Omni-VRP[r2] or with local policy like ELG[r1].

---

We sincerely thank you for your valuable time and insightful comments. We kindly welcome any further questions.

Reference

[r1] Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy. arXiv:2308.14104.

[r2] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. ICML 2023.

We sincerely thank you for your thorough review and valuable insights. Your constructive feedback has significantly improved our manuscript. We present the detailed responses as follows and hope that could address the concerns.

---

1. Broadening comparison with SOTA solvers on large-scale problems and generalization

We appreciate your suggestion to enhance experimental evaluation. In response, we have included additional comparisons with SOTA solvers LEHD [r1], BQ-NCO [r2], DIFUSCO [r3], NeuroLKH [r4], T2TCO [r5], ELG [r6] on large-scale problems and generalization tasks.

Specifically, recall that our PO approach can serve as algorithmic improvements over baselines, which implies it is applicable to RL-based solvers for large-scale and generalization problems. To validate this claim, we conducted additional experiments with ELG, a neural solver designed for such challenges. Below are the results of optimality gap on TSPLib and CVRPLib with problems scaling up to 1002:

Results on TSPLib:

Results on CVRPLib-Set-X:

Consequently, the results demonstrate that the solver trained with our PO method consistently outperforms the original counterpart, verifying that PO enhances generalizability across diverse problem scales. We will incorporate these findings to main text in revision.

---

2. Pros and Cons of RL and other paradigms

We sincerely appreciate your suggestion. We try to expand our discussion on the Pros and Cons of RL over other paradigms as follows.

Generally, RL-based approaches offer flexible training without requiring expert knowledge or high-quality reference solutions. As demonstrated in Table 2, our PO-based solver achieves better performance on FFSP instances where heuristic solvers struggle. We acknowledge that RL may face challenges such as slower convergence rates and longer training times compared to supervised learning (SL) approaches, while SL also induces the intractable problem of acquiring the supervision, e.g., annotations. Note that RL-based methods are free of these limitations, and our PO-based algorithmic improvement can further improve the RL baselines with significantly better results.

Besides, a promising future research direction lies in hybrid approaches combining RL with heuristic methods like MCTS and 2-Opt, as in DIMES. Our experiment results also preliminary verify this point, i.e., the experiment and analysis of training DIMES with PO (included in the Appendix E.3) demonstrate that PO can further enhance such hybrid methods.

---

We are deeply grateful for your thorough review and insightful feedback. We sincerely hope that these responses address your concerns, and kindly welcome any further discussions.

References

[r1] [Fu Luo et al., 2023]. Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.

[r2] [Drakulic et al., 2023]. BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. NeurIPS 2023.

[r3] [Sun et al., 2023]. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. NeurIPS 2023.

[r4] [Xin et al., 2021]. NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem. NeurIPS 2021.

[r5] [Li et al., 2023]. T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. NeurIPS 2023.

[r6] [Liu et al., 2023]. Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy. arXiv:2308.14104.

We sincerely thank you for your valuable feedback and constructive comments. Your insightful suggestions are invaluable for improving our work. Below, we address your concerns in detail.

---

1. Including comparison with Poppy and COMPASS

Thank you for providing the related references, i.e., COMPASS [r1] and Poppy [r2]. We discuss them from the following aspects, and will incorporate them into revision.

Methodological Comparison. In general, both them and our work focus on RL for COPs, while the major difference is that the provided works focus on the framework design for enhancing the diversity of learned policies, and our proposed PO algorithm concentrates on algorithmic improvements on the quality of policies and efficiency of learning, which can serve as a plug-and-play objective to the baselines with REINFORCE-based objective.

Experimental Validation. To validate our plug-and-play PO objective on these baselines, we try to reproduce the baselines with the official open-source codes and adapted our objective for further algorithmic improvement, i.e., replacing the policy gradient-based training with PO-based training.

Due to computational constraints (each experiment requires approximately 50 hours on a single 80GB-A800 GPU for 1e5 training steps, with complete training requiring over 60 days), we provide the preliminary comparison results of current training records, including the models trained from scratch with original baselines and PO-based improvement:

Results on TSP-100:

Results on CVRP-100:

The results above demonstrate that 1) PO significantly ensures lower optimality gap at the same iteration number; 2) PO ensures much faster convergence speed for the same gap, and higher stability during optimization. Moreover, these results also validate that our proposed algorithmic improvement method is consistently effective in various RL-based baselines.

---

2. Regarding comparison to reward shaping

We fully agree with you about the importance of comparing PO with reward shaping methods, which is just right considered in experiment section. Specifically, the original Pointerformer implementation already incorporated reward normalization techniques: $\nabla_{\theta} J(\theta) \approx \frac{1}{B \times N} \sum_{i=1}^{B} \sum_{j=1}^{N}\left(\frac{R(\tau_i^j)-\mu(\tau_i)}{\sigma(\tau_i)}\right)\nabla_{\theta}\log p_{\theta}\left(\tau_i^j \mid s\right)$. As shown in Table 1 and Figure 2(c) of our manuscript, the results consistently show that PO outperforms its REINFORCE variant with reward shaping. Figure 3(b) also illustrates how PO re-distributes the advantage values.

Besides, from theoretical view, the fundamental difference between PO and reward shaping lies in the fact that PO is derived from an entropy-regularized objective and is invariant to reward shaping since that would not change the preference relationship between solutions, making it more suitable for exploring large discrete spaces, while reward shaping functions more as a technique to stabilize the training of RL policies. In current manuscript, the analysis is already included in Appendix E.2, i.e., the different preference models (e.g., Bradley-Terry, Thurstone, Exponential) which is used to control the advantage values assignment like reward shaping.

---

3. Correction of Equation 3

We sincerely thank you for your careful examination and valuable suggestion. We will revise Equation 3 to the more precise form: $\max_{\pi_{\theta}} E_{x \sim \mathcal{D}, \tau \sim \pi_{\theta}(\tau|x)}\left[ r(x,\tau) + \alpha \mathcal{H}\left(\pi_{\theta}(\tau|x)\right)\right]$.

---

We are deeply grateful for your thoughtful feedbacks, and sincerely hope that these responses address your concerns. We welcome any further discussions or suggesstions.

Reference

[r1] [Grinsztajn et al., 2023] Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization. NeurIPS 2023

[r2] [Chalumeau et al., 2023] COMPASS: Cooperative Multi-Agent Policy Search for Combinatorial Optimization. NeurIPS 2023