Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems

Haohui Zhang; Xinyu Hu; Wouter van Heeswijk; Neil Yorke-Smith; Martijn Mes

cs.AIOct 22, 2026

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

Abstract

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 $\tau^{\star}$ marks the optimal solution.

\ell_{b,m}=T_{b,m}^{-\beta}\sum_{t=1}^{T_{b,m}}\log\pi_{\theta}(a_{t}\mid s_{t},x_{b}).

Algorithm 1 RWPO Training and Scale Adaptation

	Methods	$N=100$				$N=500$			$N=1{,}000$			$N=2{,}000$
	Methods	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.

Panel of Figure 2 — Figure 2: Objective gap against Compass on OP instances under different travel budgets $T$ and problem sizes.

Panel of Figure 3 — Figure 3: Step-wise policy entropy during decoding on OP instances of different sizes.

Panel of Figure 4 — Figure 4: Step-wise decoder-query soft entropy during decoding on OP instances of different sizes.

Panel of Figure 5 — 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.

\check{z}_{m,k}\leftarrow\frac{\exp(s_{m,k}/\tau)}{\sum_{j=1}^{K}\exp(s_{m,j}/\tau)}

Appendix

Algorithm 2 Soft entropy estimation for hidden representations

Category	Label	Definition and motivation
Encoder-side static instance labels	Depot distance	$d_{\mathrm{depot}}(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	$\mathbb{I}\!\left(D_{t}+d(v_{t},i)+d(i,0)\leq B\right)$ . 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	$r_{i}$ . The static prize of node $i$ . Since OP is a selective maximization problem, this is the core objective-relevant node attribute.
	Reward–distance ratio	$\rho_{i}=\frac{r_{i}}{d(v_{t},i)+\epsilon}$ . Measures reward efficiency relative to travel cost, which is critical when high reward and high travel distance conflict.
	Spatial quadrant	$q_{i}=\mathrm{Quadrant}(x_{i},y_{i})$ . 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$
	Methods	Obj. $\downarrow$	Gap	Time		Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	Gap	Time	Obj. $\downarrow$	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.

Panel of Figure 6 — 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 $\Delta$ (%)	Mean $\|\Delta\|$ (%)	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.

Panel of Figure 7 — 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 $\mathcal{H}(Z_{t})$ . These plots provide qualitative evidence of how different methods modulate uncertainty along the constructed route.

Panel of Figure 8 — 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.

Panel of Figure 9 — 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.

Panel of Figure 10 — 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.

Panel of Figure 11 — Figure 11: Step-wise mutual information between decoder-query representations and trajectory-level features during OP decoding.

Panel of Figure 12 — 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	$\beta$	$\lambda$	Best Reward @ 20 $\downarrow$	Mean Reward @ 20 $\downarrow$	Best Reward @ 50 $\downarrow$	Mean Reward @ 50 $\downarrow$	Best Reward $\downarrow$ (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	$\beta$	$\lambda$	Best Reward @ 10 $\downarrow$	Mean Reward @ 10 $\downarrow$	Best Reward @ 20 $\downarrow$	Mean Reward @ 20 $\downarrow$	Best Reward $\downarrow$ (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.

RL for Combinatorial Optimization

Reinforcement learning for combinatorial optimization learns sequential decisions and search strategies for difficult discrete problems.

See all 106 papers

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization
Aug 12, 2026Yuanyu Li, Jintao Xu, Zijiang Liu +6Combinatorial Optimization Preference Optimization
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
Leader Reward for POMO-Based Neural Combinatorial Optimization
May 22, 2024Chaoyang Wang, Pengzhi Cheng, Jingze Li +1Traveling Salesperson Problem Reward Shaping
Fudan University
AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization
Jul 30, 2026Shengda Gu, Kai Li, Xinyi Ke +3Automated Algorithm Discovery Pairwise Preference Evaluation
C2DL, Institute of Automation, Chinese Academy of Sciences · School of Artificial Intelligence, University of Chinese Academy of Sciences · Tencent AI Lab +1

Aug 12, 2026J/K move · Enter open · S save

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

Yuanyu Li, Jintao Xu, Zijiang Liu, Yongzhi Qi+5

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

Combinatorial Optimization Preference Optimization Importance Weighting RL for Combinatorial Optimization Neural Combinatorial Optimization

Open paper AskPDF arXiv

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

\mathord{.}

com, confirming practical viability at scale.

Abstract

RL for Combinatorial Optimization

Explore similar work

SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

Leader Reward for POMO-Based Neural Combinatorial Optimization

AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization