Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems
Authors: Haohui Zhang, Xinyu Hu, Wouter van Heeswijk, Neil Yorke-Smith, Martijn Mes
Organizations: University of Twente, Enschede, Netherlands · University of Bath, Bath, United Kingdom · Delft University of Technology, Delft, Netherlands
Reinforcement learning has emerged as an effective approach for combinatorial optimization, but most existing methods focus on problems such as the Travelling Salesperson Problem (TSP) in which all elements must be served. Selective combinatorial optimization problems (SCOPs), including the Orienteering Problem (OP), Prize-Collecting TSP (PCTSP), Stochastic PCTSP and Knapsack Problem (KP), additionally require selecting which elements to include. This selection creates sampled solutions with substantially different objective values, yet standard preference optimization reduces such comparisons to binary rankings and discards the magnitude of these differences. We introduce Reward-Weighted Preference Optimization (RWPO), a pairwise training objective that incorporates reward-gap information into preference learning. For candidate trajectories sampled from the same instance, RWPO weights each preference loss according to the normalized difference in their rewards, assigning greater training emphasis to comparisons that represent larger improvements in solution quality. We further combine RWPO with scale-specific fine-tuning and reward- and likelihood-weighted tilted sampling to adapt trained policies to larger and shifted instance distributions without relying on local-search post-processing. Experiments on the OP, PCTSP, Stochastic PCTSP, and KP show that RWPO consistently improves over unweighted preference optimization and policy-gradient baselines across a wide range of instance sizes. On the OP, the resulting solver exceeds the mean reward of the Compass metaheuristic at scales from 100 to 2,000 nodes. The results demonstrate that preserving reward-gap information can substantially improve preference-based learning for selective combinatorial optimization and support generalization to large-scale instances.
Figures & tables
Figure 1: Overview of the RWPO training and adaptation pipeline. The distributions below are conceptual visualizations of probability mass over solutions (with empirical validation provided in Appendix E.2.1 ). Starting from a random initial policy, RWPO learns reward-aware preferences, scale-specific fine-tuning adapts the policy to different scales ( N ), and tilted sampling further refines the policy toward high-quality solutions. Yellow stars denote solution quality, and τ⋆ marks the optimal solution.
ℓb,m=Tb,m−β∑t=1Tb,mlogπθ(at∣st,xb).
Algorithm 1 RWPO Training and Scale Adaptation
Methods
N=100
N=500
N=1,000
N=2,000
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
OP
Compass
33.133
0.00%
12m
81.123
0.00%
56s
115.690
0.00%
4.1m
166.749
0.00%
1.3m
AM-bs1024
32.686
1.35%
20m
OOD
68.592
15.45%
2.5m
79.655
31.15%
7m
95.484
42.74%
3.4m
MDAM-bs50
32.975
0.48%
22m
65.842
18.84%
3.5m
81.114
29.89%
33m
102.983
38.24%
12m
Sym-NCO
33.039
0.28%
6m
73.225
9.74%
52s
95.358
17.57%
2.7m
122.832
26.34%
40s
BQ
33.074
0.18%
1.5m
78.140
3.68%
48s
107.446
7.13%
4.3m
144.007
13.64%
3.3m
Table 1: Comparison on OP, PCTSP, SPCTSP, and KP instances across different scales.
Method
(50,200]
(200,400]
(400,2000]
(2000,5934]
POMO 100
6.03%
10.98%
41.04%
61.54%
PO 100
13.31%
41.47%
62.79%
75.99%
RWPO 50
5.71%
15.89%
34.48%
46.74%
RWPO 100
6.35%
10.77%
26.71%
35.72%
RWPO 500
14.68%
16.72%
25.96%
28.47%
RWPO 1000
13.82%
17.02%
22.92%
26.72%
Table 2: Average gap to the Compass results.
Figure 2: Objective gap against Compass on OP instances under different travel budgets T and problem sizes.
Figure 3: Step-wise policy entropy during decoding on OP instances of different sizes.
Figure 4: Step-wise decoder-query soft entropy during decoding on OP instances of different sizes.
Figure 5: Training and evaluation curves on the OP and PCTSP problem.
Appendix figures & tables14 assets
Supplementary material from the paper’s appendix.
Appendix
CVRP100
OP100
PCTSP100/SPCTSP100
KP200
Alpha
0.03
0.05
0.05
0.05
Preference Function
Exponential
BT
BT
BT
Length normalization
0
0.3
0.1
0.3
RWPO Lambda
0.5
0.5
1
0.5
Epochs
4000
1000
500
500
Epochs (FT)
200
200
100
100
Appendix
Table 3: Hyperparameter setting for POMO, PO, and RWPO.
zˇm,k←∑j=1Kexp(sm,j/τ)exp(sm,k/τ)
Appendix
Algorithm 2 Soft entropy estimation for hidden representations
Category
Label
Definition and motivation
Encoder-side static instance labels
Depot distance
ddepot(i)=d(i,0) . Measures the geometric accessibility of node i from the depot. Nodes far from the depot is costly to visit even if they have high reward.
Depot feasible
I(Dt+d(vt,i)+d(i,0)≤B) . Indicates whether node i can be visited while still allowing return to the depot. This tests whether representations encode feasibility in addition to reward attractiveness.
Node type
A categorical label distinguishing depot, selected nodes, unvisited candidates, and infeasible nodes. This tests whether the model separates structurally different roles.
Reward
ri . The static prize of node i . Since OP is a selective maximization problem, this is the core objective-relevant node attribute.
Reward–distance ratio
ρi=d(vt,i)+ϵri . Measures reward efficiency relative to travel cost, which is critical when high reward and high travel distance conflict.
Spatial quadrant
qi=Quadrant(xi,yi) . A coarse spatial-region label used to test whether encoder embeddings capture geometric clustering.
Appendix
Table 4: Task-relevant labels used for mutual-information analysis on OP. The labels cover static instance properties, dynamic decoding states, and preference-level solution-quality signals.
Methods
N=100
N=500
N=1,000
N=2,000
Obj. ↓
Gap
Time
Obj. ↓
Gap
Time
Obj. ↓
Gap
Time
Obj. ↓
Gap
Time
CVRP
LKH3 ∗
15.65
0.00%
–
37.23
0.00%
1.2m
46.40
7.91%
4m
64.90
8.15%
14m
BQ
16.09
2.79%
2.2m
OOD
38.44
3.25%
1.5m
44.17
2.72%
13m
62.59
4.30%
30m
POMO
15.75
0.66%
2.3m
44.64
19.90%
2.5m
52.97
23.18%
19m
92.34
53.87%
2.2h
PO
15.80
0.94%
4.4m
43.76
17.53%
2.9m
62.69
45.78%
20m
124.87
108.09%
2.2h
PO+LS
15.82
1.11%
4.5m
44.20
18.73%
3.0m
63.95
48.71%
21m
116.63
94.35%
2.2h
Appendix
Table 5: Comparison on instances across different scales. Best results are highlighted in bold.
Figure 6: Length-normalized likelihood–quality frontier under the base RWPO policy (1k epochs). Each point represents a sampled trajectory, plotted by its length-normalized log-likelihood under the base policy (x-axis) versus its objective value (y-axis). Solid curves indicate binned mean objectives. On N=100 , scale-specific fine-tuning (FT) and tilted sampling (TS) shift the distribution toward substantially higher-quality solutions while retaining high likelihood under the base policy, whereas local search (LS) fine-tuning induces a significantly larger distribution shift. On N=500 , the frontier flattens and trajectories tightly cluster in the high-likelihood region; nevertheless, RWPO-based adaptation successfully elevates the upper quality envelope. These dynamics confirm that FT performs a conservative probability redistribution among already-plausible trajectories—avoiding drastic shifts into low-likelihood regions—while TS effectively concentrates the probability mass of the base policy.
Fine-tuned model
Reference model
OOD scales
Mean Δ (%)
Mean ∣Δ∣ (%)
Max loss (%)
Better/equal (%)
RWPO-FT
RWPO
200, 500, 1000
-0.57
0.66
2.06
22.86
RWPO-FT-LS
RWPO-FT
200, 500, 1000
-0.28
1.40
2.68
34.29
RWPO-FT-TS
RWPO-FT
200, 500, 1000
+0.63
0.63
0.00
100.00
RWPO-FT-TS
RWPO-FT-LS
200, 500, 1000
+0.94
1.57
2.14
74.29
RWPO-FT 200
RWPO-FT
500, 1000
+6.71
6.72
0.15
96.15
RWPO-FT 500
RWPO-FT
1000
+9.42
12.83
6.35
66.67
Appendix
Table 6: Effect of fine-tuning on larger-scale generalization on OP. Relative differences are computed using mean tour revenue, where higher is better.
Figure 7: Route-level decoder-query soft entropy visualization on a representative OP instance with N=500 . Candidate nodes are shown in light blue, selected routes are shown as connected paths, and visited nodes are coloured by decoder-query soft entropy H(Zt) . These plots provide qualitative evidence of how different methods modulate uncertainty along the constructed route.
Figure 8: Route-level decoder-query soft entropy visualization on a second representative OP instance with N=500 . The comparison illustrates how entropy evolves spatially along the selected route and whether uncertainty is concentrated near local route segments or transitions between regions.
Figure 9: Mutual information between encoder/decoder representations and task-relevant labels on OP instances with N=100 . The encoder labels include static instance-level information such as depot distance, node reward, spatial quadrant, and top-rollout membership. The decoder labels include dynamic route-construction signals such as accumulated reward, budget feasibility, current distance, decoding phase, feasible actions, remaining budget, and selected count. Brighter colours indicate that the corresponding representation contains more information about the label.
Figure 10: Mutual information between encoder/decoder representations and task-relevant labels on OP instances with N=500 . Encoder-side labels describe static instance-level information, including depot distance, node reward, spatial quadrant, and top-rollout membership. Decoder-side labels describe dynamic route-construction states, including accumulated reward, budget feasibility, current distance, decoding phase, feasible actions, remaining budget, and selected count. Brighter colours indicate that the corresponding representation contains more information about the label.
Figure 11: Step-wise mutual information between decoder-query representations and trajectory-level features during OP decoding.
Figure 12: Training dynamics of PO and RWPO on SPCTSP100, KP200, and CVRP100. All three panels report the mean validation objective over all top- k starts. For SPCTSP and CVRP, lower objective values indicate better performance and for KP, vice versa. RWPO shows smoother and more stable optimization than PO, with the clearest final improvement on SPCTSP100 and CVRP100. On KP200, both methods reach similar final values, but RWPO exhibits substantially lower variance during training. These results complement the training curves in Fig. 5 .
Loss type
β
λ
Best Reward @ 20 ↓
Mean Reward @ 20 ↓
Best Reward @ 50 ↓
Mean Reward @ 50 ↓
Best Reward ↓ (epoch)
RWPO base
0.0
0.5
-16.022
-15.155
-16.117
-15.296
-16.117 (50)
RWPO base
0.2
0.5
-15.990
-15.071
-16.080
-15.214
-16.080 (50)
RWPO all pair
0.3
0.0
-15.913
-14.950
-12.256
-10.205
-15.953 (15)
RWPO all pair
0.0
0.5
-16.122
-15.336
-16.172
-15.434
-16.176 (45)
RWPO all pair
0.2
0.5
-16.096
-15.292
-16.143
-15.387
-16.160 (45)
RWPO all pair
0.3
0.5
-16.031
-15.194
-16.107
-15.332
-16.111 (49)
Appendix
Table 7: Ablation results for different loss functions and hyperparameter settings on OP50. Lower (more negative) objective values indicate better performance.
Loss type
β
λ
Best Reward @ 10 ↓
Mean Reward @ 10 ↓
Best Reward @ 20 ↓
Mean Reward @ 20 ↓
Best Reward ↓ (epoch)
RWPO base
0.0
0.5
-31.817
-30.394
-32.230
-30.872
-32.230 (19)
RWPO base
0.3
0.5
-31.710
-30.190
-32.221
-30.827
-32.221 (19)
RWPO all pair
0.3
0.0
-32.049
-30.556
-32.294
-30.824
-32.294 (19)
RWPO all pair
0.0
0.5
-32.404
-30.989
-32.644
-31.300
-32.644 (19)
RWPO all pair
0.2
0.5
-32.678
-31.353
-32.897
-31.684
-32.897 (19)
RWPO all pair
0.3
0.5
-32.569
-31.210
-32.815
-31.585
-32.815 (19)
Appendix
Table 8: Ablation results for different loss functions and hyperparameter settings. Lower (more negative) objective values indicate better performance.
Neural combinatorial optimization (NCO) relies on parallel solution sampling for training, yet existing methods fail to fully exploit the rich information latent in a co-sampled solution group. Preference-optimization methods anchor on the single best solution and discard fine-grained quality and structural signal from all other peers-a failure we term gradient signal polarization. Mean-based baselines instead weight peers uniformly, so structurally near-identical peers flood the baseline with redundant information and keep gradient variance high-a failure we term baseline redundancy. We propose SSPO (Structure-Aware Similarity-Weighted Preference Optimization), which scores all B sampled solutions jointly through a dissimilarity-weighted leave-one-out baseline: structurally distinct peers receive higher weight, resolving both failures in a single mechanism. The baseline uses zero-parameter, problem-adaptive solution embeddings built from the encoder's existing node representations. Experiments on TSP, EFL, and JSP benchmarks show consistent gains over prior best-anchor and uniform-weight baselines. A direct comparison against uniform RLOO on TSP and EFL confirms that structure-aware weighting is the primary driver of improvement. The SSPO-trained EFL policy has been deployed in a production facility-location system at JD.com, confirming practical viability at scale.
Yuanyu Li, Jintao Xu, Zijiang Liu +6
Supply Chain Tech Team Y, JD.com, Beijing, China · Department of Industrial Engineering, Tsinghua University, Beijing, China · Faculty of Engineering and Faculty of Business and Economics, The University of Hong Kong, Hong Kong, China
Deep neural networks based on reinforcement learning (RL) for solving combinatorial optimization (CO) problems are developing rapidly and have shown a tendency to approach or even outperform traditional solvers. However, existing methods overlook an important distinction: CO problems differ from other traditional problems in that they focus solely on the optimal solution provided by the model within a specific length of time, rather than considering the overall quality of all solutions generated by the model. In this paper, we propose Leader Reward and apply it during two different training phases of the Policy Optimization with Multiple Optima (POMO) model to enhance the model's ability to generate optimal solutions. This approach is applicable to a variety of CO problems, such as the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP), and the Flexible Flow Shop Problem (FFSP), but also works well with other POMO-based models or inference phase's strategies. We demonstrate that Leader Reward greatly improves the quality of the optimal solutions generated by the model. Specifically, we reduce the POMO's gap to the optimum by more than 100 times on TSP100 with almost no additional computational overhead.
Combinatorial optimization problems (COPs) underpin many real-world decisions, but their exponentially large search spaces make high-quality solutions costly to obtain. Neural combinatorial optimization (NCO) learns fast construction policies, typically with reinforcement learning (RL), while preference-based NCO improves sample efficiency by learning from relative solution quality. However, existing preference objectives combine two distinct design choices in manually specified, one-size-fits-all formulations: what learning signal to extract from each solution pair and how to weight each pair relative to the sampled set. We present AutoPref, the first LLM-guided framework for automated preference-objective discovery in NCO. AutoPref factorizes the objective into a pairwise loss program, which defines the learning signal, and a set-aware weighting program, which determines each pair's relative contribution. Their composition forms a unified programmatic objective space containing existing preference objectives as special cases. To make its search tractable, we introduce a staged conditional search strategy with behavioral gates that filter inadmissible programs before short-horizon training and evaluation. Across TSP, CVRP, FFSP, and JSSP, AutoPref consistently outperforms strong hand-designed baselines across problem scales, demonstrating the benefits and scalability of automated objective discovery for NCO.
Shengda Gu, Kai Li, Xinyi Ke +3
C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tencent AI Lab +1