Preference Optimization for Combinatorial Optimization Problems
Authors: Mingjun Pan
Guanquan Lin
You-Wei Luo
Bin Zhu
Zhien Dai
Lijun Sun
Chun Yuan
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Combinatorial Optimization
Preference-Based Reinforcement Learning
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We theoretically transform numerical rewards into pairwise preference signals and integrate local search during fine-tuning, empirically enabling faster convergence and higher-quality solutions for COPs like TSP, CVRP, and scheduling.

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 expert knowledge. Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast combinatorial action spaces, leading to inefficiency. In this paper, we propose **Preference Optimization**, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling, emphasizing the superiority among sampled solutions. Methodologically, by reparameterizing the reward function in terms of policy and utilizing preference models, we formulate an entropy-regularized RL objective that aligns the policy directly with preferences while avoiding intractable computations. Furthermore, we integrate local search techniques into the fine-tuning rather than post-process to generate high-quality preference pairs, helping the policy escape local optima. Empirical results on various 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 significantly outperforms existing RL algorithms, achieving superior convergence efficiency and solution quality.

Preference Optimization for Combinatorial Optimization Problems
Mingjun Pan 12 Guanquan Lin
You-Wei Luo 45
Bin Zhu 2 Zhien Dai
Lijun Sun Chun Yuan
Abstract
planning, circuit design, scheduling, and bioinformatics (Pa- padimitriou & Steiglitz, 1998; Cook et al., 1994; Korte et al., 2011). These problems require finding an optimal solution from finite but exponentially large set of possibilities and have been extensively studied in the operations research community. While computing the exact solution is impeded by their hP-hard complexity (Garey & Johnson, 1979), effi- ciently obtaining near-optimal solutions is essential from a practical standpoint.
Reinforcement Learning (RL) has emerged as a powerful tool for neural combinatorial opti- mization, enabling models to learn heuristics that solve complex problems without requiring expert knowledge. Despite significant progress, existing RL approaches face challenges such as diminish- ing reward signals and inefficient exploration in vast combinatorial action spaces, leading to inef- ficiency. In this paper, we propose Preference Optimization, novel method that transforms quantitative reward signals into qualitative prefer- ence signals via statistical comparison modeling, emphasizing the superiority among sampled so- lutions. Methodologically, by reparameterizing the reward funetion in terms of policy and utiliz- ing preference models, we formulate an entropy- regularized RL objective that aligns the policy di- rectly with preferences while avoiding intractable computations. Furthermore, we integrate local search techniques into the fine-tuning rather than post-processing to generate high-quality prefer- ence pairs, helping the policy escape local optima. Empirical results on various benchmarks, such as the Traveling Salesman Problem (TSP), the Ca- pacitated Vehicle Routing Problem (CVRP) and the Flexible Flow Shop Problem (FFSP), demon- strate that our method significantly outperforms existing RL algorithms, achieving superior con- vergence efficiency and solution quality.
Deep learning, encompassing supervised learning and rein- forcement learning, has shown great potential in tackling COPs by learning heuristics directly from data (Bengio et al., 2021; Vinyals et al., 2015). However, supervised learning approaches heavily rely on high-quality solutions, and due the NP-hardness of COPs, such collected training datasets may not guarantee optimality, which can lead mod- els to fit suboptimal policies. In contrast, RL has emerged as promising alternative, achieving success in areas involving COPs such as mathematical reasoning (Silver et al., 2018) and chip design (Mirhoseini et al., 2021). (Deep) RL-based solvers leverage neural networks to approximate policies and interactively obtain rewards/feedback from the envi- ronment, allowing models to improve in trial-and-error manner. (Bello et al., 2016; Kool et al., 2019).
Despite its potential, applying RL to COPs presents signifi- cant challenges. Diminishing reward signals: As the policy improves, the magnitude of advantage value decreases sig- nificantly. Since RL rely on these numerical signals to drive learning, the reduction in their scale leads vanishing gradi- ents and slow convergence. Unconstrained action spaces: The vast combinatorial action spaces complicate efficient ex- ploration, rendering traditional exploration techniques like entropy regularization of trajectories computationally infea- sible. Additional inference time: While neural solvers are efficient in inference, they often suffer from finding near- optimal solutions. Many works adopt techniques like local search as post-processing step further improve solutions, but this incurs additional inference costs.
1. Introduction
Combinatorial Optimization Problems (COPs) are funda- mental in numerous practical applications, including route
"Equal contribution 'China Mobile 'Peking University Tsinghua University "Jiaying University "Sun Yat-Sen University
'Central South University
Mingjun Pan <mingjunpan966 wawpraannnnmmmmoooommomommmmmmme com>. Correspondence
To address the issue of diminishing reward signals and in- efficient exploration, we propose transforming quantitative reward signals into qualitative preference signals, focusing on the superiority among generated solutions rather than their absolute reward values. This approach stabilizes the
to: You-Wo Luo <luoyw28@mmall maill..ysu..du.cm Chun Yuan <yuane @ sz. usinsuuuaaccuu.cns
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Preference Optimization for Combinatorial Optimization Problems
learning process and theoretically emphasizes optimality, as preference signals are insensitive the scale of rewards. By deriving our method from entropy-regularrzzd objec- tive, we inherently promote efficient exploration within the vast action space of COPs, overcoming the computational intractability associated with traditional entropy regulariza- tion techniques. Additionally, to mitigate the extra inference time induced by local search, we integrate such techniques into the fine-tuning process rather than using them for post- processing, which enables the policy to learn from improved solutions without incurring additional inference time.
problems (RL4CO) by (Bello et al., 2016; Nazari al., 2018; Kool et al., 2019) has prompted subsequent explo- ration on frameworks and paradigms. We classify the ma- jority of RL4CO research from the following perspectives:
End-to- EEd Neural Solvers. Numerous works have focused on designing end-to-end neural solvers that directly map problem instances to solutions. Techniques exploiting the inherent equivalence and symmetry properties of COPs have been introduced to facilitate near-optimal solutions (Kwon et al., 2020; Kim et al., 2022; Ouyang et al., 2021; Kim et al., 2023). For example, POMO (Kwon et al., 2020) em- ploys multiple diverse starting points to improve training efficiency, while Sym-NCO (Kim et al., 2022) leverages problem symmetries to boost performance. Other studies incorporate entropy regularization the step level encour- age exploration and improve solution diversity (Xin et al., 2021a; Sultana et al., 2020). Further efforts to enhance generalization include diversifying training datasets to han- dle a broader range of problem instances (Bi et al., 2022; Wang et al., 2024; Zhou et al., 2023; Jiang et al., 2024). Al- though most of these works primarily focus on architectural or learning- paraddigg improvements, less efforts has been paid developing novel optimization framework.
Furthermore, preference- based optimization has recently gained prominence through its application in Reinforcement Learning from Human Feedback (RIHF) for large language models (Christiano et al., 2017; Rafailov et al., 2024; Meng et al., 2024). Inspired by these advancements, we intro- duce a novel update scheme that bridges preference-based optimization with COPs, leading to a more effective and con- sistent learning process. In this work, we propose a novel algorithm named Preference Optimization (PO), which can seamlessly substitute conventional policy gradient methods in many contexts. In summary, our contributions are:
1. Preference-based Framework for RL4CO: We present a novel method that transforms quantitative reward signals into qualitative preference signals, en- suring robust learning independent of reward scaling. This addresses the diminishing reward differences com- mon in COPs, stabilizing training and consistently em- phasizing better solutions with relation preservation.
Hybrid Solvers. Another promising direction integrates neural methods with conventional optimization techniques, combining established heuristics such as k-Opt, Ant Colony Optimization, Monte Carlo Tree Search, or Lin- Lin-Kernighan to refine solution quality (d O Costa al., 2020; Wu et al., 2021: Ye et al., 2023; Xin et al.. 2021b). For instance, NeuRewriter (d O Costa et al., 2020) couples deep learning with graph rewriting heuristics, while NeuroLKH (Xin et al., 202 embeds neural methods into the LKH algorithm. In many cases, these heuristics function as post-processing steps to refine near-optimal solutions (Fu et al., 2021; Ma et al., 2021; Ouyang et al., 2021), but the associated ad- ditional inference time can reduce efficiency and may be infeasible for time-critical scenarios.
2. Reparameterized By reparameterizing the reward function in terms of policy and leveraging statistical preference models, we formulate an entropy-regularize objective that aligns the policy directly with preferences. This approach bypass the intractable enumeration of the entire action space, maintaining computational feasibility.
Reguuli-ee Objective:
3. Integration with Local Search:
We demonstrate how our framework naturally incorporates heuristic local search for fine-tuning, rather than relegating it to post- processing. This integration aids trained solvers in escaping local optima and enhances solution quality without introducing additional time at inference.
In this work, we primarily focus end-to-end neural solvers because hybrid methods rely heavily on heuristic- based solution generation, making it difficult to evaluate the algorithmic impact of RL-based approaches. Therefore, considering the end-to-end modeling can provide a practical evaluation of how different algorithms affect performance.
Preference-based Reinforcement Learning. Preference- based reinforcement learning (PbRI.) is another area re- lated to our work, which has been widely studied in of- fline RL settings. PbRL involves approximate the ground truth reward function from preference information rather than relying on explicit reward signals (Wirth et al., 2017). This approach is particularly useful when reward signals are sparse difficult to specify. Recently, works such as (Hejna & Sadigh, 2024; Rafailov et al., 2024; Meng et al.,
Extensive experiments across a diverse range of COPs vali- date the efficiency of our proposed PO framework, which achieves significant acceleration in convergence and supe- rior solution quality compared to existing RL algorithms.
2. Related Work
RL-based Neural Solvers. The pioneering application of Reinforcement Learning for Combinatorial Optimization
2

---

Preference Optimization for Combinatorial Optimization Problems
5.72
Phase 1
A
indicating is preferred than
Lirrin (0)
Len.-5.64
f(a - [Log(To(TZ =)) log(TTo(Tala)
Encoder
Preference Comparison
PO Loss
Len.=5.68
Phase 2
Optional
Decoder
L.7.55.72
Len.55.70
L frantoone (0) fa [og(To((.S(()l=))
Sampling Solutions
log(=a(r(=)))
Original Solutions
Local Search Search
Figure 1: Algorithmic framework of PO for COPs. In the Preference Comparison module, pairwise comparisons are conducted between solutions based on their grounding quality (e.g., trajectory length). The Local Search slightly refines solution to produce improved solution LS(T) which contribute additional preference signals Liinetue during fine-tuning.
2024) have proposed novel paradigms to directly improve the KL-regularized policy without the need for learning an approximate reward function, leading more stable and efficient training. This has led to the development of series of works (Azar et al., 2024; Park et al., 2024; Hong et al.,
signals. In COPs, the state transitions are typically modeled as deterministic. commonly used method is REINFORCE (Sutton & Barto, 2018) and its variants, whose update rule is given by: 2024) in the RLHF phase within language-based models, where preference information is leveraged to align large language models effectively.
VoJ(0) B Banmroro(Hle) ((((1,)) M(x)) Va log [x)
Σ [r(a, 6(z)) Vo logmelr [a)] (I) TES
Our work bridges the gap between these domains by intro- ducing meefrrence-based optimization framework specifi- cally tailored for COPs. By transforming quantitative reward signals into qualitative preferences, we address key chal- lenges in RL4CO, such as diminishing reward differences and exploration inefficiency, while avoiding the need for explicit reward function approximation as in PbRL.
where D is the dataset of problem instances, & E D repre- sents an instance, S₁ is the set of sampled solutions (tra- jectories) for æ, r(x,, T) the reward function derived from distinct COPs and b(x) represents the baseline used to cal- culate the advantage function A A 7) r(ar, r) b(x)), which helps reduce the variance of the gradient estimator.
A critical challenge in REINFORCE based algorithms is their sensitivity to baseline selection. As demonstrated in (Kool et al., 2019), training without an appropriate baseline led to significantly degraded performance COP appli- cations. The policy 7 xx) defines distribution trajectories
3. Methodology
In this section, we first recap Reinforcement Learning for Combinatorial Optimization (RL4CO), and Preference- based Reinforcement Learning (PHRL). Next, we explain how to leverage these techniques to develop a novel frame- work to efficiently train neural solvers that rely solely on rel- ative superiority among generated solutions. Subsequently, investigate the compatibility of our approach with Local Search techniques for solver training, i.e. fine-tuning. The algorithmic framework of our method is illustrated in Fig. 1.
(01, 02,,,a,.... -.. ,ar) given the instance Each trajectory is sequence of actions generated by the policy: TT(T x) I[ To(a; st-1), with being the initial state determined by x. and 8; representing the state at time step t, which depends on the previous state and the taken action (e.g., 8; T(*-11, Here, T(.) represents the state transition function, which deterministic in COPs. The action a, is selected by the policy based state St-1-
3.1. Reinforcement Learning for Combinatorial Optimization Problems
Unlike popular RL environments such as Atari (Belle- mare et al., 2013) and Mujoco (Todorov et al., 2012), which provide stable learning signals, COPs present dis- tinctive challenges. As the policy improves, the magnitude of advantage value diminishes significantly. Specifically,
RL trains an agent to maximize cumulative rewards by inter- acting with an environment and receiving numerical reward
3

---

Preference Optimization for Combinatorial Optimization Problems
(r(2,)) b(x) < e, where is small except for the initial training process. This leads negligible updates to the pol- icy objective (0) in REINFORCE-variants, which heavily relies on the advantage value A(z, r) = r(z, r) - b(x). Consequently, the policy struggles to escape local optima during later training stages.
dency on numerical reward signals and consistently empha- sizes optimality. We hegin our derivation with the entropy- regularized RL introduced by (Haarnoja et al., 2017), which was originally designed to encourage exploration.
A challenge in applying RL to COPs is the exponential growth of the state and action spaces with problem size, making efficient exploration difficult. A common approach to encourage exploration is to include an entropy regulariza- tion term H(TT)) to balance exploitation and exploration:
3.2. Preference-based Reinforcement Learning
Preference-Basee Reinforcement Learning (PbRL) (Wirth et al., 2017) trains an agent using preference labels instead of explicit reward signals obtained through direct interaction with the environment. Concretely, we assume access preference dataset D, = {(T1, 72. y)), where each triplet consists of two trajectories 71, 72 and preference label E {0, 13. A label y = indicates that Ti is preferred over 72 (T1 > T2), while y = O indicates the opposite.
max EXND (Br=no(11)) [r +)] + aHl (Te() x))] (3)
Te
where a controls the strength of the entropy regulariza- tion, and H (sTo() =)) - Σ, To(T xx) log (o | 2:) is the entropy of the policy for instance However, comput- ing the entropy term H(TT)) is intractable in practice due to the exponential number of possible trajectories.
These preferences are assumed to be generated by an un- derlying (latent) reward function f(,,T). Various models, such as Frarl (BT), Thurstone (David, 1963), and Plackett- (PL) (Plackett, 1975), link differences in re- ward values to observed preferences, enabling us to formu- late an objective for learning the reward function.
Following prior works (Ziebart et al., 2008; Haarnoja et al., 2017), it is straightforward to show that the optimal policy to the maximum entropy- based objective in Eq. admits an analytical form:
In paired preference models like BT and Thurstone, a func- tion (-) maps the difference in rewards to a probability of one trajectory being preferred over another:
T (T (z) (T|2)
exp (a (r(1,T)),
(4)
Z(x)
where the partition function Z(x)= E. ( +)) normalizes the policy over all possible trajectories T. The de- tailed derivation is included in the Appendix D.1. Although the solution space of COPs is finite and the reward function r r(a, 7) is accessible, computing the partition function ((x) is still intractable due to the exponential number of possi- ble trajectories. This intractability makes it impractical to utilize the analytical optimal policy directly in practice.
p'( > T2) = f(f(2, - ((I,T2)).
(2)
where the Bradley-Terry model adopts the sigmoid function (xx) (1 + e -- and the Thurstone model uses the CDF (zx) of the normal distribution.
This relationship allows us to learn (x( T) via a binary classification problem: maximizing the likelihood of the observed preferences,
The specific formulation of Eq. 4 implies that the latent reward function f(z,7) can be reparameterized in rela- tion the corresponding policy <( x). analogous to the approach adopted in (Rafailov et al., 2024) for KL- regularized objective and in (Hejna & Sadigh, 2024) within the inverse RL framework. Eq. 4 can thereby be rearranged to express the reward function in terms of its corresponding optimal policy æ for the entropy-regularie
max E ((rrraa)) Iylog > 72)].
Once iss is learned, policy me can be optimized under this learned reward, ensuring Ti > 72 = (T(TT) > na (T2),,
so that preferred trajectories receive higher probabilities under the policy.
objective:
major challenge in PbRL is obtaining reliable preference data. Labels often depend on expert judgment, leading to potential preference conflicts, such as cyclic preferences Ti > T2 > T3, and T3 > 71- These contradictions violate transitivity, making it critical to construct consistent preference labels to ensure stable policy learning.
f(z, T) a log ((T x)) + a log (zz).
(5)
From Eq. 5, the grounding reward function r can be explic- itly expressed by the optimal policy x* of Eq. 3. Then we can relate preferences between trajectories directly to the policy probabilities. Specifically, the preference between two trajectories Ti and 72 can be modeled by projecting the difference in their rewards into paired preference distri- bution. Note that this analytic expression naturally avoids intractable term (xx), since Z(x) is a constant w.r.t the r and cancels out when considering reward differences.
3.3. Derivation of Preference Optimization
The key insight of our method is to transform the quantita- tive reward signals into qualitative preferences. This trans- formation stabilizes learning process by avoiding the depen-
4

---

Preference Optimization for Combinatorial Optimization Problems
Using preference models, by substituting Eq. 5 into Eq. 2, the preference probability between two trajectories is:
where (T,
T' .r)
(r(x,7) > r(a, affo(1,77 7)
(x, 7)), and (o(x,,)) = a log To(T x) + a log ((x) Taking a deeper look at the gradient level, compared to the REINFORCE- based algorithm in Eq. 1, the term about T',, x) g(T', -,,)) serves as a quantity-invarian ad- vantage signal. A key finding is that this reparameterized reward signal ensures that if r(a, TI) > r((r, T2), then the gradient will favor increasing (T( over Ta (T2).
p(T1 > Te x) = f (a [log (T x) - log (1 | x)]), (6)
By leveraging this relationship, we transform the quantita- tive reward into qualitative preferences in terms of policy Iτ Next, we could approximate π with parameterized xy.
Proposition 3.1. Let f(x,7 T) be a reward function consistent with the Bradley-Terry Thurstone, or Plackett-Luce models. For a given reward function f' (x,T). (f T) 80 (2, h(x)) for some function h(x), it holds that both F(x,,)) and Pl T induce the same optimal policy in the context of regulazeee reinforcement learning problem.
Algorithm 1 Preference Optimization for COPs.
Input: problem set DD number of training steps T, fine- tune steps Tir 2 0,batch size B, learning rate 7/. ground truth reward function r. number of local search iteration ILS, initialized policy TT.
Based on Proposition 3. we can conclude that shifting the reward function by any function of the instance z does not affect the optimal policy. This ensures that canceling out (xx) in Eq. 6 still preserves the optimality of the policy my learned, we defer the proof to Appendix D.2.
for step = 1, ,,..., T + TFT do //Sampling N solutions for each instance xi; Ij x D. Vi E {I.....)
T = (T..,7...... T,N s --(().), ViE {I...., (L...,,). B} // Fine-tuming with for Ter steps (Optional)
if step > T then
Comparison Criteria. We adopt the grounding reward function r to generate conflict-free preference labels = 1 ()) IR- + {0, 1}. As the reward function r(z, 7) in COPs can be seen as a physical measure, pairwise comparisons generated in this manner preserve a consistent and transitive partial order of preferences throughout the dataset. More- over, while traditional RL methods may rely on affine trans- formations to scale the reward signal, our approach benefits from the affine invariance of the preference labels. Specifi- cally, the indicator function is invariant under positive affine transformations: (k: rxx, mI) + b > k r(æ;, re) + b) (r(a, m) > r(ar, for any k >> 0 and any real number b. This property implies that our method emphasizes opti- mality independently of the scale and shift of the explicit reward function (e.g., reward shaping), facilitating the learn ing process by focusing on the relative superiority among solutions rather than their absolute reward values.
[7, 42 ....., + t LocalSearch(T, r, Lss), Vi C T UU! , AN)
end if
/Caaccllte conflict-free preference labels via ground- ing reward function r r(x,T)
vr, + (r(z,, T() > ((T,, Vj.k
//A //Approximating the gradient according Eq. 8
R
VeJ(O) BT 2
Σ
Σ
gا ,
V VologTo mi)
0 0 + (0) end for
3.4. Fine- Tine-Tuning with Local Search
Objective. To make the approach practical, we approximate the optimal policy x² with a parameterized policy иe. This approximation allows us reparameterize the latent reward differences using ne, naturally transforming the policy op- timization into a classification problem analogous to the reward function trained in PbRL. Guided by the preference information from the grounding reward function r(ar, T), the optimization objective (0) can be formulated as:
Although neural solvers offer computational efficiency, they often struggle to achieve near-optimal solutions compared to the heuristic solvers. After policy convergence, additional standard training fails to improve the policy's 's performance, which can be observed in both PO and REINFORCE-based algorithms within the RL4CO framework.
Local Search (LS) is commonly employed as a post- processing step to refine solutions generated by combinato- rial solvers, guaranteeing monotonic improvement. Specif- ically, for any solution т, the refined solution LS(r) satis- fies r(z, LS(r)) 2 r(z,,) 7) through localized adjustments. When integrating it into learning, traditional RI algorithms typically depend on numerical reward magnitudes, which may exhibit small variations following LS and thus yield weak gradient signals. In contrast, PO framework relies on qualitative comparisons rather than numerical reward values,
max 0
[1 ((r(,,)) r(s, ra)) logpo(n 72 xx), (7) D. (-1b))
F
while instantiating with BT model (.), maximizing p(T) >
T2 x) = affo(I, TI) - fo(x, 72)) leads to the gradient:
VoJ
ΣΣ Σ
(T,
SA
TED T'ES,
(mr(T', T, x)) V log (T( (|/1)) |x)] (8)
5

---

Preference Optimization for Combinatorial Optimization Problems
Table 1: Experiment results on TSP and CVRP. Gap is evaluated on 10k instances and Times are summation of them.
TSP
CVRP
Solver
Algorithm
N
20
50
.V
100
N 20
N
50
N
100
Gap
Time
Gap
Time
Cap
Time
Gap
Time
Gap
Time
Cap
Time
Heuristie
Concorde LKII3
0.00%
13m
0.00%
21.5m
0.00%
1.2h
0.00%
28s
0.00%
4.3m
0.00%
15.6m
0.09%
0.5h 0.18%
2h
0.55%
4h
HGS
0.00%
0.00%
3h 0.00%
5h
RF
0.28%
0.1s
1.66%
3,40%
2s
4.40%
0.1s
6.02%
7.69%
3s
AM (Kool ct al., 2019)
PO
0.33%
0.1s
1.56%
Is
2.86%
4.60%
0.1s
5.65%
Is 6.82%
3s
Neural NeoralSolvees Solvers
RF
0.00%
6s 0.02%
12s
0.15%
1m
Pointerformer (Jin et al., 2023)
PO
0.00%
6s 0.01%
12s
0.06%
1m
RF
0.01%
Is 0.16%
2s
0.39%
8s
0.72%
1.31%
4s 2.07%
16s
Sym-NCO (Kim et al., 2022)
PO
0.00%
Is 0.08%
0.28%
0.63%
1s
1.20%
4s
1.88%
16s
RF
0.01%
Is 0.04%
15s
0.15%
Im 0.37%
0.94%
5s 1.76%
3.3m
POMO (Kwon et al., 2020)
PO
0.00%
Is 0.02%
15s
0.07%
Im 0.16%
0.68%
5s
1.37%
3.3m
PO+Finetune
0.00%
%
1s
0.00%
15s
0.03%
1m 0.08% %
Is
0.53%
5s
1.19%
3.3m
making it inherently compatible with LS-driven fine-tuning, To harness the benefits of LS while avoiding additional in- ference costs, we integrate LS into the post-training process (i.e. fine-tuning) after the policy has converged through stan- dard RI. training procedures. For each generated solution T, we apply a small number of LS iterations to obtain an im- proved solution LS(T). In practice, (ax, LS(r)) > r(2,7) r) for most cases except in the case that LS fails to improve.
et al., 2011)), treating LS outputs expert demonstrations. Thus, PO can absorb these LS-refined solutions without encountering severe off-policy issues, allowing the policy to imitate these expert-like trajectories effectively.
4. Experiments
In this section, present the main results of our experi- ments, demonstrating the superior performance of the pro- posed Preference Optimization (PO) algorithm for COPs. We aim to answer the following questions: 1. How does PO compare to existing algorithms on standard benchmarks such as the Traveling Salesman Problem (TSP), the Capac- itated Vehicle Routing Problem (CVRP) and the Flexible Flow Shop Problem (FFSP)? 2. How effectively does PO balance exploitation and exploration by considering entropy, in comparison to traditional RL algorithms?
We then form a preference tuple (r, LS(T), v). where y (r(2, LS(T)) > r(z,,)) The optimization objective dur- ing fine-tuning becomes:
max 8
E ZND, (
y log (o(((r)) > r| =
(9)
E I (ex [log (LS(r)) a)) - log me(r 2)))
ZND, (11x)
(11x))
where the LS-refined solutions act as high- prefer- ence references. By incorporating these references directly into training, the solver can internalize local search improve- ments rather than relying on LS as separate, computa- tionally expensive post-processing step. Although each LS iteration introduces some overhead, it remains manageable by limiting the number of LS calls per trajectory. As sum- marized in Algorithm 1, the resulting algorithm seamlessly combines neural policy learning and local search in a unified, end-to-end training pipeline.
Benchmark Setups. We implement the PO algorithm upon various RL-based neural solvers, emphasizing that it is a general algorithm not tied specific model structure. The fundamental COPs including TSP, CVRP and FFSP, serve our testbed. In routing problems, the reward r(x, 7) is defined as the Euclidean length of the trajectory т. The TSP aims to find Hamiltonian cycle on graph, minimizing the trajectory length, while the CVRP incorporates capacity constraints for vehicles and points, along with a depot as the starting point. Our main experiments utilize problems sampled from a uniform distribution, as prescribed in (Kool et al., 2019). The experiments the FFSP are conducted to schedule tasks across multiple stages of machines with the objective of minimizing the makespan (MS.), which refers to the total time required for completing all tasks. To evaluate generalization capabilities, we conduct zero-shot testing on problems with diverse distributions as specified
A potential concern lies in the off-policy nature of LS- refined solutions, since existing REINFORCE-basee algo- rithms require on-policy sampling. When adopting such fine-tuning process into REINFORCE, distribution shifts introduced by LS could demand importance sampling to correct for. However, during fine-tuning PO's preference- based objective naturally aligns with an imitation learning perspective (e.g., BC (Pomerleau, 1988) and DAgger (Ross
6

---

Preference Optimization for Combinatorial Optimization Problems
Table 2: Experiment results on FFSP. MS and Gap are evaluated on Ik instances, Time are summation of them. indicate the results are sourced from MatNet (Kwon et al., 2021) and Aug. indicate the data augmentation for inference.
FFSP20
FFSP50
FFSP100
Solver
MS.
Gap
Time MS.
Gap
Time MS.
Gap
Time
CPLEX (60s)*
46,4
84.13%
17h
X
CPLEX (600))*
36.6
45.24%
167h
Heuristic
Random
47.8
89.68%
Im
93.2
88.28%
2m
167.2
87.42%
3m
Shortest Job First
31.3
24.21%
40s
57.0
15.15%
1m
99.3
11.33%
2m
Genetic Algorithm
30.6
21.43%
56.4
13.94%
16h
98.7
10.65%
29h
Particle Swarm Opt.
29.1
15.48%
13h
55.1
11.31%
26h
97.3
9.09%
48h
(Neural Solver
MatNet (RF)
27.3
8.33%
8s
51.5
4.04%
14s
91.5
2.58%
27s
MatNet (PO)
27.0
7.14%
8s
51.3
3.64%
14s
91.1
2.13%
27s
MaiNet Aug.)
25.4
0.79%
3m
49.6
0.20%
8m
89.7
0.56%
23m
MatNet (PO+Aug.)
25.2
0.00%
3m
49.5
0.00%
8m
89.2
0.00%
23m
in (Bi et al., 2022) and on standard benchmark datasets: TSPLib (Reinelt, 1991) and CVRPLib (Uchoa et al., 2017). The hyperparameter configurations for these solvers pri- marily follow their original implementations, with detailed specifications provided in Appendix E.3. Most experiments were conducted on a server with NVIDIA 24GB-RTX 4090 GPUs and an Intel Xeon Gold 6133 CPU.
ready maintain sufficient diversity in their solution sampling. This calibration prevents excessive exploration that could impede convergence. Further details regarding our parame- ter tuning methodology are provided in Appendix E.2.
4.1. Comparison with Existing Algorithms on Standard Benchmarks
Baselines. We employ well-established heuristic solvers, including LKH3 (Helsgaun, 2017), HGS (Vidal, 2022), Concorde (Applegate al., 2006) for routing problems and CPLEX (Cplex, 2009) for FRSP, to evaluate the op- timality gap. We also compare against RL-based neural solvers that use variants of REINFORCE: AM (Kool et al., 2019), POMO (Kwon et al., 2020). Sym-NCO (Kim et al., 2022), Pointerformer (Jin et al., 2023) and ELG (Gao et al., 2024) for TSP/CVRP, and MatNet (Kwon et al., 2021) for FFSP. Additional experiments on large scale COPs with hybrid solver DIMES (Qiu et al., 2022) are included in Appendix F.1. Since all these neural solvers are originally trained using modified FEINFORCE methods, we collec- tively refer to these algorithms as RF(s) for simplicity. AM estimates the advantage function using its previous step solver, while POMO refines this by averaging the quality of sampled solutions from the same instance as a base- line. Building upon POMO, Sym-NCO further improves REINFORCE by leveraging problem equivalences for data augmentation, and Pointerformer enhances stability through reward normalization (i.e., reward shaping).
We aim to compare the proposed Preference Optimization (PO) method with existing modified REINFORCE (termed as RF) methods, considering sample efficiency during train- ing, solution quality during inference and generalization ability on unseen instances with different distributions and sizes on TSPLib and CVRPLib.
Sample Efficiency. The training performance of PO and RF upon POMO, Sym-NCO and Pointerformer are illustrated in Figure 2. PO achieves convergence speed 1.5x to 2.5x faster than RFs on such solvers. Notably for POMO and Sym-NCO, training with PO for 80 epochs yields compa- rable performance to that with RF for 200 epochs. Sim- ilar improvements are observed for Pointerformer. For FFSP using MatNet and large-scale TSP using DIMES, PO achieves comparable performance with only 60%-70% training epochs that of RFs. This demonstrates the in- herent exploration ability of PO, which stem from entropy- regularized objective in Eq. 3. Additional experiments on COMPASS (Chalumeau et al., 2023) and Poppy (Grinsztajn et al., 2023) are included in Appendix F.3.
Choice of parameter a. The parameter a in PO framework stems from the entropy-regularize objective, which gov- erns the exploration-ee axploration-exploitation exploittaionn trade-off during training. Higher a values increase entropy regularization, thereby pro- moting exploration of the solution space, while lower values emphasize exploitation. In our implementation, we system- atically adopt lower a values for training the solvers that incorporate built-in exploration mechanisms (e.g., POMO, Sym-NCO, and Pointerformer), as these architectures al-
Solution Quality. As shown in Table 1, while sharing the same inference times, models trained with PO mostly outperform those trained with the RFs in terms of solution quality. We also perform fine-tuning with Local Search (2-Opt (Croes, 1958) for TSP and swap* (Vidal, 2022) for CVRP) as mentioned in Section 3.4. After few steps for fine-tuning, POMO achieves an gap of only 0.03% on TSP- 100 and 1.19% on CVRP-100, demonstrating that when approaching the optimal solution, PO can further enhance

---

Preference Optimization for Combinatorial Optimization Problems
Table 3: Zero-shot generalization experiments on TSPLib and CVRPLib-Set-X benchmarks. Results show averaged computational time over entire testing set and optimality gaps across different problem size ranges. The SL and RL indicate Supervised Learning and Reinforcement Learning paradigms respectively.
TSPLib
CVRPLib
Solver
Paradigm
(0, 200
(200, 1002]
Total Gap
(0, 200
(200, 1000]
Total
Time
Time
Gap
Gap
Gap
Gap
Gap
LKH3
Heuristic
0.00%
0.00%
0.00%
24s
0.36%
1.18%
1.00%
16m
HGS
Heuristic Heuristic+SL
0.01% %
0.13%
0.11%
16m
NeuroLKH (Xin et al., 2021b)
0.00%
0.00%
0.00%
24s
0.47%
1.16%
0.88%
16m
POMO (Kwon et al., 2020)
3.07%
13.35%
7.45%
0.41s
5.26%
11.82%
10.37%
0.80s
Sym-NCO (Kim et al., 2022)
2.88%
15.35%
8.29%
0.34s
9.99%
27.09%
23.32%
0.87s
Neural Solver+RI.
Omni POMO (Zhou et al., 2023)
1.74%
7.47%
4.16%
0.34s
5.04%
6.95%
6,52%
0.75s
Pointerformer (Jin et al., 2023)
2.31%
11.47%
6.32%
0.24s
LEHD (Luo et al., 2023)
2.03%
3.12%
2.50%
1.28s
11.11%
12.73%
12.25%
1.67s
BQ-NCO (Drakulic et al., 2023)
1.62%
2.39%
2.22%
2.85s
10.60%
10.97%
10.89% 3.36s
Neural Solver+SL
DIFUSCO (Sun& & Yang. 2023)
1.84%
10.83%
5.77%
30.68s
T2TCO (Li ct al., 2023)
1.87%
9.72%
5.30%
30.82s
ELG (RF) (Gao et al., 2024) ELG (PO)
1.12%
5.90%
3.08%
0.63s
4.51%
6.46% 6.37 %
6.03%
1.90s
Neural Solver+RL
1.04% %
5,84%
3.00%
0.63s
4.39% %
5.94%
1.90s
the policy by using expert knowledge to fine-tune. Moreover, we extended our evaluation to the FFSP. As summarized in Table 2, solvers trained with PO consistently achieve optimal compared to their RF counterparts and heuristic solvers. These results confirm that PO not only improves training efficiency but also leads higher-quality solutions.
inferior ones. Additionally, Figure 3b presents the distri- bution of advantage scales, where RFs exhibits a narrow, peaked distribution around zero, indicating limited differ- entiation. Conversely, PO-based methods display broader distributions, covering a wider range of both positive and negative values. This indicates PO's ' enhanced ability to dis- tinguish between high- and low-quality trajectories, further supporting its effectiveness in solvers' learning process.
Generalization Ability. As PO is general algorithmic improvement that can be applied to RL-based solvers, it could inherit the architectural advantages of existing neural solvers and enhance them. To empirically validate this, we adopt it to the ELG (Gao et al., 2024), which is specifically designed for generalization by incorporating local policy. The zero-shot experiments on TSPLib and CVRPLib-Sen Set-S in Table 3 demonstrate PO improves results in all cases com- version ELG
Furthermore, Figure 3e evaluates the consistency of the poli- cies. PO significantly improves the consistency compared to RFs, and fine-tuning a pretrained solver with local search within PO framework further enhances consistency.
Diversity for Exploration. One limitation of existing REINFORCE-basee algorithms is its incompatibility with entropy regularization at the trajectory level. In contrast, the PO method is derived from an untropy-regularizee objective, which inherently promotes exploration. We compare the sum of entropy at each step during the early stage of train- ing between PO and RF. As shown in Figure 3d, the model trained using PO achieves significantly higher entropy, indi- cating a more diverse set of explored strategies. On the other hand, the RF update scheme results in lower entropy, poten- tially leading to less efficient exploration. In conclusion, PO effectively balances exploration and exploitation, enabling the model to explore the solution space more thoroughly.
pared with their original REINFORCE- (RF). Further results about cross dioss-distribttion generalization experiments are included in Appendix F.5.
4.2. How Effectively does PO Balance Exploitation and Exploration?
Consistency of Policy. A key superiority of the proposed PO algorithm is its ability to consistently emphasize bet- ter solutions, independent of the numerical values of the advantage function. Figure 3a compares the advantage as- signment between PO and REINFORCE- based algorithms. PO marginally separates high-quality trajectories by assign- ing them positive advantage values while allocating negative values to low-quality ones. In contrast, RFs struggles to dif- ferentiate trajectory quality, with most advantage values centered around zero. This distinction showcases PO's ca- pability to both highlight superior solutions and suppress
Study on Preference Models. A crucial aspect of PO is the choice of the preference model, as discussed in Sec- tion 3.3. Different preference models may lead to varying implicit reward models, as outlined in Eq. 7 and 8. As- suming a differentiable paired preference model f(-), the generalized form of the latent reward assigned for each
8

---

Preference Optimization for Combinatorial Optimization Problems
POMO RE
3am-K001 RE
Pointes RF
DT
POMO420
Rou-NOO4PP
A.0
Printtefsccure-POO
Bxy
1725
1:39
1.33
7.02
2.0g
Fan
1.79
7.8
78
1.79
Ejurch
120
200
80
Epres
160
770
Ejuch
200
20
40
Epoch
80
300
(a) POMO
(b) Sym-NCO
(c) Pointerformer
(d) Preference Models
Figure 2: (a)-()): Comparison of PO and RFs on TSP- on different neural solvers; PO achieves RFs-level performance in only 40% 60% training epochs, and surpasses RFs' solution quality consistently. (d): Comparison of different preference
models: Brarley-Terry (BT), Plackett-Luce (PL), Thurstone (Th), and unbounded Exponential (Exp) (Azar et al., 2024).
RF
RF
BEINFORCE
PO
PO
P0-3T
P Pinetune
75%
12
75%
62%
5.5
62%
57%
1.6
Index of Socted Solucione Looe
Scale
52%
ARINP ORCK
10
10
(a) Advantage Separation
(b) Advantage Scales
(c) Consistency of Policies
(d) Trajectory Entropy
Figure 3: (a): Advantage values for solutions sorted by their length, sampled from the trained model, PO significantly assigns separable advantage values than RF. (b): Distribution of advantage scales among different algorithms, comparing REINFORCE-bass method, PO with the Thurstone model (PO-Th), and PO with the Bradley-Terry model (PO-BT), (c): Consistency measured as P(T(TI)= > π(τ2) r(TI) > r(r2)). PO shows higher consistency than RF, with further improvement after fine-tuning. (d): Trajectory entropy, which is calculated as the sum of entropy at each step.
T will be: 1 Eres, ( 95(T', (O(T',T,, ,T,,)] where Or(T,
generate near-optimal solutions without additional time dur- ing inference Extensive experimental results demonstrate the practical viability and effectiveness of our approach, achieving superior sample efficiency and solution quality compared to common algorithms in RIACO.
[3y1 xx= x',)) (r(z, > r(x,7))) -(Fa(z,)-tola.-> for any 7/ E S.. The results, shown in Figure 2d, indi- cate that the Bradley-Terry model outperforms the others TSP-100. This suggests an interesting direction for further research, exploring the rationale behind the choice of prefer- ence models on different problems and their impact on the optimization landscape. More analyses and discussions are provided in Appendix F.4.
Notably, our work distinguishes itself from preference opti- mization methods in RLHF especially for LLMs in a criti- cal dimension. While RL.FF typically relies on subjective, offline human-annotated datasets, our Preference Optimiza- tion framework for COPs employs active, online learning strategy grounded in objective metrics (e.g.. route length) to identify and prioritize superior solutions.
5. Conclusion
In this paper, we introduced Preference Optimization, novel framework for solving COPs. By transforming quan- titative reward signals into qualitative preference signals, PO addresses the challenges of diminishing reward differ- ences and inefficient exploration inherent in traditional RL approaches. We naturally integrate PO with heuristic lo- cal search techniques into the fine-tuning process, enabling neural solvers to escape local optima during training and
Despite the promising results, we acknowledge several avenues for future research. The stability of our re- parameterized reward function across diverse COPs war- rants comprehensive investigation. Looking ahead, beyond COPs, applying PO to optimization problems where reward signals are difficult to design but preference information is readily available, such as multi-objective optimization, remains a valuable direction.

---

Preference Optimization for Combinatorial Optimization Problems
Acknowledgment
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems, 30, 2017.
We would like to express our sincere gratitude to the anony- mous reviewers and (S)ACs of ICML 2025 for their thought- ful feedback and insightful comments, which have been instrumental in enhancing the quality of this work. We deeply appreciate their dedication to the scientific commu- nity. This work was supported by the National Key R&D Program of China 400241444000000000110000024 SSTIC Grant( (XXXXKX0002002333510000000 KJZD2203309331 149160 32, GJJNZ2202402 1304400) and Beijing Key Lab of Networked Multimedia.
Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., and Schrijver, A. Combinatorial optimization. Unpublished manuscript, 10:75-99: 1994.
Cplex, I. V12. 1: User's manual for cplex. International Business Machines Corporation, 46(53):157, 2009.
Croes, G. A. A method for solving traveling- salesman problems. Operations research, 6(6):791-812, 1958.
Impact Statement
1 Costa, P. R., Rhuggenaath, J., Zhang, Y., and Akcay, A. Learning 2-opt heuristies for the traveling salesman prob- lem via deep reinforcement learning. In Asian Conference Machine Learning, pp. 465-480. PMLR, 2020.
This paper presents work whose goal is to advance the field of Machine Learning. There may be many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
David, H. A. The method paired comparisons, volume 12. London, 1963.
References
Applegate, D., Bixby, R., Chvatal, V., and Cook, W. Con- corde TSP solver. http:/ / /www. math. uwaterloo. ca/tssp/ ctt.pp/ccccode////////.o/oo 2006.
Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.-M. Bq-neo:
Bisimulation quotienting for efficient neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023. URL https: //arxiv. wwwxiv.orrg/bae hbwgg//bb/23300 2301 03313.
Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandriello, D. A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, pp. 4447-4455. PMLR, 2024.
Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize small pre-trained model to arbitrarily large tsp instances. In Pruceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, pp. 7482-7482, 2021.
Bellemare, M. G., Naddaf, Y., Veness, J., and Bowling, M.
The arcade learning environment: An evaluation plat- form for general agents. Journal of Artificial Intelligence Research, 47:253-2779 2013.
Gao, C., Shang, H., Xue, K., Li, D., and Qian, C. To- wards generalizable neural solvers for vehicle routing problems via ensemble with transferrable local policy, In Larson, K. (ed.), Proceedings of the Thirty- Third In- ternational Joint Conference on Artificial Intelligence, IJCAI-24, pp. 6914-6922. International Joint Confer- ences on Artificial Intelligence Organization. 2024. doi: 10.24963/ijcai. 2024/744. URL https: / /oii org/ 10.24963 /tt.////jjaa...// 2024 / 74. Main Track.
Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 111/111911001 2016.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405 421, 2021.
Garey, M. R. and Johnson, D. S. Computers and intractabil- ity, volume 174, freeman San Francisco, 1979.
Bi, J., Ma. Y., Wang, J., Cao, Z., Chen, J., Sun, Y., and Chee, Y. M. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems, 2022.
Grinsztajn, N., Furelos- Blannoo, D., Surana, S., Bonnet, C., and Barrett, T. D. Winner takes it all: Training per- formant populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Chalumeau, F., Surana, S., Bonnet, C., Grinsztajn, N., Pre- torius, A., Laterre, A., and Barrett, T. D. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.
Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. Re- inforcement learning with deep energy-based policies. International Conference on Machine Learning, pp. 1352-1361. PMLR, 2017.
10

---

Preference Optimization for Combinatorial Optimization Problems
Hejna, J. and Sadigh, D. Inverse preference learning: Preference-based rl without reward function. Advances in Neural Information Processing Systems, 36, 2024.
Ma, Y., Li, J., Cao, Z., Song, W. Zhang, L.., Chen, Z.,, and Tang, J. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pp. 11096-11177 2021.
Helsgaun, K. An extension of the lin-kernighan-helagee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 12, 2017.
Meng, Y., Xia, M., and Chen, D. Simpo: Simple preference optimization with a reference-free reward. arXiv preprint arXiv:2405.147. 2024.
Hong, J., Lee, N., and Thome,, J. Orpo: Monolithic pref- erence optimization without reference model. arXiv preprint arXiv:2403.0769) 2(4):5, 2024.
Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang, S., Lee, Y.-., Johnson, E., Pathak, O., Nazi, A., et al. A graph placement methodology for fast chip design. N 594(7862)2007-212, 2021.
Jiang, Y., Cao, Z., Wu, Y., Song, W., and Zhang, J. Ensemble- based deep reinforcement learning for vehi- cle routing problems under distribution shift. Advances in Neural Information Processing Systems, 36, 2024.
Nazari, M., Oroojlooy, A., Snyder, L., and Takác, M. Rein- forcement learning for solving the vehicle routing prob- lem. Advances in Neural Information Processing Systems, 31, 2018.
Jin, Y., Ding, Y., Pan, X., He, K., Zhao, L., Qin, T., Song, L.,, and Bian, J. Pointerformer: Deep reinforced multi- pointer transformer for the traveling salesman problem. arXiv preprint arXiv:2304.c 09407, 2023.
Ouyang, W., Wang, Y., Weng, P., and Han, S. Generalization in deep rl for tsp problems via equivariance and local search. arXiv preprint arXiv:21
2021.
Kim, H., Kim, M., Ahn, S., and Park, J. Symmetric ex- ploration in combinatorial optimization is free! arXiv preprint arXiv:2306. 0/276, 2023.
Papadimitriou,, C. and Steiglitz, K. Combinatorial Op- timization: Algorithms and Complexity. Dover Publica- tions, 1998.
Kim, M., Park, J., and Park, Sym-nco: Leveraging symmetricity for neural combinatorial optimization. Ad- vances in Neural Information Processing Systems, 35: 1936-1949, 2022.
Park, R., Rafailov, R., Ermon, S., and Finn, C. Disentan- gling length from quality in direct preference optimiza- tion. arXiv preprint arXiv:2403. 19159, 2024.
Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! In International Conference Learning Representations, 2019.
Plackett, R.
The analysis of permutations. Journal of the Royal Statistical Society Series C: Applied Statisties, 24 12:2192200,, 1975.
Korte, B. H., Vygen, J., Korte, B., and Vygen, Combina- torial optimization, volume 1. Springer, 2011.
Pomerleau, A. Alvinn: An autonomous land vehicle in neural network. Advances in Neural Information Processing Systems, 1, 1988.
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min. S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Informa- fion Processing Systems, 33:21 1188-11188, 2020.
Qiu, R. Sun, Z., and Yang. Y. Dimes: A differentiable meta solver for combinatorial optimization problems. Ad- vances in Neural Information Processing Systems, 35: 2022.
Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., and Gwon, Y. Matrix encoding networks for neural combi- natorial optimization. Advances in Neural Information Processing Systems, 14:5133-51444 2021.
Rafailov, R., Sharma, A., Mitchell, E.,, Manning, C. D., Er- mon. S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. Ad- vances in Neurul Information Processing Systems, 36, 2024.
Li, Y., Guo, J., Wang. R., and Yan, J. T2t: From distri- bution learning in training gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Reinelt, G. Tsplib a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
I Luo, F,, Lin, X., Liu, F., Zhang, Q., and Wang, Z. Neu- ral combinatorial optimization with heavy decoder: To- ward large scale generalization. In The 37th Anniversary Conference on Neural Information Processing Systems, NeurlPS 2023, 2023.
Ross, S., Gordon, G., and Bagnell, D. A reduction of imita- tion learning and structured prediction to no-regret online learning. In Proceedings of the International Confer- ence on Artificial Intelligence and Statistics, pp. 637-635, 2011.

---

Preference Optimization for Combinatorial Optimization Problems
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, I.., Kumaran, D., Grae- pel, T., al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Sci- ence, 362(6419): 40-1 1 44, 2018.
Xin, L.., Song, W., Cao, Z., and Zhang, J. Neurolkh: Com- bining deep learning model with lin-kemighan-helage heuristic for solving the traveling salesman problem. Ad- vances in Neural Information Processing Systems, 34: 7472-7483, 2021b.
Sultana, N., Chan, J., Qin, A. K., and Sarwar, T. Learning vehicle routing problems using policy optimisation. arXiv preprint urXiv:2012.13269 2020.
Ye, H., Wang, J., Cao, Z., Liang, H., and Li, Y. Deep- aco: Neural-enhanced ant systems for combinatorial opti- mization. In Advances in Neural Information Processing Systems, 2023.
Sun, Z. and Yang, Y. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Thirtt-seventh Conference on Neurul Information Processing Systems, 2023. URL https: httptt:ttpppeeeeeeeeeeee wpw..eeieeeeeeeeeeeeeeeeee net/forunm id-Jv8Ff01gWV.
Zhou, J., Wu, Y., Song. W., Cao, Z., and Zhang, Towards omni- mumi-generalizable neural methods for vehicle routing problems. In International Conference on Machine Learn- ing, 2023.
Ziebart, B. D., Maas, A. L., Bagnell, A., Dey, A. K., et al. Maximum entropy inverse reinforcement learn- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 8, pp. 1433-1438, 2008.
Sutton, R. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018.
Todorov, E., Erez, T., and Tassa, Y. Mujoco: A physics engine for model-based control. In IEEE/RSJ Interna- tional Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., and Subramanian, A. New benchmark instances for the ca- pacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-88) 858, 2017.
Vidal, T. Hybrid genetic search for the evrp: Open- implementation and swap* neighborhood. Computers & Operations Research, 140:105643, 2022.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. In Advances in Neural Information Processing Systems, pp. (692-2700, 2015.
Wang, C., Yu, Z., McAleer, S., Yu, T., and Yang, Asp: Learn a universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A survey of preference-baste based reinforcement learning meth- ods. Journal of Machine Learning Research, 18(136):
1-46, 2017.
Wu, Y., Song, W., Cao. Z., Zhang, J., and Lim, A. Learn- ing improvement heuristies for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 3359)59057-506, 2021.
Xin, L., Song, W., Cao, 7.,, and Zhang, J. Multi-decoder attention model with embedding glimpse for solving ve- hicle routing problems. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 35, pp. 12042- 12049, 2021a.
12

---

Preference Optimization for Combinatorial Optimization Problems
A. Combinatorial Optimization Problems: TSP and CVRP
provide concise introductions to three fundamental combinatorial optimization problems: the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP) and the Flexible Flow Shop Problem (FFSP).
A.1. Traveling Salesman Problem
The Traveling Salesman Problem (TSP) seeks to determine the shortest possible route that visits each city exactly once and returns the origin city. Formally, given a of cities {c1, (c1,,2,..... c.,..., C.. and distance matrix where Da., represents the distance between cities c; and cj, the objective is find trajectory T (C1, ........ Cas C1) that minimizes the total travel distance:
Σ D(()),((+1)) Jrm
min
Subject to:
is a permutation of c, T(n 7(n+1) =+=1)=-[h
Here, rkk) denotes the li-th city in the trajectory, and the constraint 7(n + ((1) ensures that the tour returns the starting city.
A.2. Capacitated Vehicle Routing Problem
The Capacitated Vehicle Routing Problem (CVRP) extends the TSP by introducing multiple vehicles with limited carrying capacities. The goal is to determine the optimal set of routes for fleet of vehicles to deliver goods to set of customers, minimizing the total distance traveled while respecting the capacity constraints of the vehicles.
Formally, given:
A depot Cp.
A set of customers = {ci, (C,,,C,..... , Jn
A demand d, for each customer Ci.
A distance matrix 1) where Dry represents the distance between locations e; and Cj.
A fleet of m identical vehicles, each with capacity Q
the objective is to assign trajectories {r T2,, ......, Tm) } to the vehicles such that each customer is visited exactly once, the total demand on any trajectory does not exceed the vehicle capacity Q, and the total distance traveled by all vehicles is minimized:
m
|rll-1
min (11772m077)
Subject
Tu (1) = Tb(xa]) co. 4k E
m
U (2), (3)) ...., Tx(TTal 1)} = C,
k=1
(1) # TT(s) vk (i)
Σ d Vk E (1.2.....
Here, (1) denotes the I-th location in the trajectory assigned to vehicle k. The constraints ensure that:
Each trajectory starts and ends at the depot
Every customer is visited exactly once across all trajectories.
No customer is visited more than once within the same trajectory.
The total demand served by each vehicle does not exceed its capacity Q.
13

---

Preference Optimization for Combinatorial Optimization Problems
A.3. Trajectory Representation
In both TSP and CVRP, a trajectory т represents sequence of actions or decisions made by the policy construct solution. For TSP, is single cyclic permutation of the cities, whereas for CVRP, comprises multiple routes, each assigned to vehicle. Our Preference Optimization framework utilizes these trajectories to model and compare solution quality through preference signals derived from statistical comparison models.
A.4. Flexible Flow Shop Problem
The Flexible Flow Shop Problem (FFSP) is combinatorial optimization problem commonly encountered in scheduling tasks. It generalizes the classic flow shop problem by allowing multiple parallel machines at each stage, where jobs can be processed on any machine within stage. The primary goal is to assign and sequence jobs across stages to minimize the makespan, which the total time required to complete all jobs.
The optimization objective for FFSP can be mathematically formulated as:
min Caax max (c) } 0,X
JEJ
subject to:
CT Sj + PPj VjE Vm, E M,
5Th 2 C,,,, Vj J, Vm,-1 E M, S 2 OF v(j.j') E J, if of) o(j'),
Jim, 1, job j assigned machine m
Σ Jj.m. 11 VJEJ.
M.EM
Here: J the set of jobs. M is the set machines at each stage. a represents the sequence of jobs. ær is the assignment matrix of jobs machines. ST is the start time of job on machine m,. CT is the completion time of job j on machine my p) the processing time of job on machine m.. Cmax is the makespan be minimized.
The constraints ensure that jobs are scheduled sequentially on machines, maintain precedence, and adhere to the assignment rules. The FFSP is NP-hard and challenging to solve for large-scale instances.
B. Graph Embedding and Solution Decoder
The Attention Model (Ko) al., 2019) represents a groundbreaking approach that successfully applied the Transformer architecture, based on attention mechanisms, solve typical COPs such as routing and scheduling problems. AM adopts classic Encoder-Decodee structure. Its core innovation lies in the Encoder, which utilizes self-attention mechanism to comprehensively capture relationships between input nodes, while the Decoder employs specialized attention mechanism (often a variant of Pointer Setworks(Vnyalll et al., 2015)) to sequentially construct solutions. Both POMO (Kwon et al., 2020) and Pointerformer (Jin et al., 2023) inherit this fundamental architecture.
B.1. Graph Encoder
The encoder first projects raw features X; RRd (e.g., 2D coordinates) into initial node embeddings via shared MLP:
MLP((x)) E dd
(10)
These initial embeddings are then refined through N layers of multi-head attention (MHA). In each layer / E (1, .N. the embedding for node is updated as follows:
h
h (1-1)
+ MHA (1h5-1))3
(11)
14

---

Preference Optimization for Combinatorial Optimization Problems
h +FFN (h,
(12)
where FFN represents feed-forward network with activation.
To provide the Decoder with global contextual information about the entire problem instance, graph-level embedding h is computed by aggregating all final node embeddings. A common method is mean pooling:
h
1 72
(N)
(13)
where h, ( represents the final embedding of node after N layers of attention, and h captures the aggregate features of the entire graph.
B.2. Solution Decoder
Following the encoding phase, a decoder is employed to sequentially generate the solution in an auto-regressive manner, modeling the COP as a Markov Decision Process. At each step 1, it maintains a context vector hę that represents the current state of the solution construction process. This context is initialized with the graph embedding and the first selected node (often designated starting point, such depot in routing problems):
h
[h; 2
(14)
At subsequent steps > O, the context updated to incorporate information about the most recently selected node:
M (N2
(15)
The context-dependent query vector and node-specific key vectors are computed as:
q Widee h
(16)
Q
kj- Wkhh (N)
(17)
The compatibility between the current context and each potential next node is calculated using an attention-based scoring mechanism:
C tanh
q. k, Vdx
if E U4
Mej
(18)
-00
otherwise,
where C is a temperature scaling parameter, dnis the dimension of the hidden representation, and U4 represents the of feasible (typically unvisited) nodes step t.
Finally, by applying the softmax function to the logits, the probability distribution for selecting the next node T is obtained:
exp(ui))
p(T. = j St, T1--1) EvEy, exp (ex))
(19)
B.3. Model Variants and Extensions
Different architectural variants have been proposed to enhance the performance of attention-based neural solvers:
POMO (Kwon et al., 2020) leverages the inherent symmetry in many COPs by exploring multiple trajectories starting from different initial nodes. For a problem with nn n nodes, POMO generates nn n different solutions by starting the decoding process from each node, sharing parameters across all instances to improve training efficiency.
Pointerformer (Jin al., 2023) enhances the encoder-decoder architecture with reversible residual network in Transformer blocks to effectively reduce the memory demand for larger-scale problems.
Sym-NCO (Kim et al., 2022) further exploits problem symmetry through sophisticated augmentation techniques, allowing the model to learn invariant representations that generalize better across different problem instances.
In all these variants, the core principle of encoding graph structure via attention mechanisms and decoding solutions via pointer-based selection remains consistent, demonstrating the flexibility and effectiveness of this paradigm for neural combinatorial optimization.
15

---

Preference Optimization for Combinatorial Optimization Problems
C. Preference Models
In this section, we provide a concise overview of three widely used preference models: the Bradley-Terry (BT) model, the Thurstone model, and the Plackett-Luce (PL) model. These models are fundamental statistical comparison modeling and form the basis for transforming quantitative reward signals into qualitative preference signals our Preference Optimization (PO) framework.
C.1. Bradley-Terry Model
The Bradley-Terry model probabilistic model used for pairwise comparisons. It assigns positive parameter each trajectory Ti, representing its preference strength. The probability that trajectory is preferred over trajectory тj is given by:
exp(f(T:)) p(T: x ,イ)>) exp(f(r.) + +xp((f(T,))
(F()) =
This model assumes that the preference between any two trajectories depends solely on their respective preference strengths, and it maintains the property of transitivity.
C.2. Thurstone Model
The Thurstone model, also known as the Thusstone-Mosteller model, is based on the assumption that each trajectory тN has an associated latent score which is normally distributed. The probability that trajectory is preferred over trajectory Tj modeled as:
[f(T.) (f(m)) (f(z)-((TT) -((T))))))))))){)))))))
p(T, > ==)= =
where & is the cumulative distribution function of the standard normal distribution, and represents the standard deviation of the underlying noise. This model accounts for uncertainty in preferences and allows for probabilistic interpretation of comparisons. We adopt a normal distribution throughout this work.
C.3. Plackett-Luce Model
The Plackett-Luce model extends pairwise comparisons to handle full rankings of multiple trajectories. It assigns a positive parameter A; to each trajectory т;, representing its utility. Given a set of trajectories to be ranked, the probability of observing a particular ranking 7 (TI, T2...., Tn) is given by:
P(7) II exp(f(Tx))
Lez exp(f(T,))
This model is particularly useful for modeling complete rankings and can be extended to partial rankings. It preserves the property of independence of irrelevant alternatives and allows for flexible representation of preferences over multiple trajectories.
D. Mathematical Derivations
D.1. Deriving the Optimal Policy for Regropy-Regularizeed RL Objective
In this section, we derive the analytical solution for the optimal policy in an entropy-regularizzed reinforcement learning objective.
Starting from the catropy-regularigg RL objective in Eq. 3:
max
ELED
E (E [r(x, +
a7l (T [x)]]
16

---

Preference Optimization for Combinatorial Optimization Problems
where H ( x)) (rla)) (I ()) is the entropy of the policy, and 0 the regularization coefficient.
We can rewrite the objective as:
max EgND, (-m(r(a)) [r(x, 7) a log (( x)]
(20)
Our goal is to find the policy x " æ) that maximizes this objective. To facilitate the derivation, we can express the problem as minimization:
EzND raa(raa) log (( (x) (((2.))
min
(21)
Notice that:
1 -r(,,, log <(r | x)) exp (2, +))
log ( x))
(22)
Introduce the partition function ((x) Σ, exp (2r(2, and define the probability distribution:
n (" x) = ( exp (frles)))
(23)
This defines valid probability distribution over trajectories T for each instance as I (r x)) > 0 and Σ, <-(r x)) Substituting Eq. 23 into Eq. 22, we have:
1.
M( x:) 1 -r( = log nT (T x))
log [T x)
+ log ((r).
(24)
Therefore, the minimization problem in Eq. 21 becomes:
π(T x) n (T x) + log 2(x)
min ED Brwm(tle)
log
(25)
Since log 7xx) does not depend n minimizing over reduces minimizing the Kullback-Leibhe (KI.) divergence between <[r ()) and =²(T 2):
Ein [DLL (a(r (x) || n (r [x)]
(26)
where the KL divergence defined as:
log T( x)) π- x)
DKL (T(T x)) x x)) = E (r(a(r)))
The KL divergence is minimized when ক ()) = ( x) according to Gibbs' inequality, So, the optimal policy is:
Z(x) exp (Er(e.)).
T (T x))
(27)
This shows that the optimal policy under the entropy-regularized RL objective is proportional to the exponentiated reward function, normalized by the partition function 7(x).
Conclusion. We have derived that the optimal policy n" (r x) in the rntropy-regularized RL framework given by Eq. 27. This policy assigns higher probabilities to trajectories with higher rewards, balanced by the entropy regularization parameter a, which controls the trade-off between exploitation and exploration.
17

---

Preference Optimization for Combinatorial Optimization Problems
D.2. Proof of Proposition 3.1
Proposition. Let f(z, T) be a reward functionn consistent with the Bradley-Terry, Thurstone, Plackett-Luce models. For given reward function F (2, T), if there exists function h(z) such that F' (x, f(z, h(æ). then both f(2,T) and (x, induce the same optimal policy in the context of an entropy reinforcement learning problem.
Proof: In entropy-regularizee reinforcement learning framework, the optimal policy n² (r (:) for given reward function
f(z,7 T) is given by:
1
! a
f(a.))
<"(r (r|
exp
((r)
where 0 is the temperature parameter (inverse of the regularization coefficient), and Z(x) is the partition function defined as:
Z(x) = E exp (flaat).
Similarly, for the reward function f'(x,T) r) = f(x, T)- - h(x), the optimal policy r'"(T | ax) is:
exp f (c. ('(x) exp ((x
n" (T x.)
(28)
('(r)
where (z) is the partition function corresponding to f' fr r):
(L Σ exp -((o)))
2'xx) = Σ exp a
xxx)=
Simplifying the exponent in Eq. 28:
exp ((1,,)) = =exp (xxp(1((57) exp (-an(a)
Since h(x)) depends only on and not the term exp (- is constant with respect to Therefore, we can rewrite Eq. 28 as:
1 (--n(ar) exp
1 (2)(,,))
n (T x))
7x(x))
exp
a
(29)
Combining constants:
<" (z) = exp (-
1 ((((.)))
exp
7'(x)
Notice that the term exp(-).(x)) (x)
is normalization constant that ensures Σ, T'" x)) Similarly, for " x)) the
normalization constant is 7(a)*
Since both <r I and 7' (T i) are proportional to exp (1r(x, they differ only by their respective normalization constants. Therefore, they assign the same relative probabilities to trajectories т.
To formalize this, consider any two trajectories 71 and 72. The ratio of their probabilities under n" (T xx) is:
18

---

Preference Optimization for Combinatorial Optimization Problems
("i z) exp ((, exp (1) ((2, T (T2 z) exp (2,
(30)
Similarly, under n"*(T (T x):
(Ti x
exp (z,
exp (() F(x
(31)
(1² x))
exp (z,
Substituting (x, f(1,T) h((x):
(r, - (5, T2) [fx h(x)) (f(x,
m) -f(r, 12)-
Therefore, the ratios Eq. and 31 are equal:
(Ti
x)) <' x) T' (T2 x)
12 x)
Since the policies assign the same relative probabilities all trajectories, and they are both properly normalized, it holds:
x (' (2) VT.
Thus, f(x,7) and fi( T) induce the same optimal policy in the context of an entropy-regularized reinforcement learning problem. This result holds for the Haudeey-Terry Thurstone, and Plackett-Luce models because these models relate preferences to differences in reward values, and any constant shift h(x) in the reward function does not affect the differences between reward values for different trajectories.
E. Experiment Detail and Setting
E.1. Implementation Details of the Code
The implementation of the Preference Optimization (PO) algorithm in Python using PyTorch is as follows:
import torch. nn. functional as F
def prefereence_optiiazzziioo (reward, log_prob):
reward: reward for all solutions, shape (B, P)
poo_prob: policy log prob, shape (B, P)
preference rewardl:, i, None] rewardl;, None, :] log_prob_pate pair poo_prob[;, i, None] pro_ None, :]
# Under Brandley-Terry model:
log = torch. log (F ss log_prob_pair))
Exponential: torch. log (torcc.rrccc... exp (self. pog_prob_pair)) pf_log self.alpha pog_prob_pair
loss -torch. moarchmeeaniee (pf_log preference)
return loss
19

---

Preference Optimization for Combinatorial Optimization Problems
E.2. Parameter Tuning
Methodological views. From PO's entropy-reguulrrized objective, the parameter a represents the exploration-exploiatiio trade-off. Higher values promote exploration, while lower values emphasize exploitation. In experiments, employed grid search within 0.005, 0,01, 0.05, 0.1, 0.5, 1.0, 2.0 for each problem-model combination.
Empirical views. Our empirical findings suggest that PO's performance is influenced by two additional factors:
Nenwork architecture's 's inherent exploration capacity: Models with built-in exploration mechanisms (c.g., POMO and its variants with multi-start approaches) typically benefit from lower a values to prioritize exploitation but DIMES require more exploration with higher a values. For POMO and its variants on different problems, we observed that routing problems typically perform well with in the range of le-2 to le-3, while FFSP benefits from a values between 1.0 and 2.0.
Preference model selection: As PO serves flexible framework, different preference models could yield distinct parameterized reward assignments, necessitating different calibrations. The Exponential model could be good candidate when the Bradley-Tery model underperforms on new problems, particularly for challenging problems, before exploring alternatives like Thurstone or Plackett-Luce models (which generalize Bradley-Terry beyond pairwise comparisons). Besides, we also provide detailed analyses regarding different preference models Appendix F.4.
Adapting to new problems. For applications, there
intuitions for practical extensions:
Length-control regularization: For problems where sampled solutions have varying lengths and shorter solu- tions with lower costs are preferred, length-control regularization factor [ can be effective, resulting in: f(a A log To()o())))) mral log To (Falz)))
Margin enhancement: For models with limited capacity, margin enhancement term f(x [log To (x) log (0(r2)))) -7) can help prioritize better solutions, where serves margin parameter when f(-) is a non-linear function.
E.3. Hyperparameters Setting
In our experimental setup, we the tanh clip to 50.0 for VRPs, which has been shown facilitate the training process (Jin al., 2023). The following table presents the parameter settings for the four training frameworks: POMO (Kwon et al.,
2020), Pointerformer (Jin et al., 2023), AM (Kool al., 2019), and Sym-NCO (Kim et al., 2023).
POMO framework hyperparameter settings:
Table Hyperparameter setting for POMO.
TSP-100 CVRP-
Alpha
0.05
0.03
Preference Function
Exponential
Epochs
2000
4000
Epochs (Finetune)
100
200
Epoch Size
100000
50000
Encoder Layer Number
6
6
Batch Size
64
64
Embedding Dimension
128
128
Attention Head Number
8
Feed Forward Dimension
512
512
Tanh Clip
50
50
Learning Rate
3e-4
3e-4
Additional linear projection layer was adopted followed MHA decoder as (Kool et al., 2019).
20

---

Preference Optimization for Combinatorial Optimization Problems
Pointerformer framework hyperparameter settings:
Table 5: Hyperparameter setting for Pointerformer.
TSP
Alpha
0.05
Preference Function
BT
Epochs
2000
Epoch Size
100000
Batch Size
64
Embedding Dimension
128
Attention Head Number
8
Feed Forward Dimension
512
Encoder Layer Number
6
Learning Rate
le-4
AM framework hyperparameter settings.
Batch size of 512 contains 32 instances, each with 16 solutions, totaling 512
trajectories:
Table 6: Hyperparameter setting for AM.
TSP
CVRP
Alpha
0.05
0.03
Preference Function
BT
BT
Epochs
100
100
Epoch Size
1280000
1280000
Encoder Layer Number
3
Batch Size
256
256
Embedding Dimension
128
128
Attention Head Number
8
Tanh Clip
50
50
Learning Rate
le-4
lc-4
Sym-NCO framework hyperparameter settings:
Table 7: Hyperparameter setting for Sym-NCO.
TSP
CVRP
Alpha
0.05
0.03
Preference Function
BT
Exponential
Epochs
2000
4000
Epoch Size
100000
50000
Batch Size
64
64
SR Size
Embedding Dimension
128
128
Attention Head Number
Feed Forward Dimension
512
512
Encoder Layer Number
Learning Rate
le-4
1e-4
21

---

Preference Optimization for Combinatorial Optimization Problems
DIMES framework hyperparameter settings:
Table 8: Hyperparameter Setting for DIMES.
TSP500
TSP1000
TSP10000
Alpha
2
2
Preference Function Exponential Exponential Exponential
KNN K
50
50
50
Outer Opt
A
AdamW
Adam
Outer Opt LR
0.001
0.001
0.001
Outer Opt WD
le-5
le-5
le-5
Net Units
32
32
Net Act
SiLU
SiLU
SiLU
Emb Depth
12
12
12
Par Depth
3
3
3
Training Batch Size
3
3
3
MАTNEТ framework hyperparameter settings:
Table 9: Hyperparameter Setting for MATNET.
FFSP20
FFSP50
FFSP100
Alpha
1.5
Preference Function
Exponential Exponential Exponential
Pomo Size
24
24
24
Epochs
100
150
200
Epoch Size
1000
1000
1000
Encoder Layer Number
3
3
3
Batch Size
50
50
50
Embedding Dimension
256
256
256
Attention Head Number
16
16
16
Feed Forward Dimension
512
512
512
Tanh Clip
10
10
10
Learning Rate
le-4
le-4
le-4
F. Additional Experiments.
F.1. Experiments on Large Scale Problems
We further conduct experiments on large-scale TSP problems to validate the effectiveness of PO using the DIMES model (Qiu et al., 2022). DIMES leverages a reinforcement learning and meta-learning framework to train parameterized heatmap, with REINFORCE as the optimization method in their original experiments. Solutions are generated by combining the heatmap with various heuristic methods, such as greedy decoding, MCTS, 2-Opt, or fine-tuning methods like Active Search (AS), which further train the solver for each instance.
As summarized in Table 10, our experiments demonstrate that PO improves the quality of the heatmap representations compared to REINFORCE. Across all decoding strategies (e.g., greedy, sampling, Active Search, MCTS (with 2-Opt as an inner loop)), PO-trained models consistently outperform their REINFORCE-trained counterparts in terms of solution quality, as evidenced by lower gap percentages across TSP500, TSP1000, and TSP10000. This confirms that PO enhances the learned policy, making more effective regardless of the heuristic decoding method applied.
22

---

Preference Optimization for Combinatorial Optimization Problems
Table 10: Experiment results on large scale TSP.
TSP500
TSPI000
TSP10000
Method
Len.
Gap
Time
Len. 4
Gap
Time Len.
Gap
Time
LKH-3
16.55
0.00%
46.28m
23.12
0.00%
2.57h 71.79 0.00% 8.8h
DIMES-GIE G(RL)
19.30 16.62%
0.8m
26.58
14.96%
1.5m 86.38 20.36% 2.3m
DIMES- G(PO)
18.82
13.73%
0.8m
26.22
13.39%
1.5m 85.33 18.87% 2.3m
DIMES-S(RL)
19.11
15.47%
0.9m
26.37
14.05%
1.8m 85.79 19.50% 2.4m
DIMES-S(PO)
18.75
13.29%
0.9m
26.07
12.74%
1.8m 85.21 18.67% 2.4m
DIMES-AS(RL)
17.82 7.68%
2h
24.99
8.09%
4.3h 80.68
12.39% 2.5h
DIMES-AS(PO)
17.78
7.42%
2h
24.73
6.97%
4.3h 80.14
11.64%
2.5h
DIMES- (ECESL)
16.93
2.30%
3m
24.30
5.10%
6.3m
74.69
4.04%
27m
DIMES- (ECESSO
16.89
2.05%
3m
24.33
5.23%
6.3m
74.61
3.93%
27m
F.2 Training POMO for Long Time
Figure 4 compares the training efficiency of the PO and RL algorithms for TSP and CVRP. In the TSP task (a), PO reaches an objective value of 7.785 at epoch 400, while RI requires up to 1600 epochs to achieve comparable performance, demonstrating the sample efficiency of PO. This difference becomes more pronounced as training progresses. In the more challenging CVRP environment (b), PO continues to outperform RL, indicating its robustness and effectiveness in handling more complex optimization problems.
For TSP, each training epoch takes approximately 9 minutes, while each finetuning epoch with local search takes about 12 minutes. For CVRP, training epoch takes about 8 minutes, and finetuning epoch takes around 20 minutes. Since local search is executed on the CPU, does not introduce additional GPU inference time. The finetuning phase constitutes 5% of the total epochs, adding manageable overhead to the overall training time.
RL.
RC
PO
Pо
7.9
A0t Lenggh
7.85
Avg. Length
7.82
16
15.95
15.83
200
1000 1200 Epoch
1600 1800 2000
1600 2000 Epoch
2800 3200 3600
(a)
(b)
Figure 4: (a) Training curve for TSP (N=100) over 2000 epochs. (b) Training curve for CVRP (N=100) over 4000 epochs.
E33. Experiments on COMPASS and Poppy
To validate the PO's flexibility, adapt it to the recent population based framework COMPASS (Chalumeau al., 2023) and Poppy (Grinsztajn et al., 2023). COMPASS learns a continuous latent space representing diverse strategies for combinatorial optimization and Poppy trains a population of reinforcement learning agents for combinatorial optimization, guiding unsupervised specialization via a "winner-takes-all" objective to produce complementary strategies that collaborate effectively to solve the problems. We implement PO upon these baselines and train them from scratch for 100k steps on a single 80GB-A800 GPU.
23

---

Preference Optimization for Combinatorial Optimization Problems
TSP-Poppy
TSP- COMP ASS
COMPAES COMPASS4PO
POPPY-PO
12
5.5
Axv Aonrr
Arg.
202
DAL
803
103k
20L
80L
50E
1006
Steps
Steps
(a) TSP-100 Poppy
(b) TSP-100 COMPASS
CVRP-Poppy
CVRP-COMPASS
POPPY POPPY-PO
COMPASS+LL
Ave.
Avg.
183
16.
20k
30k
100k
25k
1tk
83k
103k
Steps
Steps
(c) CVRP-100 Poppy
(d) CVRP-100 COMPASS
Figure 5: Training curves of PO and REINFORCE on Poppy and COMPASS.
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 RI-bbased baselines.
E.4. Preference Modeling
As indicated in (Azar al., 2024), the Bradley-Terry and Thurstone models struggle handle extreme scenarios where p(π > T2) 1. Achieving such near-certain preference requires (1 71) fo T2) - +oo, implying *a(T)) 0. #e(ra)
However, both the logistic function (in the Bradley-Teryy model) and the CDF of the normal distribution (in the Thurstone model) exhibit gradient vanishing this regime, as shown in Figure 6b. natural alternative is the unbounded exponential function f(-) = exp(-), which places much stronger emphasis on preferred solutions compared to Bradley-Terry and Thurstone.
Empirically, we observe that while the Bradley-Terry model performs better on smaller-scale problems (where overfitting is more likely, and a conservative preference function can mitigate this), the exponential function is more effective for scrger-scale or complex (harder) COPs, as it prevents convergence to suboptimal local optima more vigorously. Future research could investigate thcoretical properties these preference models in different reward regimes, develop adaptive mechanisms that switch between them based on problem complexity.
24

---

Preference Optimization for Combinatorial Optimization Problems
Preference Functions
Weight Scaler PucP(MMM)))
Thurstone
Thurstone
Bradley-Terry
Bradley-Terry
Exponential
Exponential
rolx, Tι) - ro(x, T2)
rolx, -r(xx T2)
(a)
(b)
Figure 6: Comparison of three preference models Thhrstone,, Tradley-Terry, and Exponential under different reward differences re (2 T1) (2), (a) Illustrates how each model's 's preference function behaves the reward gap changes. (b) Shows the corresponding weight (gradient) scaling factor, highlighting the gradient vanishing issue in Bradley-Terry and Thurstone for large positive reward gaps, and the strong emphasis provided by the exponential model.
F.5. Generalization
We conducted a zero-shot cross- distrribitiittoonn evaluation, where models were tested on data from unseen distributions. Since models trained purely with RI. tend to overfit the training data distribution (Zhou al., 2023), they may struggle with different reward functions in new distributions. However, training with PO helps mitigate this overfitting by avoiding the need for ground-truse -trth reward signals. Following the diverse distribution setup in (Bi al., 2022), the results summarized in Table I.. Our findings show that the model trained with PO outperforms the original RL-based model across all scenarios.
Table 11: Zero-shot generalization experiment results. The Len and Gap are average on 10k instances.
Cluster
Expansion
Explosion
Grid
Implosion
Method
Len.l
Gap
Len.]
Gap
Len.]
Gap
Len.|
Gap
Len.
Gap
LKH
3.66
0.00%
5.38
0.00%
5.83
0.00%
7.79
0.00%
7.61
0.00%
TSP
POMO-RL
3.74
2.09%
5.41
0.60%
5.85
0.20%
7.80
0.16%
7.63
0.15%
POMO-PO
3.70
1.12%
5.40
0.34 %
5.84
0.06 %
7.79
0.04%
7.62
0.05 %
HGS
7.79
0.00%
11.38
0.00%
12.35
0.00%
15.59
0.00%
15.47
0.00%
CVRP
POMO-RL
7.97
2.28%
11.51
1.29%
12.48
0.97%
15.79
0.86%
15.60
0.87%
POMO-PO
7.93
1.73%
11.49
1.12% %
12.45
0.76 %
15.76
0.63 %
15.57
0.65 %
25


Reviews:
[{"review_id": "gSKBjovCiZ", "reviewer": "Reviewer_HAxz", "summary": "This paper introduces Preference Optimization (PO), a novel method for solving CO problems like TSP and CVRP.\nKey contributions:\n1. The authors transform quantitative reward signals into qualitative preference signals, addressing two major challenges in reinforcement learning for COPs:\n   - Diminishing reward signals as policy improves\n   - Inefficient exploration in vast combinatorial action spaces\n\n2. They reparameterize the reward function in terms of policy and use statistical preference models (like Bradley-Terry) to formulate an entropy-regularized objective that aligns policy directly with preferences.\n\n3. They integrate local search techniques during fine-tuning rather than as post-processing, helping policies escape local optima without adding inference time.\n\n\n## Update after rebuttal\n\nThe authors have partially answered my questions but failed to address all my concerns during the rebuttal. I maintain my rating as weak accept.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n### **1. Including comparison with Poppy and COMPASS**\n\nThank 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.\n\n*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.\n\n*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.\n\nDue 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:\n\n*Results on TSP-100:*\n|Step|10k|20k|30k|40k|50k|60k|70k|80k|90k|100k|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|COMPASS(RF)|75.29%|29.69%|32.43%|51.36%|34.44%|39.23%|27.14%|17.22%|14.02%|10.93%|\n|COMPASS(PO)|9.51%|7.15%|5.89%|4.95%|4.50%|4.32%|4.14%|3.90%|3.76%|3.61%|\n|Poppy(RF)|4.57%|3.85%|3.17%|2.83%|2.59%|2.39%|2.39%|2.24%|2.05%|1.95%|\n|Poppy(PO)|2.28%|1.56%|1.23%|1.03%|0.92%|0.78%|0.71%|0.69%|0.66%|0.63%|\n\n*Results on CVRP-100:*\n|Step|10k|20k|30k|40k|50k|60k|70k|80k|90k|100k|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|COMPASS(RF)|120.82%|58.17%|43.11%|20.38%|14.80%|12.78%|11.46%|10.84%|10.40%|9.79%|\n|COMPASS(PO)|18.84%|10.26%|8.99%|8.10%|7.47%|7.19%|6.91%|6.53%|6.04%|6.50%|\n|Poppy(RF)|14.15%|11.13%|9.42%|8.52%|8.63%|7.16%|6.94%|6.15%|5.91%|5.42%|\n|Poppy(PO)|6.25%|4.54%|3.77%|3.43%|3.11%|2.95%|2.78%|2.65%|2.53%|2.43%|\n\nThe 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. \n\n---\n### **2. Regarding comparison to reward shaping**\n\nWe 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:\n$\\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)$.\nAs 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.\n\nBesides, 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.\n\n---\n### **3. Correction of Equation 3**\n\nWe sincerely thank you for your careful examination and valuable suggestion. We will revise Equation 3 to the more precise form:\n$\\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]$.\n\n---\nWe are deeply grateful for your thoughtful feedbacks, and sincerely hope that these responses address your concerns. We welcome any further discussions or suggesstions.\n\n### **Reference**\n>[r1] [Grinsztajn et al., 2023] Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization. NeurIPS 2023\n>\n>[r2] [Chalumeau et al., 2023] COMPASS: Cooperative Multi-Agent Policy Search for Combinatorial Optimization. NeurIPS 2023", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "The proposed method aims at CO problems, for which TSP, CVRP, and FFSP are standard benchmarks.", "theoretical_claims": "I have not found any concerns.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "This work brings ideas from preference-based optimization (e.g. in RLHF) to combinatorial optimization.", "essential_references_not_discussed": "- [Grinsztajn et al., 2023] Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization.\n- [Chalumeau et al., 2023] Combinatorial Optimization with Policy Adaptation using Latent Space Search", "other_strengths_and_weaknesses": "Strength: formulation of the method\nWeakness: lacks more recent baselines (e.g. Poppy [Grinsztajn et al., 2023] and COMPASS [Chalumeau et al., 2023])", "other_comments_or_suggestions": "None", "questions_for_authors": "1. Optimizers are mostly scale-invariant, e.g. Adam scales updates to be loss scale invariant. The proposed method can be compared to reward shaping. Would you have ablation studies using reward shaping or reward normalization to understand how PO compares to that?\n2. Equation 3: should the entropy term not be inside the expectation over x? (max-entropy framework)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "654M53ppNH", "reviewer": "Reviewer_SKGq", "summary": "This paper attempts to improve the training paradigm of end-to-end deep learning solvers for combinatorial optimization problems. It introduces Preference Optimization (PO) to alleviate the issue of diminishing advantage signals in the later stages of reinforcement learning (RL) training, thereby preventing models from getting stuck in local optima.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n### **1. Broadening comparison with SOTA solvers on large-scale problems and generalization**\n\nWe 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.\n\nSpecifically, 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:\n\n**Results on TSPLib:**\n|Method|(0, 200]|(200, 1002]|Total|Time|Paradigm|\n|-|-|-|-|-|-|\n|LKH3|0.00%|0.00%|0.00%|24s|Heuristic|\n|NeuroLKH|0.00%|0.00%|0.00%|24s|Heuristic+SL|\n|POMO|3.07%|13.35%|7.45%|0.41s|RL|\n|Sym-POMO|2.88%|15.35%|8.29%|0.34s|RL|\n|Omni-POMO|1.74%|7.47%|4.16%|0.34s|RL|\n|Pointerformer|2.31%|11.47%|6.32%|0.24s|RL|\n|LEHD|2.03%|3.12%|2.50%|1.28s|SL|\n|BQ-NCO|1.62%|**2.39%**|**2.22%**|2.85s|SL|\n|DIFUSCO|1.84%|10.83%|5.77%|30.68s|SL|\n|T2TCO|1.87%|9.72%|5.30%|30.82s|SL|\n|ELG-POMO (RF)|1.12%|5.90%|3.08%|0.63s|RL|\n|ELG-POMO(PO)|**1.04%**|5.84%|3.00%|0.63s|RL|\n\n**Results on CVRPLib-Set-X:**\n|Method|(0, 200]|(200, 1000]|Total|Time|Paradigm|\n|-|-|-|-|-|-|\n|LKH3|0.36%|1.18%|1.00%|16m|Heuristic|\n|NeuroLKH|0.47%|1.16%|0.88%|16m|Heuristic+SL|\n|HGS|0.01%|0.13%|0.11%|16m|Heuristic|\n|POMO|5.26%|11.82%|10.37%|0.80s|RL|\n|Sym-POMO|9.99%|27.09%|23.32%|0.87s|RL|\n|Omni-POMO|5.04%|6.95%|6.52%|0.75s|RL|\n|LEHD|11.11%|12.73%|12.25%|1.67s|SL|\n|BQ-NCO|10.60%|10.97%|10.89%|3.36s|SL|\n|ELG-POMO (RF)|4.51%|6.46%|6.03%|1.90s|RL|\n|ELG-POMO (PO)|**4.39%**|**6.37%**|**5.94%**|1.90s|RL|\n\nConsequently, 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.\n\n---\n### **2. Pros and Cons of RL and other paradigms**\n\nWe sincerely appreciate your suggestion. We try to expand our discussion on the Pros and Cons of RL over other paradigms as follows. \n\nGenerally, 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. \n\nBesides, 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.\n\n---\nWe 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.\n\n\n**References**\n>[r1] [Fu Luo et al., 2023]. Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization. NeurIPS 2023.\n>\n>[r2] [Drakulic et al., 2023]. BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization. NeurIPS 2023.\n>\n>[r3] [Sun et al., 2023]. DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization. NeurIPS 2023.\n>\n>[r4] [Xin et al., 2021]. NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem. NeurIPS 2021.\n>\n>[r5] [Li et al., 2023]. T2T: From Distribution Learning in Training to Gradient Search in Testing for Combinatorial Optimization. NeurIPS 2023.\n>\n>[r6] [Liu et al., 2023]. Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy. arXiv:2308.14104.", "claims_and_evidence": "Yes, I believe the evidence is sufficient.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "n/a", "experimental_designs_or_analyses": "The experiment is reliable.", "relation_to_broader_scientific_literature": "See strength", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strengths:\n- The problem addressed by the authors, namely improving the training paradigm of end-to-end neural solvers, is interesting. Introducing preference optimization into this domain is novel. \n- The proposed method is plug-and-play and demonstrates performance improvements across multiple RL-based neural solvers. \nWeaknesses:\n- The paper only compares RL algorithms enhanced with PO to their original RL counterparts. However, it does not benchmark the improvements against other state-of-the-art (SOTA) approaches from different paradigms, such as:\nSupervised learning-based methods (e.g., BQ-NCQ), \nDiffusion model-based methods (e.g., Diffusco), \nHeuristic learning-based solvers (e.g., NeuroLKH). \n- Even if some comparisons do not favor the RL approach, acknowledging the inherent limitations of end-to-end RL methods in this domain and discussing RL’s potential advantages over other paradigms—as well as ways to narrow the performance gap—would add significant value to the paper.\n- The problem scale studied in the main text is too small. The authors are encouraged to incorporate the large-scale generalization experiments from the appendix into the main text and compare against relevant SOTA methods to provide a more comprehensive evaluation.", "other_comments_or_suggestions": "see above\n\n--------------\nUpdate:\nAfter rebuttal, I raised the score from 2 to 3.", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h0cJ4jAbNH", "reviewer": "Reviewer_u9d3", "summary": "This paper proposes a way to modify reinforcement learning (RL) so that it can deal with diminishing reward signals. The key idea is to turn the reward signals into pairwise preferences from which an underlying reward function can be learned. Another contribution of the paper is to use local search to generate additional pairwise preference relations (solution after local search is preferred over solution before local search). \n\nThe ideas are applied to combinatorial optimization problems, and it is shown that the conversion of reward to preference function is helpful on different problems (TSP, CVRP, FFSP) and for different underlying Neural RL approaches (AM, Pointerformer, Sym-NCO and POMO).\n\n## update after rebuttal\nThe authors have addressed my questions and comments. I retain my score and recommend accepting the paper.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n---\n### **1. Math implications behind the proposed PO algorithm**\nWe appreciate this insightful question on the rationale PO model, which can be justified from following aspects.\n\n*Transform numerical signals into ranks*. First, consider the REINFORCE algorithm:\n$$\n\\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].\n$$\nThe 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:\n1) Sensitive to baseline selection;\n2) Sensitive to the numerical scale of reward signals.\n   \n*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.\n\n*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.\n\n---\n### **2. Parameter setting**\nAll parameters in baselines were adopted from their official codes, and we only retrained all models from scratch for comparison.\n\n---\n### **3. Choice of $\\alpha$ in PO**\nWe 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.\n\n---\n### **4. Graph embedding and decoder**\nWe utilize the same graph embedding and decoder as in the original works. We will include a comprehensive summary in the revision.\n\n---\n### **5. Generalization of PO**\nMethodologically, 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:\n\n**TSPLib:**\n|Method|(0, 200]|(200, 1002]|Total|Time|\n|-|-|-|-|-|\n|LKH3|0.00%|0.00%|0.00%|24s|\n|POMO|3.07%|13.35%|7.45%|0.41s|\n|Sym-POMO|2.88%|15.35%|8.29%|0.34s|\n|Omni-POMO|1.74%|7.47%|4.16%|0.34s|\n|Pointerformer|2.31%|11.47%|6.32%|0.24s|\n|LEHD|2.03%|3.12%|2.50%|1.28s|\n|BQ-NCO|1.62%|**2.39%**|**2.22%**|2.85s|\n|DIFUSCO|1.84%|10.83%|5.77%|30.68s|\n|T2TCO|1.87%|9.72%|5.30%|30.82s|\n|ELG-POMO (RF)|1.12%|5.90%|3.08%|0.63s|\n|ELG-POMO(PO)|**1.04%**|5.84%|3.00%|0.63s|\n\n**CVRPLib-Set-X:**\n|Method|(0, 200]|(200, 1000]|Total|Time|\n|-|-|-|-|-|\n|LKH3|0.36%|1.18%|1.00%|16m|\n|HGS|0.01%|0.13%|0.11%|16m|\n|POMO|5.26%|11.82%|10.37%|0.80s|\n|Sym-POMO|9.99%|27.09%|23.32%|0.87s|\n|Omni-POMO|5.04%|6.95%|6.52%|0.75s|\n|LEHD|11.11%|12.73%|12.25%|1.67s|\n|BQ-NCO|10.60%|10.97%|10.89%|3.36s|\n|ELG-POMO (RF)|4.51%|6.46%|6.03%|1.90s|\n|ELG-POMO (PO)|**4.39%**|**6.37%**|**5.94%**|1.90s|\n\nTherefore, these findings verify that PO is also effect in enhancing the generalization ability of RL-based solvers. We will incorporate them into revision.\n\n---\n**Q1:** Yes, the test set differs from the training set. Training data is generated on-the-fly while test data uses different seeds.\n\n---\n**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.\n\n---\n**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].\n\n---\nWe sincerely thank you for your valuable time and insightful comments. We kindly welcome any further questions.\n\n**Reference**\n>[r1] Towards Generalizable Neural Solvers for Vehicle Routing Problems via Ensemble with Transferrable Local Policy. arXiv:2308.14104.\n>\n>[r2] Towards Omni-generalizable Neural Methods for Vehicle Routing Problems. ICML 2023.", "claims_and_evidence": "The main claims are\n- that the proposed transformation of reward signals into preference signals addresses the issue of diminishing reward signals and inefficient exploration.\n- That the reparameterized entropy-regularized objective bypasses the enumeration of the entire action space\n- That the integration with local search helps during training.\n\nThe paper shows on different neural solvers that the transformation of reward signal into preference signal is beneficial. It is also demonstrated that the fine-tuning helps. However, here it is not clear whether the fine-tuning is done in addition or instead of the final iterations of the algorithm without fine-tuning. In the former case, one may wonder whether simply running the algorithm without fine-tuning for some additional generations would have yielded similar results.", "methods_and_evaluation_criteria": "The method is compared with the default method from the literature and with state-of-the-art heuristics such as LKH3 and HGS. The metrics used are optimality gap and inference time that are commonly used in the field.", "theoretical_claims": "I did not review the mathematical derivations in Appendix C.", "experimental_designs_or_analyses": "It is not said explicitly, but I assume the training and test set are different (albeit drawn from the same distribution). Results seem to be based on single training runs, no standard errors are provided, which is not best practice. \nHowever, given the consistency of the results across problems, it seems unlikely that replicating the experiments would lead to very different results. Thus, it does not raise a major concern in my eyes.", "relation_to_broader_scientific_literature": "The proposed mechanism is shown to improve results when integrated into three different methods from the literature, and tested on three different combinatorial problems. There is some relation to Preference-based RL which is discussed.", "essential_references_not_discussed": "I am not aware of missing references.", "other_strengths_and_weaknesses": "- I understand the issue of diminishing reward signals. However, there are many possible solutions, e.g., simply replacing the reward by the rank of the solution. It is not intuitive why the proposed transformation into pairwise preferences is a natural choice. However, it seems to work.\n\n- The name “Preference optimization” seems misleading, as it usually refers to optimization based on preference information where only such information is available, whereas in the current paper, the actual reward function is available but turned into preferences.\n\n- It is not clear how parameters were chosen. I assume parameters for the baseline algorithms are taken from the corresponding original references? How were the alpha and the preference function chosen? How would they be chosen for a new problem (since different settings are chosen for different problems)?\n\n- The paper doesn’t provide any information on e.g. the graph embedding or decoder used. It would be nice to have a summary in the appendix.\n\n- While I believe it is not explicitly stated, the models are trained separately for different problem sizes. In practice, a heuristic that only works on a specific size seems very limited ted. Some experiments to see how the trained models generalize to other problem sizes would have been nice.", "other_comments_or_suggestions": "NA", "questions_for_authors": "1. Could you please confirm that the test set is different from the training set?\n\n2. Could you clarify whether the fine-tuning is in addition to the non-fine-tuning iterations, or\nreplacing the last few non-fine-tuning iterations?\n\n3. Do you have an idea how the approach generalizes across different sized problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZuKXJchtV4", "reviewer": "Reviewer_HsDN", "summary": "The paper studies the problem of solving combinatorial optimization problems with reinforcement learning, focusing on two key issues: diminishing reward signals that slow down learning and inefficient exploration in large solution spaces. To address this, it introduces preference optimization, a method that replaces numerical rewards with preference-based signals. It also integrates local search into training rather than post-processing, aiming to improve solution quality without extra inference cost. The approach is tested on problems like the traveling salesman etc, claiming faster convergence and better solutions compared to standard RL methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for your thoughtful comments, which help us improve our presentation clarity. Below, we address your concerns regarding terminology and methodology.\n\n---\n### **1. Regarding the Claims of Optimality**\nWe 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.\n\n---\n### **2. Rationale of PO**\n+ **Background: Reinforcement Learning for Combinatorial Optimization (RL4CO)**\nIn 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.\n+ **Key Challenge: Diminishing Rewards**\nA 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.\n+ **Introducing Preference Optimization**\nTo 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:\n> 1. Sample a batch of feasible solutions from the current policy.\n> 2. Compare them by the objective function (e.g., cost, makespan) and label the better one as \"preferred.\"\n> 3. Update the policy by *increasing the probability* of generating solutions that are \"preferred (winner)\" over others (loser) and back to Step 1.\n\nMore details are provided in Algorithm 1 in our manuscript.\n+ **Distinction from RLHF**\n1. *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.\n2. *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\n3. *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.\n\n---\n### **3. Explanation of \"Fine-Tuning\"**\nIn 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.\n\nIn 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*.\n\n**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:\n> 1. Take the policy's output $\\tau$.\n> 2. Run local search on $\\tau$ to get a slightly improved solution $\\mathrm{LS}(\\tau)$.\n> 3. Update the policy to favor $\\mathrm{LS}(\\tau)$ and go back to Step 1.\n\nThis 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.\n\n---\nWe 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.", "claims_and_evidence": "In contribution 1, the authors mentioned optimal solutions. However, the paper is entirely empirical, I believe there is no evidence showing optimality.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The paper does not include theoretical claims or proofs, except for a light proposition.", "experimental_designs_or_analyses": "The experiment section is well presented without significant issue.", "relation_to_broader_scientific_literature": "The paper adapts preference-based learning, which is currently very popular in llm era, to combinatorial optimization problems. This can potentially open new chances for preference learning outside llm.", "essential_references_not_discussed": "I am not aware of any missing references.", "other_strengths_and_weaknesses": "Strengths:\n- The paper presents experimental results on several combinatorial optimization problems, showing improvements over the baselines\n\nWeaknesses:\n- A key concern with this paper is the lack of a natural justification for applying preference learning to combinatorial optimization problems. In language models, preference learning arises organically because human feedback provides qualitative judgments on responses, making it a natural fit for reinforcement learning from human feedback. However, in COPs, there is no intrinsic notion of human preference—solutions are typically evaluated using well-defined numerical objective functions. It is unclear whether PO’s improvements stem from methodological advantages or better-tuned training procedures.", "other_comments_or_suggestions": "None", "questions_for_authors": "1. Can the authors clarify what \"fine-tuning\" refers to in detail? \n2. Can the authors provide a side-by-side comparison between the preference model used in this combinatorial optimization framework and other preference learning applications? I am particularly interested in understanding why preference models are the right tool for this setting. Unlike RLHF, where preference conflicts are often allowed, combinatorial optimization problems typically have well-defined objective functions. Given this distinction, how does preference learning in this work align with or differ from existing applications, and what makes it particularly suitable here?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This study explores the concept of qualitative preference optimization to address important challenges in applying reinforcement learning to combinatorial optimization. All reviewers recognize the novelty of the preference optimization framework and highlight the substantial improvements it offers compared to current state-of-the-art methods. For these reasons, I recommend that the paper be accepted.

Given that the authors have engaged in productive discussions with the reviewers, it would be beneficial to incorporate these insights into the final version of the paper. Key suggestions include clarifying the rationale behind the framework, explaining the choice of parameters, and discussing parameter tuning. Additionally, the authors should include detailed comparisons with other baselines, such as Compass and Poppy, and conduct more experiments using SOTA solvers to highlight the framework's flexibility.
Decision: Accept (poster)