Some optimization problems require choosing which items or destinations to include, as well as how to arrange them. Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems studies how a learning objective can retain the size of the difference between competing solutions.
A ranking can discard useful information
The paper focuses on selective combinatorial optimization, including the Orienteering Problem, Prize-Collecting TSP, Stochastic PCTSP and the Knapsack Problem. Unlike a tour that must serve every element, these tasks also require selecting a subset. Sampled solutions can consequently differ substantially in objective value.
Standard preference optimization reduces a comparison to a binary ranking. RWPO instead weights each pairwise preference loss using the normalized reward difference between candidate trajectories sampled from the same instance. Comparisons representing larger improvements receive greater training emphasis.
Adapt the trained policy to a different scale
The authors combine this objective with scale-specific fine-tuning and reward- and likelihood-weighted tilted sampling. These components are intended to adapt trained policies to larger or shifted instance distributions without relying on local-search post-processing.
Experiments cover all four named problem families and compare with unweighted preference optimization and policy-gradient baselines. For the Orienteering Problem, the resulting solver exceeds the mean reward of the Compass metaheuristic at scales from 100 to 2,000 nodes.
Keep the comparison tied to its problem
That Orienteering result is a mean-reward comparison over the evaluated scales. It does not establish a universally optimal solver, an advantage over every heuristic or a measured improvement for a real transport operation with additional constraints.
A reproduction should preserve how candidate pairs are sampled, how reward gaps are normalized and what adaptation or sampling budget each baseline receives. The practical contribution is a way to preserve information that a simple better-or-worse label discards. Its value for another selective optimization task depends on the objective, constraints and instance distribution being solved.
Comments