BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Authors: Zijun Liao
Jinbiao Chen
Debing Wang
Zizhen Zhang
Jiahai Wang
Venue: ICML 2025 poster (2025)
Keywords: Neural Combinatorial Optimization; Preference Optimization; Machine Learning;
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We propose preference optimization with  best-anchored preference pairs and objective-guided loss, outperforming existing methods on NP-hard problems like JSP, TSP, and FJSP.

Abstract: Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We propose *Best-anchored and Objective-guided Preference Optimization (BOPO)*, a training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored preference pair construction for better explore and exploit solutions, and (2) an objective-guided pairwise loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. BOPO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.

Neural Combinatorial Optimization via Best-anchored and Objective-guiin guided Preference Optimization
BOРO:
Zijun Liao 1
Jinbiao Chen 1 Debing Wang'
Zizhen Zhang Jiahai Wang'
Abstract
obtaining high-quality solutions within reasonable time over the past decades. Nevertheless, these methods still heavily rely on expert knowledge and extensive iterative search.
Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based meth- ods suffer from low sample efficiency due to sparse rewards and underused solutions. We pro- pose Best-anchored and Objective- guiiee Prefer- ence Optimization (BOPO), training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored pref- erence pair construction for better explore and exploit solutions, and (2) an objective-guided pair- wise loss function that adaptively scales gradients via objective differences, removing reliance on reward models reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outper- forms sate-of-the-ar neural methods, reducing optimality gaps impressively with efficient infer- ence. BOPO is architecture-agnosiiic, enabling seamless integration with existing NCO models, and establishes preference optimization prin- cipled framework for combinatorial optimization.
In the emerging field of neural combinatorial optimization (NCO), deep neural models are employed to automatically learn heuristies from training data, enabling the rapid con- struction of high-quality solutions in an end-to-end fashion (Mazyavkina et al., 2021; Bengio et al., 2021; Yan et al., 2022; Kayhan & Yildiz, 2023; Zhang et al., 2023; Gar- mendia et al., 2024). Early research (Vinyals et al., 2015) adopted supervised learning (SL) to train the deep models, which required (near-) optimal solutions produced by ex- pensive specialized solvers as labels. Different from SL, reinforcement learning (RL), which does not require labels, has emerged as the mainstream training paradigm for NCO (Kool et al., 2019; Kwon et al., 2020; Zhang et al., 2020; Ho et al., 2024). However, RL encounters challenges such as sparse rewards and low sample efficiency (Kim et al., 2024). Recently, self-labeling learning (SLLL) (Corsini et al., 2024; Luo et al., 2025) was proposed to partially address these issues by sampling multiple solutions and treating the best one among them Nevertheless, SLL still faces the challenge of low sample efficiency, as all sampled solutions except the optimal one are discarded during training.
pseudo-label for model training.
To improve sample efficiency in NCO training, we lever- age multiple sampled solutions rather than focusing solely the optimal one by introducing preference optimization (Rafailov et al., 2023; Meng et al., 2024). To this end, we propose Best-anchond Optimization (BOPO), which leverages the natural prefer- ence relation among solutions according to their objective values. Our approach builds upon two fundamental obser- vations: (I) NCO models (typically generative models) can generate multiple distinct solutions for given problem in- stance, and (2) the objective value of COP solution be computed with a low cost. As shown in Figure 1, our BOPO comprises two essential components: constructing multiple preference pairs from sampled solutions and building pref- erence optimization loss. As a new training paradigm for neural combinatorial optimization, BOPO avoids expensive labels and formulation of Markov Decision Process, making
1. Introduction
Combinatorial optimization problems (COPs), such scheduling (Zhang et al., 2019; Xiong et al., 2022) and rout- ing problems (Vidal et al., 2020; Berghman et al., 2023), are widely applied in real-world scenarios and have attracted significant research attention. Most COPs are NP-hard, making them challenging to find optimal solutions. Exact methods, such as branch-and-boume algorithms, require ex- ponential computation time as the problem size increases. Consequently, heuristic methods have proven effective in
Preference and Objective-guide
"Equal contribution 'School of Computer Science and Engineer- ing, Sun Yat-sen University, China. Correspondence to: Zizhen Zhang <zhangzzh7 maail.sysu.edu.c..
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
it particularly well-suited for addressing various types of COPs.
including JSP (Zhang et al., 2020; Park al., 2021a:b; Jeon
et al., 2023; Tassel et al., 2023; Iklassov et al., 2023; Ho et al., 2024) and FJSP (Song et al., 2023; Yuan et al., 2024), Different from the above RL-based constructive methods, RI. is also employed in improvement methods for both routing (Ma et al., 2021; Wu et al., 2022; Ma et al., 2023; Kong et al., 2024) and scheduling problems (Falkner et al., 2022: Zhang et al., 2024b). Recently, SLL (Luo et al., 2025; Corsini et al., 2024) utilizes the local optimal solution dur- ing training as a pseudo-label to train an end-to-end model using cross-entropy loss, where self- improvement method (SLIM) (Corsini et al., 2024) has achieved state-of- the-art performance on JSP.
In summary, our contributions are as follows:
We propose BOPO, a novel training paradigm using preference optimization for neural combinatorial opti- mization, which enhances sample efficiency compared with the mainstream RL and recent SLL paradigms.
As the first key component of BOPO, we design a best-anchored preference pair construction method for COPs to better explore and exploit solutions.
As the second key component, we tailor novel sojective-guided preference optimization loss that in- corporates preferences quantified by objective values of COPs.
Preference Optimization. Preference optimization has been widely adopted to align large language models (LLMs) with human preferences. One of the most well-known techniques is reinforcement learning with human feedback (RLHF) (Stiennon et al., 2020; Ouyang et al., 2022), which trains a reward model using ranking learning and then aligns LLM through RL. Direct preference optimization (DPO) (Rafailov et al., 2023) offers an efficient alternative by skip- ping the reward model training phase and directly optimiz- ing LLMs using preference pairs. Building upon DPO, subsequent studies explore comparing more samples (Dong et al., 2023; Song et al., 2024) and designing more concise loss functions (Xu et al., 2023; Meng et al., 2024). Among them, simple preference optimization (SimPO) (Meng et al., 2024) has gained popularity due to its simplicity and effec- tiveness. Recent advancements in preference optimization are summarized in comprehensive survey (Xiao al., 2024a). Inspired by preference optimization, we propose best-anchored and objective-guided preference optimization (BOPO). A concurrent work (Pan et al., 2025) also applies preference optimization to COPs. However, fundamentally different from Pan et al. (2025), BOPO develops a best- anchored preference pair construction method and a novel objective-guidee preference optimization loss specially de- signed for COPs.
Experimental results on three classic problems, namely the Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP), demonstrate that BOPO outperforms state-of-thh-arr methods.
2. Related Works
Supervised Learning (SL) for NCO. SL methods utilize optimal solutions labels to train neural models with cross- entropy loss for solving COPs, such as TSP (PP(V (Vinyals et al., 2015; Milan et al., 2017) and JSP (Ingimundardottir & Runarsson, 2018). Data augmentation techniques have been exploited to enhance the performance of SL methods for routing problems (Luo al., 2023; Yao et al., 2024). Ad- ditionally, diffusion-based SL approaches (Sun & Yang, 2023; Li et al., 2023; 2024) learn to generate heatmaps for TSP. The primary limitation of SL, however, lies in the high computational cost of obtaining optimal solutions as labels, which restricts its practical applications.
Reinforcement Learning (RL)& & Self-Labeling Learning (SLL) for NCO. Label-free RL currently the mainstream training paradigm in neural combinatorial optimization. At- tention Model (Kool et al., 2019), which combines RL with Transformer (Vaswani, 2017), marks a milestone in solving routing problems. The policy optimization with multiple optima (POMO) (Kwon et al., 2020) introduces a shared baseline leveraging solution symmetry. Given its compet- itive performance and practicality, POMO has established itself as a prominent training algorithm for routing problems and has inspired numerous advancements (Grinsztajn et al., 2023; Chalumeau et al., 2023; Drakulic et al., 2023; Chen et al., 2023a;b; Xiao et al., 2024b; Goh et al., 2024; Fang et al., 2024; Zhou et al., 2024a;b; Bi et al., 2024; Zheng et al., 2024; Wang et al., 2024: Chen et al., 2025a;b). Addition- ally, RL has been widely adopted for scheduling problems,
3. Preliminaries
3.1. Neural Combinatorial Optimization (NCO)
COP aims to find a solution y that minimizes (or maximizes) the objective function g(y). In the NCO domain, neural constructive methods sequentially construct solution y in end-to-end manner for a COP instance æ. Specifically, at step {1..... [ feasible action ye is selected based on the partial solution V<r = (vi, -tt-)) with constraints enforced through masking. A model with param- eter O outputs the policy ( [x) = I To (sr /o//,, x) of solution y. Solutions can be obtained via multiple search strategies based on policy To az), including greedy and sampling rollouts.
2

---

BОРО: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Forward
Best-anchored Preference Pair Construction
Propogation Back Propogation
COP Instance
Hybrid Rollout
Uniffrrm Filtering:
Best-anchored Pairing
Solution
Solution 1
Solution
Solution
Solution 3
Solution 5
Solution
Solution
Solution
model
Solution 5
Objective-guided
Loss
Selected
Discarded
Figure I. The pipeline of best-anchored and objective-guided preforence optimization (BOPO).
Typical training paradigms include SL, RL, and SLL. label to
multiple candidate machines with shape (n k denotes the maximum number of operations in all jobs. To construct FJSP solution, action Y/ at step / represents joint selection of an operation and one of its available machines. This construction requires ly] = nkk steps.
k), where
SL utilizes the (near-) optimal solution y" train model 0 using cross-entropy loss L( wx) = - loog To (y ( (z). In RI, the REINFORCE loss (Williams,
1992) C(Telyy.0) .) = -(g - b(x)) log Th (y|<) with a baseline b(x:) is commonly used for routing problems, while the proximal policy optimization (PPO) (Schulman et al., 2017) loss ((Tolyy,))
The definitions above COPs and details of their features are provided in Appendix A.
Σ. min(r,A,,,lipp
1 e) A. is predominantly used for scheduling problems, sta(ve ())..)) denotes the ratio of current policy where r, xe- (yk ())))))
4. Methodology
0 and old policy 8', A represents the advantage estimate, and is hyperparameter. SIL, recent paradigm, selects the best among solutions sampled from current policy as a pseudo-label and applies cross-entropy loss.
4.1. Best-anchored and Objective-guided Preference Optimization (BOPO)
To improve sample efficiency, we propose a novel training paradigm, namely BOPO. Distinet from the RL and SLL training paradigms, BOPO exploits the preference relations among generated solutions according to their objective val- ues. Specifically, for a COP with the minimization objective, the explicit preference f" x) for instance and solution y is defined as the negative of the objective function:
3.2. Solution Construction for Classic COPs
The job-shop scheduling problem (JSP) entails allocating a set of n jobs across m machines with shape (n x m), wherein each job must be performed on the machines in a predefined sequence. The instance a comprises the pro- cessing time of operations and the corresponding required machines. Action Y/ is defined as operation that assigns job to the earliest available time slot on the corresponding machine and updates the job's progress. The goal is to deter- mine the job processing order on each machine to minimize the maximum completion time, known as the makespan. This construction involves |yl = nm steps.
f (y. x) = -gy)).
A preference pair, denoted as a triplet (æ, you yı), consists of an instance æ and two solutions yo and y satisfying you > yr e (" ar) ) > f" (3),
BOPO employs preference optimization loss based on such preference pairs to train the neural model parameter- ized as A. As the two critical components of BOPO, we de- velop best-anchored preference pair construction method and derive novel objective-guided preference optimization loss function specialized for COPs.
For the traveling salesman problem (TSP), the instance æ is composed of n nodes with 2-dimensional coordinates. The objective is to find tour that passes through all nodes with minimal total distance. To construct a TSP solution, an unvisited node at step is selected to be added to the current partial tour. This process requires ly = n steps.
4.2. Best-anchored Preference Pair Construction
The construction of preference pairs consists of three steps: (1) Hybrid Rollout generates diverse solutions via sampling rollout and high-quality one via greedy rollout. (2) Uni-
The flexible job-shop scheduling problem (FISP) extends JSP by considering that each operation be processed
3

---

Comparison with RL. By leveraging preference learning between the best solution and diverse inferior ones, BOPO guides the model toward promising decision trajectories and BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
form Filtering selects representative ones from the obtained solutions for efficient pairing. (3) Best-anchored Pairing
Algorithm 1 BOPO Training
1: Input: Dataset X' number of epochs E, number of training steps T, batch size D, number of obtained so- lutions B, number of filtered solutions K, and learning rate 1)
constructs preference pairs to enhance model learning.
Both diverse and high-quality solutions play vital roles in model learning. Sampling from policy ( generates diverse solutions, occasionally surpass- ing the greedy rollout solution. However, most sampled solutions are inferior to the greedy one. To leverage their complementary strengths, we propose hybrid rollout strat- egy combining both approaches. This strategy generates B solutions, including B - from sampling and one from greedy rollout. It ensures coverage of both exploratory and exploitative solutions.
Hybrid Rollout.
2: Initialize model parameter θ
for epoch to E do for step to T do
5:
2; SAMPLEINSTANCELE) Vi E (1 (1...., D)
6:
S: <- HYBRIDROLLOUTTEE; B) Vi E {1, .1...... D}
7:
C < UNIFORMFILLTERINGGS, K) Vi C [1, D)
8:
P: < BEST-ANGHORREDAARIGGGG EEE (1...., D)
9:
Compute LBOPо( a, yu: y1) using Equation (4)
10: c(0) < b Ei= |2: Eingnneee CHOPO a yo 3r)
Uniform Filtering. Constructing preference pairs using all B solutions would produce combination of (*) pairs,
11: O (d VoL(0).
12: end for
resulting in high computational cost and many low-quality pairs. Instead, we employ uniform filtering to select solu- tions to maximize representational diversity. Specifically, we select K solutions C = {3/ > ... > yk² uniformly from B sorted solutions
13: end for
ing factor derived from explicit preferences, which acts as natural curriculum. For different pairs with the same best solution yo but different suboptimal solutions yr, their preference differences should vary according to explicit pref- erences. Therefore, it is wise to introduce scaling factor to adjust the difference in the preference distribution.
= {yy > ... > } i.c.,
yv = y B/ (k-1))+1 Yk E (1...., K.. This avoids overfitting to clusters of similar solutions.
Best-anchored Pairing. Since COP solely focuses finding the optimal solution, we anchor pairs to the best so- lution to prioritize learning from high-quality examples. For K solutions {311 > > yk ). we create K - preference pairs, each combining the best solution with a suboptimal one, i.e., P = {(x, //1 yk E (2..... K}}. This design encourages learning from the optimal solution while dis- couraging learning from various suboptimal ones, being more efficient than using all (K) possible pairs.
By maximizing the log-likelihood of po (yw > y: [z), the model is encouraged to assign higher probabilities to pre- ferred solutions yoe compared with less preferred solutions yt. From Equations (1) to (3), can derive the BOPO loss function:
LBO (Te, x. you yi)
4.3. Objective-guided Preference Optimization Loss
After obtaining preference pairs, we formulate the loss func- tion of BOPO by incorporating factor derived from the objective values of COP solutions.
(
log Tea (3 (a)) log कo
(x)
loog
sifference-based scaling
g(y
|3/|
Aduppive Scaling
Avenge Log likelshood Differencee
(4)
Objective-guided Preference Optimization Loss. For policy To ( æ)) used to construct solution y, its implicit preference (3. x) defined as the average log-likelihood:
The BOPO training algorithm is presented in Algorithm 1.
Comparison with Other Losses. Our BOPO loss differs from existing preference optimization losses in several key aspects. Compared with RLHF (Stiennon et al.. 2020), it eliminates the need to train an additional reward model. Compared with DPO (Rafailov et al., 2023), it avoids using a reference model, reducing computational costs. Com- pared with SimPO (Meng et al., 2024), it incorporates a objective-guide scaling factor without requiring extra hy- perparameters, avoiding labor-intensive hyperparameter tun- ing. Detailed analyses are provided in Appendix C.
1 lvv 1
1
fo x)- log To (b(z)) y
log To (o Vet, x).
(2)
For a preference pair (x. yu yt). the preference distribution (o > y (x) is modeled using the Bradley- Terry ranking objective (Bradley& & Terry, 1952) and implicit preferences:
Po > y)(x)=
(3)
a(3(x, Bw. (f) x)- fo( x))),
where o(-) is the sigmoid function. f(x, y vI) = 2t) æ²) is a preference-basee adaptive scal-

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
discern suboptimal choices, demonstrating its advantage against RL methods. Meanwhile, recognizing that precise rewards (i.e., objective values) in RL are crucial to combina- torial optimization, BOPO introduces an objective-guide guided scaling factor beyond the standard preference optimization loss function to better distinguish preference differences.
(LA) (Lawrance, 1984), and Demirkol's (DMU) (Demirkol et al., 1998). Each benchmark contains 8 different shapes with 10 instances per shape, except LA which has 5 in- stances per shape. We generate a training dataset of 30000 instances following SLIM (Corsini et al., 2024), consisting of 6 shapes (n x m) in {10 X 10, 15 x 10, 15 x 15, 20 x 10, 20 x 15, 20 x 20) with 5000 instances per shape. During training, we generate additional 100 different instances per shape from the same shape set for validation. We employ the Adam optimizer (Kingma & Ba, 2014) with learning rate 1 = 0.0002 and train the neural model for 20 epochs. We set the solution number of hybrid rollout B = 256, the number of filtered solutions K = 16, batch size of D = 1. During inference, we adopt both greedy rollout and sam- pling rollout with B' solutions.
4.4. Characteristics of BOPO
In summary, our BOPO has the following characteristics. (I) Novel training paradigm: BOPO introduces prefer- ence optimization to neural combinatorial optimization as a new training paradigm, featuring two effective problem- awareness components: best-anchored preference pair con- struction and objective-guide preference optimization loss. (2) Architecture agnostic: BOPO is compatible with vari- ous models for different problems, achieving high sample efficiency without expensive labels while inheriting the fast inference advantage of neural models. (3) Outstanding performance: Compared with existing methods, BOPO surpasses state-of-the-ard results classic COPs, including ISP, TSP, and FISP.
Baselines. We compare BOPO with two categories of ap- proaches: non-constructive methods and constructive meth- ods. (1) Non-constructive methods, which require extensive search time, include both exact solvers and state-of-the- art neural improvement methods. We employ two exact solvers: Gurobi and Google OR Tools, both with a time limit of 3600 seconds. We also include four RL-based im- provement methods: ALSS (Falkner et al., 2022), L,2 with 500 (L2S500) and 5000 (L2S5k) solutions (Zhang et al., 2024a), and TGA500 (Zhang et al., 2024b) with 500 so- lutions. (2) Constructive methods comprise widely used traditional constructive heuristics and state-of-the-art neu- ral constructive methods, where neural methods adopt both greedy rollout and sampling rollout with B' solutions. For traditional constructive heuristies, we consider three rep- resentative traditional Priority Dispatching Rules (PDRs) (Haupt, 1989): shortest processing time (SPT), most op- erations remaining (MOR), and most work remaining (MWR). The neural constructive baselines include three RL-based methods: L2D (Zhang et al., 2020) and SchN (Park et al., 2021a), which utilize PPO with different mod- cling approaches, and CL (Iklassov et al., 2023), which incorporates curriculum learning. We also include two state- of-the-art SLL-based baselines, SLIM (Corsini et al., 2024) and SLIMMGL. where SLIMMGL uses our MGL model with SLIM's 's training algorithm. For a fair comparison, we set its batch size to 16, matching BOPO's ' setting.
5. Experimental Results
To evaluate the performance of BOPO, we compare it with state-of-the-art NCO methods and strong traditional solvers on typical COP benchmarks with various problem shapes and distributions. Performance evaluation is based the gap metric ((v)-g(y") ) x 100% between the obtained solu- tion y and known optimal solution y" where lower gap in- dicates better performance. The best results are highlighted in bold. We also report total solving time for each instance group. Experiments were conducted on a Linux system with an NVIDIA TITAN Xp GPU and an Intel(R) Xeon(R) E5- 2680 CPU. Our implementation of BOPO using PyTorch and trained models for each problem are available.'
)(y")
5.1. Job-shop Scheduling Problem
Neural Model. Each JSP instance is represented as a dis- junctive graph, standard representation for scheduling problems. For details of disjunctive graphs, see Appendix A. We employ neural model. named MGL, that combines multi-layer graph attention network (GAT) (Veličković et al., 2018) encoder for computing node embeddings with a long short-term memory (LSTM) based (Hochreiter & Schmid- huber, 1997) context-attention decoder for predicting action probabilities using both embedding and context features. The complete architecture is detailed in Appendix B.
Results on JSP Benchmarks. Comparative results on the TA and LA benchmarks are presented in Table 1. Our method achieves the lowest average optimality gap among all constructive methods on all benchmarks, with sampling rollout further enhancing its performance through the explo- ration of more solutions. Notably, BOPO even surpasses RL- based improvement methods, with the exception of L2S where BOPO achieves a comparable gap (7.5% vs. 7.4% on TA) while requiring significantly less computational time (4.8m vs. 4h on TA). Detailed runtime analysis is provided in Appendix D. Compared with SLIM, the current state-
Training& & Test. For evaluation, we use three standard JSP benchmarks: Taillard's (TA) (Taillard, 1993), Lawrence's ss hhtps///ithuh.com11777777000
5

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Table 1. Average gaps (%) of evaluated methods on JSP benchmarks. "_" indicates unavailable results from the corresponding paper.
Non constructive
Greedy Constructive
Sampling Constractive
Exact Solver
RL-based Improvement
Tradiiioal PUK
SLL
BUPO
122
D'
Shape
Curbbi OR-Tuols
L2Spp
NLS.A
TGAzz
MWR
L.3
Sch
CL
SLIMwa
SLIM
BOPO
L2D
SLIMam SLIM BOPO
SL.Mam.
SUIM
BOPO
15x15
0.1
9.3
7.7
8.0
6.2
25.8
20.5
19.2
26.0
15.3
14.3
13.1
13.8
13.6
17.1
9.0
3.8
7.2
7.1
7.2
6.5
6.3
20x15
11.6
12:2
9.9
8.3
32.9
23.6
30.0
19.4
16.5
16.1
15
14.3
23.7
10.6
11.0
9.3
9.0
10.4
20
2,9
0.7
12.4
11.5
10.0
9.0
27.8
21.7
21.8
31.6
17.2
17.3
15.3
15.2
15.1
22.6
10.9
11.1
10.0
9.8
10.0
9.0
9.1
30x15'
10.7
2.1
14.7
14.1
13.3
9.0
35.1
22.7
23.7
33.0
19.1
18.5
17.7
17.1
16.5
24.4
14.0
14.0
11.0
11.0
12.2
10.6
10.3
30"211"
13.2
2.8
17.5
164
16.4
12.6
24.9
25.2
33.6
23.7
21.5
19.3
18.5
17.3
28.4
16.1
16.3
13.4
13.3
14.9
12.7
50"155
12.2
3.0
11.0
11.0
9.5
4.6
24.1
17.3
16.8
22.4
13.9
12.2
13.4
10.1
9.8
17.1
9.3
9.2
5.5
5.8
8.2
4.9
4.9
30"
13.6
2,8
13.0
11.2
11.9
6.5
25.6
17.7
17.9
26.5
13.5
13.2
14,0
11.6
11.8
20.4
9.9
10.6
8.4
8.0
9.8
7.6
7.4
100"220"
11.0
7.9
3.0
13.6
6.7
5.9
5.8
4.9
4.8
4.4
2.1
Aug
8.4
2,0
12.2
11.3
10.7
7.4
27.5
19.7
19.5
27.1
16.1
14.9
14.5
13:4
12.9
20.8
10.4
10.7
8.4
8.2
9.6
7.8
7.5
10x
0.0
0.0
2.1
2.1
1.8
14.8
16.0
14.3
12.1
9:3
6.0
8.8
3.7
1.9
2.7
2.5
1.1
2.1
10x10
0.0
0.0
4.4
1.8
0.9
15.7
18.1
12.2
23.7
11.9
9.1
8.99
8.2
10.4
3.5
3.1
2.3
2.1
2.5
2.1
15'"5"
0.0
0.0
2.7
2.6
1.1
0.0
0.0
15x110
6.4
3.4
28.7
23.7
27.2
14.6
11.7
11.6
11.0
16.2
6.3
5.6
15x11
0.0
0.0
7.3
5.5
5.9
24.6
18.1
18.2
27.1
16.1
13.5
13.6
12:2
17.4
7.1
6.8
6.5
6.7
5.6
4.9
30
0.0
0.0
0.0
0.0
0.0
13.7
3.8
5.2
6.3
3.6
1.5
2.1
0.4
3.1
0.5
0.0
0.0
0.0
0.0
0.0
7.0
2.6
20.9
24.6
15.7
12.1
12.2
18.3
7.9
7.1
30xx10 10"
0.0
0.0
0.2
0.0
0.0
13.9
6.5
8.5
8.4
3.1
3.1
2
2.4
6.8
0.3
0.0
0.0
0.1
0.0
0.0
0.D
0.0
3.4
2.3
1.8
20.0
13.9
12.6
17.4
10.0
7.9
7.8
6.7
10.6
3.7
3.0
2.9
3.0
2.5
2.3
15
5.3
1.8
28.0
30.9
28.8
39.00
17.0
18
17.5
29.3
19.4
13.7
12.0
11.2
12.7
11.3
10.4
20
4.7
31.3
27.4
27.3
37.7
22.6
19.1
20.3
27.1
16.0
15.3
13.5
12.7
14.1
12.3
11.8
30x115'
14.2
2.5
37.4
32.3
42.0
24.1
21.8
19.1
34.0
16.5
18.4
13.9
17.5
14.0
12.9
DMI
30"-20'
16.7
4.4
34.4
34.7
31.4
10.7
25.6
25.7
25.6
33.6
20.2
19.0
17.1
16.5
17.8
15.8
15.5
10x15'
16.3
4.1
24.0
36.7
27.5
35.6
20.1
17.5
15.9
31.5
17.6
15.8
11.7
11.4
15.3
10.9
10.9
40'200"
22.5
39.
23.5
22.2
22.3
35.8
25.6
19.8
16:7
19.0
13.9
10'
14.9
3.8
24.8
35.5
28.0
56.5
18.2
15.7
14.5
32.7
21.7
15.6
11.2
11.2
15.3
10.6
10.4
30x200
22.5
4.8
30.1
37,0
30.8
39.5
25.8
22.4
25.2
36.1
15.2
20.8
15.8
16.5
20.0
15,0
15.5
Avg
||
33.77
20.3
20.0
32.5
17.3
16.5
of-the-art SLL-based constructive method, BOPO, which employs the efficient MGL model, achieves both reduced parameter count and computational overhead (detailed in Appendix B). More significantly, when evaluated against MLI using the identical model, the performance dispar- ity increases markedly across all scenarios, underscoring the fundamental advantage of the proposed training paradigm over the SLL counterpart. Furthermore, BOPO exhibits superior generalization performance on problem shapes (marked by *).
rameter configuration as POMO and INVIT, respectively. During training. the number of filtered solutions is set to K = 8. For TSP20 and TSP50, we set the hybric rollout solution number B = 128 and batch size D = 64. For TSP100, we set = 256, K 16 and D = 48 due to the memory limit. Specifically, we adopt BOPO to train INViT- 2V, but due to memory constraints, we set D 1, B = 64 (half of batch size in INViT), with K 8 and double epochs. For inference, we adopt greedy rollout with multi- ple start nodes and x8 instance augmentation (denoted as aug.), consistent with POMO.
5.2. Traveling Salesman Problem
Baselines. We assess BOPO against both traditional meth- ods and neural constructive methods. The traditional meth- ods include exact solver Concorde and Gurobi, and LKH3, powerful problem-specifie heuristic. The neural con- structive methods include POMO (Kwon et al., 2020), a widely-adopted RI-based backbone for advanced methods; DABL (Yao et al., 2024), a state-of-the-ar SL-based method with data augmentation for routing problems; INVIT (Fang et al., 2024), a sfate-of-the-art RL-based method: and SLIM (Corsini et al., 2024), a state-of-the-ar SLL-e method applied to the POMO model.
Neural Model. BOPO adopts the same model as the typical POMO (Kwon et al., 2020), comprising an encoder with 6 Transformer layers and a decoder with a multi-head atten- tion layer. To further demonstrate the universality of BOPO, it also employs the state-of-the-a INVIT (Fang et al., 2024) model.
Training& & Test. Following the NCO literature, we evalu- ate the proposed method on randomly generated instances with n = 20/50/10 1100 (denoted as TSP20/50/100), using models trained on corresponding problem shapes. Train- ing instances are generated randomly from an uniform dis- tribution. Additionally, we assess BOPO's generalization capability on the out-of-distribution TSPLIB benchmark (Reinelt, 1991), and randomly generated instances with four different distributions, including uniform, cluster, explosion, and implosion distributions. We adopt the same hyperpa-
Results on TSP. Results based on POMO are presented in Table 2 and Table 3. As shown in Table 2, BOPO out- performs other neural baselines (except DABL on TSP50) while delivering competitive solutions against traditional solvers, despite the latter requiring substantially more com- putational time. Compared with DABL which requires ex- pensive labeled optimal solutions for SL, BOPO achieves
6

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Table 2. Results on 1000 uniformly generated TSP instances.
Table 4. Average gaps (%) FISP henchmarks.
TSP20
TSP50
TSP100
Greedy Constractive
Sampling Constractive
Method
Obj
Gapp
Time.
Obj-4
Gap)
Time!
Obj-4
Gap).
Time.
Tradttional PDR
BOPO
#'=100
fr'=256
H²=512
Beachmarks
SPT MOR MWR
JINN
HG RS
BOPO
HG
RS
BOPO BOPO
BOPO
Concorde
3.83
0.00
5.69
0.00
7.75
0.00
Gurobi
3.83
0.00
7s
5.69
0.00
2m
7.75
0.00
17m
LM(e-data)
26.1
17.7
20.5
15.5
15.5
13.2
14.5
8.2
6.9
6.1
5.4
5.0
LKH3
3.83
0.00
42s
5.69
0.00
6m
7.75
0.00
25m
LA(r-baa)
28.7
14.4
17.8
12.1
112
96
84
58
4.7
4,0
36
3,4
LA(y-dana)
600
6.6
4.3
188
1.4
0.6
00.4
POMO
3.83
0.04
3.3s
5.70
0.21
6.4s
7,80
0.46
11.46
DABL
3.83
5.69
0.04
0.29
SLIM
3.85
0.22
3.3s
5.78
1.51
6.4s
8.18
5:51
11,46
Table 5. Average gaps (%) of various preference pair construction methods on the DMU benchmark.
BOPO
3.83
0.02
3.3%
5.70
0.14
6.4s
7.78
0.37
11.45
POMO (aug.)
3.83
0.00
3.6s
5.69
0.03
6.6s
7.77
0.14
18.15
DABL (aug.) )
3,83
0.00
3.6s
5.69
0.00
6.68
7.75
0.05
18.16
SLJM (aug.)
3.84
0.01
3.6s
5.70
0.15
6.6s
7.84
1.17
18.15
w/o Hybrid Rollout
wro Uniform Filtering
weo Best-anchorod Pairing
BOPO (aug.)
3,83
0.00
3.6s
5.69
0.01
6.68
7.75
0.04
18.15
Shape
Sampling Rollout
Randam
Top-XC
Bottom-K K|
Fall Permutation Paining
BOPO
20
11.5
12.0
12.8
12.5
11.9
10.9
20:20
13.0
12.5
13.3
Table 3. Generalization on TSPLIB with various problem shapes.
50x
15.2
14.0
15.9
14.6
15.5
13.3
30:20
16.7
16.4
18.5
16.7
16.6
15.8
40.13 15
12.1
11.7
13.2
11.8
11.2
11.2
100
100.5 instances)
200
E insinnes))
40:20
17.5
16.1
18.7
16.4
16.5
16.1
Method
instanss))
(16 intunce))
50x15
12.1
12.1
11.4
11.2
Obj.i
GapL. Timel
Gopl
Time.
(bbi..
Gaps. Timel
Obj.: Gaps. Time]
50x20
17.1
16.3
18.8
16.6
16.4
16.3
POMO (amg.)
6.26
2.36
0.15
6.75
3.08
0.27%
10.33
14.11 0.95
16.22
30.14
4.6
Aug
14,4
14.1
14.1
SLIM (ang.)
6.19
1.36
0.15%
6.58
5.24
0.27%
10.82
16.99
0.95
19.40
55.57
4.66
SOPO (ssgg)
6.19
1.36
0.15
6.72
2.55
0.274
10.21
10.41
0.95
15.29
22.44
4.6
(Ho et al., 2024) employing residual scheduling to remove finished operations.
comparable performance, demonstrating its superiority. No- tably, our BOPO achieves superior performance over POMO
Results on EJSP Benchmarks. As shown in Table 4, with greedy rollout, BOPO significantly outperforms most baselines, only marginally falling behind RS on LA e-data. When all methods use sampling rollout with 100 solutions, the proposed method even achieves the best performance across all cases. Notably, increasing the number of sampled solutions consistently reduces the optimality gap.
on TSP100, even with fewer training epochs (700 vs. 2000). Generalization results on TSPLIB presented in Table 3 demonstrate BOPO's s significant advantages over other neu- ral baselines when generalizing to -ft-sriiiitiitto in-
stances. Moreover, results based on INVIT's generalization to other distributions are shown in Figure 2, showing con- sistent superiority when implemented on different models.
5.4. Ablation Study
5.3. Flexible Job-shop Scheduling Problem
Higher Sample Efficiency of the BOPO Training Paradigm. We compare BOPO with two representative training paradigms: RL and SLL. For JSP, we compare BOPO with RL-based PPO and SLL-based SLIMMGL, all using the MGL model and identical training settings. For TSP, we compare BOPO with RL-based POMO and SLL- based SLIM, all using the POMO model and identical train- ing settings. The training curves in Figure 3 demonstrate our proposal's 's higher sample efficiency, achieving lower optimality gaps than both baselines with the same num- ber of training instances, with the advantage being more pronounced when training data is limited.
Neural Model. For FJSP instance represented as a dis- junctive graph, we adopt the MGL model (sce Appendix B) to compute action probabilities, which is similar to the model for JSP.
Training & Test For evaluation, we use FISP instances from the LA benchmark (Lawrance, 1984). The benchmark includes e-data, r-data, and v-data, where each operation can be allocated to 1-2 machines, 1-3 machines, and 1- m machines, respectively. Following Song et al. (2023), we generate 25000 FJSP instances with 5 different shapes: {10 x 5 x 5, 10 x 10 x 10, 15 x 10 x 10, 20 x 5 x 5, 20 x 10 x 7). For each shape, 2500 instances belong to r-data and 2500 to v-data. We set B 128, K = 16, and D during training, and employ both greedy rollout and sampling rollout with B' solutions during inference.
Effectiveness of the Best-anchored Preference Pair Con- struction Method. To validate our three-step preference pair construction method, we replace each step with a sim- pler alternative. We substitute sampling rollout for hybrid rollout, replace uniform filtering with random, top- K, or bottom- K filtering, and use full permutation pairing instead of best-anchored pairing while maintaining the same total number of pairs. As shown in Table 5, BOPO's 's perfor- mance deteriorates without (w/o) any of these components,
Baselines. For FJSP, we compare our proposal with both representative traditional PDRs and state-of-the-art RL- based constructive methods: DNN (Yuan et al., 2024) using the actor-critte framework, HG (Song et al., 2023) utilizing heterogeneous graphs for instance representation, and RS
7

---

BОРО: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
IMMT-2V PR. -onggral RL-rstained)
10.5
A-2
9.75
10.0
10.44
0.5
0:50
2:33
8.2
Buengge Cogp
0.32
0.25
9:26
6.6
1:15
9.00
0.07
1//2
6:63
5.6
6.5
6.
8.
54
10k
16
10t
3K
3t
10k
12
56
20t
Probiam
(a)
(b)
(c)
(d)
Figure Performance on TSP with different problem scales and distributions: (a) uniform, (b) cluster, (c) explosion, and (d) implosion.
RL-original denotes the results reported in the INVIT paper; RL-retrained denotes the results retrained with the same batch size as BOPO.
Validation Set
20
3,860
(RL)
(RL)
10
SLIMia (SLL)
TSP20
3.855
SLIM (SLL)
16
BO
BOPD
3.850
14
12
3.843
10
3.840
Average
3.835
3.830
120000
140000
120
140
Training Instances
Training Epochs
(a)
(b)
Figure 3. Training curves of different training paradigms for: (a) JSP and (b) TSP.
demonstrating the necessity of our design. Notably, top-K filtering leads to significantly worse performance, highlight- ing the importance of filtering worse solutions to create sufficient preference differences in pair construction. Addi- tional analyses of hybrid rollout effectiveness are provided in Appendix E.
Table 6. Average gaps (%) various functions for
||
B'
128
B' 512
Benchmark [ Smuro Coro Caoro
Ceoro SsmPo Eppo Eooro- Caoro
TA DMU
8.5
8.7
8.5
8.2
7.7
7.8
7.6
7.5
15.2
14.5
14.1
138
14.1
13.6
13.2
12.9
Superiority of the Objective-guided Preference Op- timization Loss. To evaluate our proposed loss with preference-based scaling factor, compare it with other preference optimization losses: the classic DPO loss (Cpro) (Rafailov et al., 2023). the popular SimPO loss (CsimPo) (Meng et al., 2024), and a variant of BOPO loss without the scaling factor (oDOPO-). Complete loss for- mulations are provided Appendix C. For DPO, which requires reference model prevent excessive policy devi- ation, use the old model from 10 episodes prior, similar to PPO, with the common hyperparameter setting 0.1. For SimPO, we follow their standard parameters with 8 = 2 and y 1. As shown in Table 6, BOPO achieves the best performance across all benchmarks for both B' = 128 and B' 512, with particularly significant improvements on the DMU benchmark, demonstrating the effectiveness of loss design and its preference-basee scaling factor. It is worth noting that SimPO performs poorly DMU, where
the test distribution diverges from training. This hints at potential overfitting caused by its target margin term 7.
5.5. Hyperaarameter Study
BOPO has two crucial hyperparameters: the solution num- ber of hybrid rollouts B and the number of filtered so- lutions K. We analyze their individual effects by vary- (32, 64, 128, 256, 512) and Additionally, we explore their interaction by maintaining fixed ratio B K K x B E {4 64, 8 128, 16 x 256, 32 512].
ing
{4,8, 16, 32).
16 while scaling both parameters
Effect of the Solution Number of Hybrid Rollouts. As shown in Figure 4a, increasing the number of sampled solu- tions during training, i.c., larger B, improves solution qual- ity by enhancing the probability collecting higher-quality
8

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
20000
Nemory
20000
Nemory
20000
Memory
8.15
1.500
Avaraag Cate on TA Sun car-chemmn chemaak
27310
8.
Auaanag Manragg Gal om TA Sun Co--Chamaaa Cam.aaaa
17500
15000-
GPU Momary Ursge In Tariin
15000
15000
-8.10
Momary In
12500-
0.2
12500
12500
8.05
L0000
8.3
20000
10000
4.00
9.1
7500-
7.95
8.0
-7.55
1228
(a)
(b)
(c)
Figure+ 4. GPU memory usage in training and average gap (%) on TA benchmark for: (a) varying B, (b) varying K, and (c) varying Bx K.
solutions. However, GPU memory consumption grows with B due to parallel computation, raising costs. While the performance improves significantly up to B 256, further increases yield diminishing returns despite rising compu- tational costs, making B 256 reasonable choice. We also evaluate our method on TSP20/50 with B = 20/50, the performance remains comparable to B = 128 (detailed in Appendix F). This suggests that for small-scale problems, the optimal B is low since the model can efficiently sample high-quality solutions.
than mainstream RL and recent SLL paradigms. Extensive experiments on JSP. TSP, and FISP demonstrate BOPO's su- perior performance over state-of-the-an th-trr-rrtttttt neural constructive methods, while requiring significantly less time deliver solutions competitive with traditional problem-specific it- erative heuristics. The proposed method requires neither expensive labels nor specialized design of the Markov De- cision Process, making it easy to use in practice. More importantly, establishes a general training paradigm that can be readily applied various neural models for solving different COPs.
Effect of the Number of Filtered Solutions. The number of filtered solutions K' determines the number of preference pairs, making it a critical parameter. As shown in Figure 4b, while increasing K generates more preference pairs, it also increases the similarity among solutions, as they are more likely to come from the same local region. Our experiments show that K = 16 achieves the best performance, with either larger or smaller values leading to performance degradation. This suggests that a moderate K value balances the trade-off between sufficient training data and solution diversity.
Although BOPO demonstrates superior sample efficiency compared with RL and SLL, one limitation is that it still re- quires a relatively large number of rollout solutions, similar to SLIM. This incurs moderate costs in collecting high- quality solutions for effective model learning. In future work, we will explore efficient ways to obtain high-quality solutions that facilitate model training. One promising di- rection is to leverage problem invariance and solution sym- metry to efficiently generate diverse high-quality training data. Another direction is to efficiently enhance solution quality by incorporating problem-sped heuristics during training, providing better learning signals for the model.
Effect of Interaction Between Number of Rollouts and Filtered Solutions. B and K are interdependent parameters, as B affects the uniform filtering step size B/K}, which influences the similarity between solutions. As shown in Figure 4c, we maintain a fixed step size of 16 while scal- ing B and K proportionally. The performance improves until B x K reaches 256 x 16, after which larger values yield minimal gains despite increased memory costs. This further validates our choice of B- = 256 and = 16 as recommended parameters.
A Acknowledgements
This work is supported by the National Natural Sci- ence Foundation of China (62472461) and the Guang- dong Basic and Applied Basic Research Foundation (2024A151501087), 2025A1515010129)
Impact Statement
6. Conclusion
This paper introduces research aimed at advancing machine learning, poised to facilitate industries and enhance decision- making. However, its adoption must be accompanied by careful considcration of ethical, societal, and environmental implications to ensure responsible and equitable use.
In this work, we present BOPO, preference optimization- based training paradigm for neural combinatorial optimiza- tion. By introducing best-anchored preference pair construc- tion and novel snrective-guidee pairwise loss function for COPs, our proposal achieves higher sample efficiency
9

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
References
RAFT: Reward ranked finetuning for generative founda- tion model alignment. arXiv preprint arXiv:2304.06767, 2023.
Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):405-422 421, 2021.
Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.-M. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Berghman, L., Kergosien, Y., and Billaut, J.-C. A review integrated scheduling and outbound vehicle routing problems. European Journal of Operational Research, (L(()):1-3,2022)
Falkner, J. K., Thyssens, D., Bdeir, A., and Schmidt-Thieme L. Learning to control local search for combinatorial optimization. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 361-376. Springer, 2022.
Bi, J., Ma, Y., Zhou, J., Song, W., Cao, Z., Wu, Y., and Zhang, J. Learning to handle complex constraints for vehicle routing problems. In Advances in Neural Infor- mation Processing Systems, 2024.
Fang, H., Song, Z.., Weng, P., and Ban, INVIT: A general- izable routing problem solver with invariant nested view transformer. In International Conference Machine Learning, 2024.
Bradley, R. A. and Terry, M. E. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, 39(3/4)3324 345.345, 1952.
Garmendia, A. I., Ceberio, J., and Mendiburu, A. Applicabil- ity of neural combinatorial optimization: critical view. ACM Transactions on Evolutionary Learning, 2024.
Chalumeau, F. Surana, S., Bonnet, C., Grinsztajn, N., Pre- torius, A., Laterre, A., and Barrett, T. Combinatorial optimization with policy adaptation using latent space search. In Advances in Neural Information Processing Systems, 2023.
Goh, Y. L., Cao, Z., Ma, Y., Dong, Y., Dupty, M. H., and
Lee, W. S. Hierarchical neural constructive solver for real-world tsp scenarios. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 384-895 2024.
Chen, J., Wang, J.. Zhang, Z., Cao, Z., Ye, T., and Chen, S. Efficient meta neural heuristic for multi-objective combi- natorial optimization. In Advances in Neural Information Processing Systems, 2023a.
Grinsztajn, N., Furelos-Blanco, D., Surana, S., Bonnet, C., and Barrett, T. Winner takes all: Training performant populations for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
Chen, J., Zhang, Z., Cao, Z.. Wu, Y.. Ma, Y., Ye, T., and Wang, J. Neural multi-objective combinatorial optimiza- tion with diversity enhancement. In Advances in Neural Information Processing Systems, 2023b.
Haupt, R. A survey of priority rule-based scheduling. Oper- ations Research Spektrum, 11(1):3-16, 1989.
Chen, J., Cao, Z., Wang, J., Wu, Y., Qin, H., Gong, Y.-J., and Zhang, Z. Rethinking neural multi-objective com- binatorial optimization via neat weight embedding. In International Conference Learning Representations, 2025a.
Ho, K.-H., Cheng, J.-Y,, Wu, J.-H., Chiang, F., Chen, Y.C.,,
Wu, Y.-Y,, and Wu, I.-C. Residual scheduling: new rein- forcement learning approach solving job shop schedul- ing problem. IEEE Access, 12: 12:4333444718 2024.
Chen, J., Wang, J.. Cao, Z., and Wu, Neural multi- objective combinatorial optimization via graph-image multimodal fusion. In International Conference on Learn- ing Representations, 2025b.
Hochreiter, S. and Schmidhuber, J. Long short-term memory. Neural Computation, 9(8): 1795:17351788 1997.
Iklassov, Z., Medvedev, D., Solozabal Ochoa de Retana, R., and Takac, M. On the study of curriculum learn- ing for inferring dispatching policies on the job shop scheduling. In Proceedings of the Thirty-Second Inter- national Joint Conference Artificial Intelligence, pp. 5350-5358, 2023.
Corsini, A., Porrello, A., Calderara, S., and Dell' Amico, M. Self-labeling the job shop scheduling problem. Ad- vances in Neural Information P Processing Systems, 2024.
Demirkol, E., Mehta, S., and Uzsoy, R. Benchmarks for shop scheduling problems. European Journal of Opera- lional Research, 109(1):137-141, 1998.
Ingimundardottir, H. and Runarsson, T. P. Discovering dis- patching rules from data using imitation learning: A case study for the job-shop problem. Journal of Scheduling. 21:413 428, 2018.
Dong, H., Xiong, W., Goyal, D., Zhang, Y., Chow, W., Pan, R., Diao, S., Zhang, J., Shum, K., and Zhang, T.
10

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Jeon, W., Gagrani, M., Bartan, B., Zeng, W. W., Teague, H., Zappi, P., and Lott, C. Neural DAG scheduling via one-shot priority sampling. In International Conference on Learning Representations, 2023.
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. I 11096-11107, 2021.
Kayhan, B. M. and Yildiz, G. Reinforcement learning appli- cations to machine scheduling problems: comprehen- sive literature review. Journal of Intelligent Manufactur- ing, 34(3):905-99)) 929, 2023.
Ma, Y., Cao, Z., and Chee, Y. M. Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt. In Advances in Neural Information Process- ing Systems, volume 36, pp. 49555 49555-49578, 2023.
Kim, H., Kim, M., Ahn, S., and Park, J. Symmetric re- play training: enhancing sample efficiency in deep rein- forcement learning for combinatorial optimization. In International Conference on Machine Learning. 2024.
Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, E. Reinforcement learning for combinatorial optimiza- tion: A survey. Computers Operations Research, 134: 105400, 2021.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2014.
Meng, Y., Xia, M., and Chen, D. SimPO: Simple preference optimization with reference- reward. In Advances in Neural Information Processing Systems, 2024.
Kong, D., Ma, Y., Cao, Z., Yu, T., and Xiao, J. Efficient neu- ral collaborative search for pickup and delivery problems. IEEE Transactions on Pattern Analysis and Machine In- 2024.
Milan, A., Rezatofighi, S., Garg, R., Dick, A., and Reid, I. Data-driven approximations to np-hard problems. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 31, pp. 1453-1459, 2017.
telligence, (6(12):11019-111
Kool, W., van Hoof, H., and Welling, M. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2019.
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L.,, Simens, M., Askell, A., Welinder, P., Christiano, P. F., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, volume 35, pp. 27730-277777
Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Infor- mation Processing Systems, volume 33, pp. 21188-211999 2020.
2022.
Lawrance, S. Resource constrained project scheduling: an experimental investigation of heuristic scheduling tech- niques. GSIA, Carnegie Mellon University, 1984.
Pan, M., Lin, G., Luo, Y.-W., Zhu, B., Dai, Z., Sun, L., and Yuan, C. Preference optimization for combinatorial optimization problems. In International Conference on Machine Learning, 2025.
Li, Y., Guo, J., Wang, R., and Yan, J. T2T: From distribution learning in training to gradient search in testing for combi- natorial optimization. In Advances Neural Information Processing Systems, volume 36. pp. 50020-50044 2023.
Park, J., Bakhtiyar, S., and Park, J. ScheduleNet: Learn to solve multi-agent scheduling problems with reinforce- ment learning. arXiv preprint arXiv:2106.0300 030551 2021a.
Li, Y. Guo, J., Wang, R., Zha, H., and Yan, J. Fast T2T: Op- timization consistency speeds up diffusion-based training- to-testing solving for combinatorial optimization. In Ad- vances Neural Information Processing Systems, 2024.
Park, J., Chun, J., Kim, S. H., Kim, Y., and Park, J. Learning schedule job-shop problems: representation and policy learning using graph neural network and reinforcement learning. International Journal of Production Research, 59(11):3360-3377 2022.
I Luo, F. Lin, X., Liu, F., Zhang, Q. and Wang, 7. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances in Neural Infor- mation Processing Systems, volume 36, pp. 8845-8864, 2023.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. Direct preference optimiza- tion: Your language model is secretly a reward model. Advances in Neural Information Processing Systems, volume 36, 2023.
Luo, F., Lin. X., Wu, Y.. Wang, Z. Tong, X., Yuan, M., and Zhang, Q. Boosting neural combinatorial optimization for large-scale vehicle routing problems. In International Conference on Learning Representations, 2025.
Reinelt, G. Tsplib a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. Proximal policy optimization algorithms. arXiv preprint arXiv: 17X7.07777.06347 2017.
Williams, R. Simple statistical gradient-folowinng algo- rithms for connectionist reinforcement learning. Machine learning, 8:229-256, 1992.
Song, F., B., Li, M., Yu, H., Huang, F., Li, Y., and Wang. H. Preference ranking optimization for human alignment. In Proceedings of the AAAI Conference on Artificial In- telligence, volume 38, pp. 18990-18998, 2024.
Wu, Y., Song, W., Cao, Z., Zhang, J., and Lim, A. Learn- ing improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 33(9):5057-506) 2022.
Song. W. Chen. X., Li, Q., and Cao, Z. Flexible job-shop scheduling via graph neural network and deep reinforce- ment learning. IEEE Transactions on Industrial Informat- ics, 1902)1600-1610, 2023.
Xiao, W. Wang, Z., Gan, L.,, Zhao, S., He, W., Tuan, L. A., Chen, L.,, Jiang, H., Zhao, Z.. and Wu, F. A comprehen- sive survey of datasets, theories, variants, and applica- tions in direct preference optimization. arXiv preprint arXiv:2410. 15595, 2024a.
Stiennon, N., Ouyang, L.,, Wu, J., Ziegler, D., Lowe, R., Voss, C., Radford, A., Amodei, D., and Christiano, P. F. Learning to summarize with human feedback. In Ad- vances in Neural Information Processing Systems, vol- ume 33, pp. 3008-3021, 2020.
Xiao, Y., Wang, D., Li, B., Wang, M., Wu, X., Zhou, C., and Zhou, Y. Distilling autoregressive models to obtain begh-performance
aurorrrrrrreeevvee solvers for vehicle routing problems with faster inference speed. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 20274-20283 2024b.
Sun, Z. and Yang. Y. DIFUSCO: Graph-based diffusion solvers for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 2023.
Xiong, H., Shi, S., Ren, D., and Hu, J. A survey of job shop scheduling problem: The types and models. Computers & Operations Research, 142: 105731,,,, 2022.
Taillard, E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278- 285, 1993.
Xu, J., Lee, A., Sukhbaatar, S., and Weston, J. Some things are more cringe than others: Preference opti- mization with the pairwise cringe loss. arXiv preprint arXiv:2312. 2023.
Tassel, P.. Gebser, M., and Schekotihin, K. An and reinforcement learning approach for job-shop schedul- ing problems based on constraint programming. In Pro- ceedings of the International Conference on Automated Planning and Scheduling. volume 33. pp. 614-622, 2023.
Yan, Y., Chow, A. H., Ho, C. Kuo, Y.H.,, Wu, Q. and Ying, C. Reinforcement learning for logistics and supply chain management: Methodologies, state of the art, and future opportunities. Transportation Research Part E: Logistics and Transportation Review, 162:102712, 2022.
Vaswani, A. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
Yao, S., Lin, X., Wang. J., Zhang, Q., and Wang. Z. Re- thinking supervised learning based neural combinatorial optimization for routing problem. ACM Transactions on Evolutionary Learning, 2024.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference Learning Representations, 2018.
Yuan, E., Wang, L., Cheng, S., Song, S., Fan, W., and Li, Y. Solving flexible job shop scheduling problems via deep reinforcement learning. Expert Systems with Applications, 245: 120119 2024.
Vidal, T., Laporte, G., and Matl, P. A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, 286(2):401- 416, 2020.
Zhang, C., Song, W., Cao, 7.,, Zhang, J., Tan, P. S., and Chi, X. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 1621- 1632, 2020.
Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, 2015.
Wang, C., Yu, Z., McAleer, S., Yu, T., and Yang, Y. ASP: Learn a universal neural solver! IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(06):4102- 41 14, 2024.
Zhang, C., Wu, Y., Ma. Y., Song, W., Le, Z., Cao, Z., and Zhang, J. A review on learning to solve combinatorial op- timisation problems in manufacturing. IET Collaborative Intelligent Manufacturing, 511)e 2023.
12

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Zhang. C., Cao, Z., Song, W., Wu, Y., and Zhang. J. Deep reinforcement learning guided improvement heuristic for job shop scheduling. In International Conference Learning Representations, 2024a.
Zhang, C., Cao, Z., Wu, Y., Song, W., and Sun, J. Learn- ing topological representations with bidirectional graph attention network for solving job shop scheduling prob- lem. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024b.
Zhang, J., Ding, G., Zou, Y., Qin, S., and Fu, Review of job shop scheduling research and its new perspectives under industry 4.0. Journal of intelligent manufacturing, 30: 10:1880-1830, 2019.
Zheng, Z., Zhou, C., Xialiang, T., Yuan, M., and Wang, Z. UDC: A unified neural divide-and-conuue framework for large-scale combinatorial optimization problems. In Ad- vances in Neural Information Processing Systems, 2024.
Zhou, J., Cao, Z. Wu, Y., Song, W. Ma. Y., Zhang, J., and Xu, C. MVMoE: Multi-task vehicle routing solver with mixture-of-experts. In International Conference Machine Learning, 2024a.
Zhou, J., Wu, Y., Cao, Z., Song, W. Zhang, J., and Shen, Z. Collaboration! towards robust neural methods for routing problems. In Advances in Neural Information Processing Systems, 2024b.
13

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Table 7. The state features s, E I that describes the information of an operation O, for JSP.
ID
Description
1
The processing time tt of the operation.
2
The completion of job J. up to Oj: Σ D t// I 4y-
3
The completion of job Jr after Oy: Σ oj t/t/ Ex tyr.
4-6
The 1st 2nd and 3rd quartile among processing times of operations on job J,.
7-9
The 1st 1 2nd and 3rd quartile among processing times of operations machine M,
10-12
The difference between iy and feature
13-15
The difference between ty and feature 7
Table 8. The context features e,
2 that describes the status a job J, within a partial solution y<e at step JSP.
ID
Description
C(J+) minus the completion time of machine M(a.))
2
C(J:) divided by the makespan of partial solution C(yce)..
3
C(J:) minus the average completion time of all jobs.
The difference between C(J:) and 1st, 2nd and 3rd quartile computed among the completion time of all jobs.
4-6
7
The completion time of machine Ma..) divided by the makespan of the partial solution C(y<t).
8
The completion time of machine M(.e)) minus the average completion of all machines.
The difference between the completion of Maaa) and the , and 3rd quartile computed among the completion time of all machines.
9-11
A. Formalization of Problems
A.1. Job-shop Scheduling Problems
JSP consists of set of jobs J (JI.... JnJ. a set of operations O (0),-.. Oi), and set of machines M [M1.- ..... M. Each job Jj E J is composed of a sequence of m operations (O Os.... where 4g E (1,....11) It must be completed sequentially in a strict order. Each operation O2 E O must be performed on a specific machine Mj E M continuously for ty seconds, and each machine can only process one operation at a time. For convenience, we define assignable operations at step as O,, the pending operation of job Jj at step as O(s.t)- and the corresponding machine of O(s.e) as M(,.)). Once scheduling plan is determined, the completion time C(O,) 1) of each operation O, decided accordingly, resulting in the maximum completion time C(y) max C(J:) of all jobs (i.e., makespan), where CJ,)) max C(O,) represents the completion time of job Jg. Makespan is typically the objective be minimized in JSP.
Disjunctive Graph. JSP can be represented using a disjunctive graph G = (V,A, In this graph, the node set V = {O, O2 E O} represents operations, the directed edge set A = {Ot., - Otag1 Oty Oug u E O} indicates precedence constraints between successive operations (Ot: Ot, O ), and the disjunetive (undirected) edge set E connects operations performed the same machine, A feasible solution obtained by assigning directions the undirected edges in E 10,- Og, Og O, M, = My. }. resulting in directed acyclic graph
Features of JSP. Following previous works (Zhang et al., 2020; Corsini et al., 2024), we define two types of features. The first type consists of static state features 8, assigned to each operation O, in the node set V. while the second type comprises contextual features C; based on job J; information at step l. The state features are fed into the encoder to compute embeddings for each node (operation), while the contextual features e, are combined with these embeddings to jointly contribute the prediction. Table 7 details the state features s, E 155 and Table details the contextual features c; E R.1.
A.2. Traveling Salesman Problem
Two-dimensional Euclidean TSP, which is discussed in this paper, involves n nodes, where each node i E {1,..., n) is represented by a two-dimensionna coordinate, forming a fully connected graph. The distance (ii,j) between nodes and j
14

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Table 9. The state features Syk
R
that describes the information of an operation operation-machine machine node (O,, Ma) for FJSP.
ID
Description
1
The processing time 7 of the node (O₃, Ma).
2
The average completion of job J. up to Oy: Ly t/ Eyeo, by-
3
The average completion of job J, after Oj: Σ / / / Eyeo, 'y'.
4-6
The 1", 2nd and 3rd quartile among processing times of operations on job Jr.
7-9
The 1st 1",,2nd 2nd and 3rd quartile among processing times of operations machine Mg.
10-12
The difference between i, and feature 4-6.
13-15
The difference between 1 and feature 7-9.
is calculated by their coordinates. The objective of TSP is to find the shortest Hamiltonian cycle ( =E== Clys,,1+1), where y = (y1...., Vn, v1), Uj E (I,...,m) n visits each node exactly once and returns to the starting node.
Features of TSP. Similar to Kool et al. (2019), the input of TSP consists of n nodes with 2-dimensional features. At each decoding step, the context embedding h. defined as the concatenation of embeddings from the first and last visited nodes. The coordinates of each instance are sampled from uniform distribution on [0, 1]2.
A.3. Flexible Job-shop Scheduling Problem
FISP, a variant of JSP, better reflects world scenarios. Unlike JSP, FISP allows each operation O, E O to choose from multiple candidate machines Mj S M, rather than being restricted to a specific one. We redefine the processing time of O₃ in machine Mg M, as tjk. and denote the t, J ElMil Ezk the average processing time of operation Oj. This flexibility significantly increases decision-makiin complexity, leading to denser disjunctive graph.
Disjunctive Graph for FJSP. To simplify the disjunctive graph for FISP, introduce operation-machine nodes, where operation is decomposed into multiple operation-machine nodes. Each operation-machine node is simi- lar to a node in JSP and can be treated as an action. Specifically. the disjunctive graph is formalized as G (V, A, E, U), where V- = {(O,, M₂) Io E O,Ms E {M,} represents the set of all operation-machine pairs, A = ((O1g) MR) + (Otas4yy ME) Otg. OuGIn E O; E MMyy Mg E MM denotes the directed edge set, E = ,O,,, Mp) + (Oy, Mx) 10,, 55 E O; E M, My] denotes the disjunctive (undirected) edge set, and veeaaien-machine
U U= [[0,, M&) + (z) Og E,; ; My M, connects all operation machine nodes belonging to the same operation.
Features of FJSP. Similar to JSP, we define two types of features for FJSP. To accommodate operation-machine nodes used in FISP, we split the context features into job context features c/' and machine context features c₁ where cf represents the context features of job J, and .M represents the context features of machine Mg. Similarly, the static state features sj > Sjk are modified from describing operation Oj to describing the operation- machine nodes (Oj, Mx). Table details the state features 8jk E 15 and Table 10 details the contextual features e/, of E RR5
B. Neural Model for Scheduling Problems
For scheduling problems, we design an efficient neural model named MGL., which combines multi-layer graph attention network (GAT) (Veličković et al., 2018) encoder with long short-term memory (LSTM) based (Hochreiter & Schmidhuber, 1997) context attention decoder.
B.1. Neural Model for JSP
Encoder. Since the disjunctive graph contains two types of edges: directed edges related to jobs, and disjunctive edges (undirected) related to machines, we treat as a two-layer graph to better distinguish between these two edge types, i.e., Gjos= = AV, Gmac = E), and = Gjob U Gmae- One layer contains only directed edges, while the other contains only disjunctive edges. To process this structure, we introduce multi-layer GAT as the encoder, where each layer can be
15

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Table 10. The job context features c/ E R² and the machine context features ct R that describe the status of a job J4 and machine Mr within a partial solution yer at step for JSP.
Job ID
Description
C(J:) divided by the makespan of partial solution C(yes). (JJs) minus the average completion time of all jobs.
2
The difference between C(J:) and the 1",,"", and 3rd quartile computed among the completion
3-5
time of all jobs.
Machine ID
Description
The completion time machine Mr divided by makespan the partial solution C(yct))
The completion time of machine M2 minus the average completion of all machines.
The difference between the completion of M& and the 1st 2nd and 3rd quartile computed among completion time of all machines.
3-5
considered a standard 2-head GAT. The computation for an N-layer GAT is follows:
GAT (x, GI...., Gx) (o(GAT (z, G1)) -.. GN))].
In our encoder, we stack two 2-layer GAT as follows to embed e, of operation Oy:
ej = [s (GAT second (1 [sy (GAT) first Gjob: Gmac))) Gjob, Gmae))]
Decoder. At step 4, we use the embedding c of the operation selected at step / - as input to the LSTM, which computes the query qi as follows:
q LN(LSTM(a(e,... Wi))) W2.
For each operation Oj, concatenate context feature c, of its job J, with the embedding e, to obtain the key ktj as follows:
ki. = lo(c: W3) |e,] W4.
Finally, the query qi attends to the keys kos of assignable operations, computing the attention to generate the policy distribution for action selection:
exp(q: kTg)) * (O,lt) Eyeo, explee kTz))
B.2. Neural Model for FJSP
Encoder for FJSP. We also employ the MGL model for FJSP. With the introduction of operation-machinn nodes and the operation-related edge set U, we redefine Gopr UV, and G Gjob U Gope U Gmac- The following describes the embedding Ejk of a 3-layer GAT to node (O,,Ma)
ejk- = [8,k]] a (GAT3 ( (lsooooo(sssssl(((AT first
/irst(Ssks (8yks Gÿod, Gmacy Gopr))], Gjobs Gmacy Gopr) ))]-
Decoder for FJSP. For maehate node (O,, Ma) of job Jr, the key kijj is modified as:
ki,jAA (a(c'' Ws) M Wallle,x] Ws.
Due to the fact that query q. is independent of eperation-machine nodes, the policy distribution for nodes (Oj, M₁) is:
explq: -.TS.))
x(OO,,MM)lt Eo,so,,,MeM, exple: TT k))
16

---

BOРO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
Table 11. MGL's efficiency compared with SLIM's model.
Memory Usage (MB)
Training Time (ms)
Inference Time (ms)
Model
Parameters
During Training
per Instance
per Instance
MGL
35KK
262.19
13955.9
800.04
GAT-MHA
376.96K (+25.73K)
71 (27x)
1785.7 (+27.9%)
851.81 (+6.4%)
B.3. Comparison with Neural Model Used in SLIM
Our MGL is compared with the neural model used in SLIM (Corsini al., 2024), denoted GAT-MHA. The main distinction between these models lies in their decoders, significantly impacting memory consumption and computational efficiency, as analyzed in Table 11. All data are collected from 15 x 15 instance, with the solution size B set to 256.
The multi-head attention (MHA) module GAT-MHA introduces additional weight matrices that contribute to its higher parameter count. In contrast, LSTM in MGL achieves efficiency through recurrent weight sharing. GAT-MHA requires 32.8% more memory during forward propagation than MGL. Moreover, GAT-MHA's backward pass memory usage is 27x higher than MGL's, primarily due MHA's gradient computation needs: Intermediate Activation Storage and Gradient Scaling with Heads. For the former, MHA must retain attention score matrices and head-specific outputs during forward pass for gradient computation, while LSTM's recurrent nature minimizes intermediate storage. For the latter, MHA's memory overhead scales linearly with the number of attention heads, as gradients for each head's parameters are stored separately.
C. Comparison with Other Loss Functions
C.1. Formulations of Loss Functions
In SLIM (Corsini et al., 2024), the locally optimal solution yo is treated pseudo-label, and the model trained using cross-entropy loss. The loss function of SLIM can be expressed as::
ESLIM (To x. yo) = yo
log no (3olz)).
(5)
This formulation effectively maximizes the average log- likeliiddoood of the locally optimal solution. In contrast to SLIM, our method incorporates suboptimal solutions into the loss function, effectively minimizing the average log-likellng likelihood of these suboptimal candidates. This approach improves sample efficiency and accelerates the convergence of model training.
DPO (Rafailov et al., 2023) employs a reference model Tref, analogous to RLHF (Stiennon et al., 2020), to regularize the trained model against excessive deviation from the initial policy. The DPO loss function is defined as:
(3 3 log
To (yt (x) Tea Teer (3)
CPPo(TT Tiet, x, Mio y1) - log log
(6)
Te Ter (Y x))
where 3 controls the strength of regularization toward the reference model Reat In contrast, method eliminates the dependency on an explicit reference model, simplifying the training framework while avoiding potential distributional shift issues.
To simplify the training phase and align the training goal with the generation goal, SimPO (Meng et al., 2024) climinates the reference model and simplifies the loss function as follows:
le, You, yn) -olog log
3 yy
log To (3 (2r)
33 1/
log mo (yr (y)(2z) -2)
where 3 is constant that controls the scaling of the difference, and is target margin term. In contrast, BOPO uses an adaptive objective gap factor to scale the differences, instead of relying on additional hyperparameters.
Considering the similarity between the BOPO loss and that of policy gradients, we additionally analyze the loss function in the REINFORCE algorithm (Kwon et al., 2020) here:
( y) -g(()) -b) log (y
(8)
17

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
where is baseline distinguish positive negative optimization signals for each sample y. In POMO, 6-00,b=33 E, dw) the average objective of B samples. Note that, both BOPO and REINFORCE the exact reward (objective) optimal policy. However, BOPO directly distinguishes optimization signals based exact preferences, and the strength of the optimization signal correlates with the difference in log-lik log-liielhhood, requiring the model to maximize the probabilities gap between yoe and y)-
C.2. Gradient Analysis
Let denote the argument of the sigmoid in Equation (4):
g(v)
log (D xx)
log no To (2))2)))
g
|/
The gradient of LEOPO with respect to 0 is:
TLBOPO
V e LOOOO
Voz.
0z
Derivative of loog (2) becomes:
OLROO
= -(1-o(z))
Oz
Gradient of with respect to 0:
(31)) (
1
Vo log (o(wla))))
Vo log mo((illt))
ywol
1y1
Combining these, the total gradient becomes:
V CoOO = ((v))
(1 (1-0(z))
Vo log no (B)l))
Ve log xo (yo (x)
g(yw)
3/1
yu
Confidence Weight
Adaptive Scaling
Direction of Policy Update
Adaptive Scaling a(an)
give) For minimization problems, g(yw) < g(9)). so g(aw)
a(w) 1. This amplifies the gradient magnitude
for pairs where y significantly worse than you prioritizing updates that correct large suboptimalities.
Confidence Weight (=)) As the policy becomes more confident in preferring yo over yı (a(z) - 1), the gradient diminishes. This prevents overfitting to already well-separated pairs.
Normalization by lyl: The normalization by/ ensures that solutions of different lengths contribute equally to the gradient. Without this, longer solutions (e.g., JSP schedules with more operations) would dominate updates.
Direction of Update: The gradient increases the likelihood of you (since Vo log To((w)l)) is added) and decreases the likelihood of y (since Ve log Ne (z) is subtracted).
Compared with DPO and SimPO, their gradients are as follows:
VoLoro -3. (1- (1-o(d)
Ve log (U))) V log (Bw (x)
Confidence Woight
Direction of Policy Update
1
VoLsimPO = (1 (1))(s))
Ve log To (3)
Vo log To (x)
y/1
Coufidenee Weight
Direction Policy Update
18

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
where
Toe (Y Tea Yw
Th 3/ x)) Tief yi az)
1
( Trefl yr
[z) (
y (z) y Tee y a 3
To
?
d=
log
log
B
log
log
a:)
1/
represent the confidence weight in DPO and SimPO.
DPO and SimPO rely on fixed hyperparameters (i.e., 3 and 7) to control the gradient magnitude, requiring manual tuning and lacking dynamic adaptability. Furthermore, DPO does not perform length normalization on the fog-likelihood calculations, which may lead to instability in scenarios with variable-length outputs. In contrast, BOPO enhances robustness across diverse scenarios through adaptive scaling factors and length normalization, thereby reducing dependence the hyperparameter.
D. Runtime Analysis for JSP
additionally provide the solving time in Table 12, which an important aspect some scheduling scenarios.
Our model, MGL, achieves significantly lower solving time compared to all non-construetive methods while delivering performance closing 1.2S5x. When compared RL-based greedy constructive methods, MGL maintains competitive solving time even when sampling 512 solutions. Notably, MGL's solving time does not increase significantly with larger B', clear distinction from GAT-MHA, the model proposed in SLIM. This is because GAT-MHA relies on MHA decoder, which has a computational complexity of Onn²), ) a drawback that becomes particularly pronounced as B' grows.
E. Further Analysis of Hybrid Rollout
To investigate the impact of introducing greedy solution through hybrid rollout, trained the model using both hybrid rollout and pure sampling approaches under different numbers of generated solutions B. The comparison results shown
Table 12, The average solving time (s) algorithms on the TA benchmark.
Non-constructive
Greedy Constructive
B'=128
B'=512
Shape
OR-Tools
L22500
TGAs00
L2S5a
PDRs
L.D
SchN
CL.
SLIM
BOPO
SLIM
BOPO
15x15
462
12.6
92.2
0.00
0.39
3.5
0.72
0.75
20x15
2880
10.1
14.6
102
0.00
0.60
6.6
1.10
0.84
0.80
1.07
0.96
20x20
3600
10.9
17.5
114
0.00
0.72
11
1.39
1.11
1.06
1.37
1.23
30x15
3600
12.7
17.2
120
0.01
0.95
17.1
1.49
1.24
1.19
1.83
1.44
30x20
3600
14
19.3
0.01
1.41
28.3
1.59
2.42
1.91
50x15
3600
16.2
23.9
168
0.01
1.81
52.5
2.82
2.19
1.99
4.06
2.60
50x20
3600
22.8
24.4
228
0.02
3.00
96
3.93
2.91
2.63
5.41
3.44
100x20
3600
50.2
42.0
504
0.19
9.39
444
9.58
7.85
5.31
20.05
7.96
0.7
0.6
4.7
0.5
Groedy So Used
42
0.4
Prozuanicy 0
Groedd So Best
Offiree
1/26
6.925
02
90
B--44
8-8 Namber Rotoot Soljkon
B-: 256 P.
23
63
60
160
Thaining Ebochs
(b)
Figure 5. Analysis of Hybrid Rollout. (a) Average gap (%) on TA benchmark of different rollout methods with varying numbers of generated solutions B. (b) Participation and optimality of greedy solution during training.
19

---

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
in Figure 5a. Evidently, hybrid rollout not only improves model performance but also significantly reduces the dependency on B. Notably, the model achieves competitive results even with smaller generated sizes B. For instance, B 32 with hybrid rollout performs similarly to B 64 with hybrid rollout and is only 0.4 points behind B = 512 with hybrid rollout. In contrast, B = 32 without hybrid rollout performs poorly. with gap of 0.8 compared to B = 512 without hybrid rollout. Notably, hybrid rollout enables a generated solutions size of 256 to match the performance of a generated solutions size of 512 without hybrid rollout, demonstrating equivalent efficacy with reduced computational demand.
As illustrated in Figure 5b, to investigate how greedy solutions enhance training efficacy, we trained the model on TSP20 with hyperparameters
128 and K systematically tracking two metrics per epoch:
The frequency of greedy solutions selected for preference pair construction (theoretical random selection probability: 1/16);
The frequency of greedy solutions being identified as the best solution.
The rising selection frequency of greedy solutions demonstrates their growing dominance in training. Given that greedy solutions exhibit the highest log-likelihood among all candidates, their participation delivers stronger gradient signals, accelerating model convergence. The synchronized increase in greedy solutions being recognized as the best solution, and the decrease of difference between the frequencies mentioned above validates their critical role in improving solution set quality. This inherently addresses the limitation of sampling rollout, where suboptimal exploration often fails to capture high-quality candidates.
These demonstrate that introducing a greedy solution via hybrid rollout has an effect akin to increasing the solution generated size B during training, but without incurring additional computational costs. This is particularly significant because large-scale and complex COPs often require substantial resources. Hybrid rollout offers memory-efficcee alternative while maintaining high performance.
F. Additional Experiments.
To further investigate the impact of on different problem types, we evaluate our method on TSP20/50 with B = 20/50 (denoted as BOPO-). ). As shown in Table 13, when sampling the same number of solutions as POMO, the performance of the model remains comparable to B 128. This suggests that for small-scale or simple problems, the optimal B is low, as the model can efficiently sample high-quality solutions with fewer times.
BOPO's s advantage primarily stems from pairwise preference learning, rather than simply being an RL variant with the proposed filtering method. To demonstrate this point, we compare BOPO with a POMO variant employing our Hybrid Rollout and Uniform Filtering (denoted as POMO*). The key difference lies the loss: while BOPO uses pairwise loss, POMO+ calculates a standard POMO loss based on the filtered K solutions, as lacks the pairwise mechanism. Results in Table 13 show that POMO inferior to BOPO, demonstrating the effectiveness of the preference learning BOPO, Moreover, POMO + is even inferior to POMO, underscoring that the filtering method is tightly adapted to BOPO and may not be applicable to general RL methods.
Table 13. Average gaps (%) on generated TSP instances.
Methods
TSP20
TSP50
POMO POMO+ +
0.002
0.042
0.005
0.081
BOPO BOPO
0.000
0.009
0.000
0.009
20


Reviews:
[{"review_id": "0UOagg11y7", "reviewer": "Reviewer_upvg", "summary": "This paper proposes POCO (Preference Optimization for Combinatorial Optimization), a method that integrates preference learning into reinforcement learning (RL) to address combinatorial optimization problems. Additionally, the authors introduce Hybrid Rollout, Uniform Filtering, and Best-anchored Pairing as methods for constructing preference pairs used in preference learning. The proposed approach is evaluated and tested on combinatorial optimization tasks including the Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP).", "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": "Thank you for your valuable comments.\n\n>**Q1:** it remains unclear precisely how sample efficiency is enhanced.\n\nWe have analyzed POCO's higher sample efficiency in Section 5.4. We further precisely demonstrate significant improvements in sample efficiency by supplementing quantitative results. Note that we retrained models on TSP20/50 with $B=20/50$ & $K=8$, ensuring a fair comparison.\n\nPOCO achieves faster convergence than RL when using the same numbers of samples and gradient steps:\n\n1. POCO achieves approximately $48\\times$, $20\\times$, and $3\\times$ higher training efficiency than RL methods on JSP, TSP20, and TSP50, respectively. Specifically, POCO requires only 2500 training steps, 10 epochs, and 70 epochs to match the gaps achieved by RL methods, which take 120000 steps, 200 epochs, and 200 epochs, respectively.\n2. POCO achieves significantly superior solution quality within the same number of training epochs. On JSP, POCO attains 0.76%/4.12% lower gaps than RL/SLIM in just 5 epochs. For TSP20/50, POCO achieves 0.0076%/0.0687% lower gaps than POMO in 100 epochs.\n\n>**Q2:** it remains unclear what specific advantages can be achieved by increasing the values of $B$ and $K$.\n\nThe advantages of increasing $B$ and $K$ under the same time and computational resources can be seen in Section 5.5.\n\n1. Increasing $B$ improves performance while increasing memory usage. As shown in Figure 4(a), the gap reduces from 8.3% to 7.9% as $B$ increases from 32 to 512, plateauing at $B=256$. Beyond this point, increasing $B$ provides negligible improvement, as sampling more from $\\pi$ rarely yields better solutions. This result demostrates our reasonable setting of $B=256$.\n2. As presented in Figures 4(b-c), the recommended value for $K$ is 16, and it should scale proportionally with $B$. \n\n>**Q3:** comparison with recent SOTA studies.\n\nWe would like to emphasize that POCO, like POMO, is a general and fundamental training algorithm. POMO serves as the backbone for most SOTA methods, so naturally, the backbone of these SOTA methods can also be replaced with the superior POCO. To further showcase this potential, we conducted additional experiments on InViT, which has demonstrated superior performance over LEHD and Pointerformer in its paper.\n\nSpecifically, we adopt POCO to train InViT, but due to memory constraints, we set the batch size to 64 for InViT (also $B$ for InViT+POCO), with $K=8$. We retrained InViT with identical parameters. Results in Table A shows that InViT+POCO outperformes InViT on various distributions and larger-scale problems.\n\n**Table A: Gaps (%) on TSP**\nMethod|U-1k|U-5k|U-10k|C-1k|C-5k|C-10k\n-|-|-|-|-|-|-\nInViT-2V|6.49|8.21|6.61|10.01|10.36|9.23\nInViT-2V+POCO|**5.98**|**7.67**|**6.00**|**9.58**|**9.81**|**9.18**\n\nMethod|E-1k|E-5k|E-10k|I-1k|I-5k|I-10k\n-|-|-|-|-|-|-\nInViT-2V|9.61|11.58|9.72|7.95|9.42|7.39\nInViT-2V+POCO|**8.67**|**10.59**|**8.94**|**7.38**|**8.88**|**7.04**\n\nDistribution: Uniform (U), Cluster (C), Explosion (E), Implosion (I). The numbers behind represent the problem scales. Note that we report the results both for 300 epochs due to extended training time. Full results for 800 epochs will be provided in the subsequent discussion phase.\n\n>**Q4:** Due to this discrepancy in the number of solutions generated by each method per instance, it is difficult to consider this experiment as a fair comparison.\n\nFor a fair comparison, we retrained models on TSP20/50 with $B=20/50$ & $K=8$, ensuring it samples the same number of solutions during training as POMO.\n\nDespite reducing $B$, POCO maintains performance comparable to $B=128$, with superior solution quality (see Table B), higher training efficiency (see response to Q1), and better generalization (see response to Q3).\n\n**Table B: Gaps (%) on TSP.**\nMethod|TSP20|TSP50\n-|-|-\nPOMO (aug)|0.0016|0.0418\nPOCO (aug)|**0.0000**|**0.0085**\n\n>**Q5:** the performance gap is too small to be considered a meaningful difference.\n\n1. For well-optimized small-scale or easy problems, such as TSP20, achieving further improvement, e.g., 0.0013% gap to the optimal solution, is quite challenging. However, the improvements become more pronounced for larger-scale or harder problems: (1) On larger-scale TSP100, POCO's gap 0.04% vs POMO's 0.14% (see Table 2); (2) On the harder JSP, POCO's gap 12.9% vs $SLIM_{MGL}$'s 16.5% on DMU benchmark (see Table 1); (3) On much larger-scale unseen TSPLIB instances with 500-1000 nodes, POCO's gap 22.44% vs POMO's 30.14% (see Table 3).\n2. In the NCO field, such improvements are considered significant, as evidenced by literature from top AI conferences [1,2]. In [1], among 12 TSP cases, 10 cases (83%) show improvements over the second-best neural method smaller than 0.1%. Similarly, in [2], 6 out of 12 TSP cases (50%) have similar improvement levels.\n\n[1] Collaboration! Towards Robust Neural Methods for Routing Problems. NeurIPS 2024.\n\n[2] Learning encodings for constructive neural combinatorial optimization needs to regret. AAAI 2024.", "claims_and_evidence": "This paper proposes a method for training combinatorial optimization (CO) solver models using preference learning and introduces specific methods for constructing preference pairs required for this approach. However, the rationale behind applying preference learning to train CO solver models is insufficiently explained. Although the introduction states that preference learning was introduced to improve sample efficiency, it remains unclear precisely how sample efficiency is enhanced by this method. Moreover, similar to most existing Neural CO studies, all three experiments performed in this paper utilized *generated* training datasets.\n\nExperiments were conducted on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP). However, the experimental setup for TSP appears inadequate. Further details regarding this issue are provided in the 'Experimental Designs Or Analyses' section.", "methods_and_evaluation_criteria": "As mentioned earlier, the benefits of applying preference learning proposed in this paper are not clearly demonstrated. \n\nFurthermore, in the preference pair construction method, rollouts are conducted B times, but only B/K of these rollouts are utilized for model updates, discarding the remaining data. This approach inevitably results in a loss of training resources due to discarding rollout data by a factor of K. Given the same amount of time and computational resources, it remains unclear what specific advantages can be achieved by increasing the values of B and K.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Regarding the experiments conducted on TSP instances, there exist several recent studies (e.g., LEHD, Pointerformer, InViT) that have improved upon POMO (Kwon et al., 2020) for solving the TSP. Although SLIM is a recently proposed method included in this paper's comparisons, it performs worse than POMO in most experimental settings presented in Tables 2 and 3. Therefore, to better demonstrate the effectiveness of the proposed method, it would be beneficial to compare it against these recent state-of-the-art studies that have shown superior performance over POMO. Additionally, in the uniformly generated TSP instance experiments presented in Table 2, the node sizes used are relatively small compared to those evaluated in recent studies. It is recommended to perform comparisons on larger-scale instances.\n\nIn Figure 3, POMO generates 20 solutions per instance, whereas POCO generates 128 solutions per instance. Due to this discrepancy in the number of solutions generated by each method per instance, it is difficult to consider this experiment as a fair comparison. Furthermore, the performance gap between POMO and POCO reported in Figure 3 is only 0.0013, which is too small to be considered a meaningful difference.\n\n\nLuo, Fu, et al. \"Neural combinatorial optimization with heavy decoder: Toward large scale generalization.\" NeurIPS 2023.  \nJin, Yan, et al. \"Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem.\" AAAI 2023.  \nFang, Han, et al. \"Invit: A generalizable routing problem solver with invariant nested view transformer.\" ICML 2024.", "relation_to_broader_scientific_literature": "None", "essential_references_not_discussed": "Luo, Fu, et al. \"Neural combinatorial optimization with heavy decoder: Toward large scale generalization.\" NeurIPS 2023.  \nJin, Yan, et al. \"Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem.\" AAAI 2023.  \nFang, Han, et al. \"Invit: A generalizable routing problem solver with invariant nested view transformer.\" ICML 2024.", "other_strengths_and_weaknesses": "None", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "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": "qpywh7ENeg", "reviewer": "Reviewer_xAAW", "summary": "The introduction of POCO, a training paradigm for NCO to enhance sample efficiency. This is accomplished by  (1) design a preference pair construction method for improving exploration and exploitation, (2) gradual building of the loss function. This is evaluated on three problems Job shop scheduling, TSP, and FJTSP.\n\n## Update after rebuttal: \nThe authors have addressed most of my comments. I would like to thank them for the efforts. I will increase my score to 3.", "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 thank the reviewer for the encouraging feedback and incisive questions.\n\n>**Q1:** Concorde is not used for TSP. \n\nWe have included Concorde's results from POMO [1] and added them to the table C for comparison. Concorde, LKH3, and Gurobi are traditional iterative search-based algorithms with identical performance (0.0% gap), differing only in solving time. \n\nLKH3, being a strong heuristic solver, can offer fast approximate solutions for large-scale problems and even delivery the optimal solutions for small-scale problems. Including Concorde's results does not alter our existing conclusions, as we have already incorporated other strong heuristic methods.\n\n**Table C: Gaps (%) on TSP Instances** \n\n|Method|TSP20 Gap|TSP20 Time|TSP50 Gap|TSP50 Time|TSP100 Gap| TSP100 Time|\n|-|-|-|-|-|-|-|\n|Concorde|0.00|5m|0.00|13m|0.00|1h|\n|Gurobi|0.00|42s|0.00|6m|0.00|25m|\n|LKH3|0.00|7s|0.00| 2m|0.00|17m|\n|POMO (aug.)|0.00|3.6s|0.03|6.6s|0.14| 18.1s|\n|SLIM (aug.)|0.01| 3.6s|0.15|6.6s|1.17|18.1s|\n|POCO (aug.)|**0.00**|3.6s|**0.01**|6.6s|**0.04**|18.1s|\n\n[1] POMO: Policy optimization with multiple optima for reinforcement learning. NeurIPS 2020.\n\n>**Q2:** Subpar results when compared to SOTA heuristic Concorde. In general, what is the advantage of using this NCO when compared to LKH3 and Concorde?\n\nUnlike traditional iterative search-based methods, NCO without expert knowledge balances solving time and performance, so its contribution should not be evaluated solely based on performance.\n\n* **A key advantage of NCO is its ability to achieve near-optimal solutions with significantly shorter solving times, especially for large-scale problems**：\n    * For TSP100, POCO achieves a near-optimal gap of 0.04% while reducing solving time dramatically (17m for LKH3 vs. 18s for POCO).\n    * On large-scale JSP problems (TA 100x20), NCO demonstrates clear advantages. Exact algorithms like Gurobi and OR-Tools, within 1 hour (see Table 12 in Appendix D), achieve 11% and 3.9% gap (see Table 1), respectively, which are inferior to the 1.4% gap POCO achieves in just 8 seconds (see Table 12 and Table 1, respectively).\n* **Another advantage of NCO is that it does not require expert knowledge to design complex algorithms**, thereby expanding its applicability to a wider range of scenarios.\n\n>**Q3:** How about TSP-1000? Can the authors test their trained model on instances where the ILP fails?\n\nTo further showcase the potential of POCO on large-scale problems, we conducted additional experiments on InViT [2] framework, which is designed to solve large-scale problems where the ILP fails. Note that POMO is not designed for large-scale problems, but we have also demonstrated the superiority of POCO with generalization experiments on TSPLIB (see Table 3). \n\nMain results generalizing to various distributions and larger-scales are shown in Table D. InViT+POCO outperformes InViT on all distributions and scales, underscoring its superiority. At these scales, Gurobi and LKH3 require 30 minutes to 1.5 days to solve, whereas NCO needs only up to approximately 10 minutes.\n\n**Table D: Gaps (%) Across Different Distributions and Scales**\n\n|Method|U-1k|U-5k|U-10k|C-1k|C-5k|C-10k|\n|-|-|-|-|-|-|-|\n|InViT-2V|6.49|8.21|6.61|10.01|10.36|9.23|\n|InViT-2V+POCO|**5.98**|**7.67**|**6.00**|**9.58**|**9.81**|**9.18**|\n\n|Method|E-1k|E-5k|E-10k|I-1k|I-5k|I-10k|\n|-|-|-|-|-|-|-|\n|InViT-2V|9.61|11.58|9.72|7.95|9.42|7.39|\n|InViT-2V+POCO|**8.67**|**10.59**|**8.94**|**7.38**|**8.88**|**7.04**|\n\n\"U\": Uniform, \"C\": Cluster, \"E\": Explosion, \"I\": Implosion distributions. The numbers behind represent the problem scales. Note that we report the results both for 300 epochs due to extended training time. Full results for 800 epochs will be provided in the subsequent discussion phase.\n\n[2] InViT: A generalizable routing problem solver with invariant nested view transformer. ICML 2024.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes. They are mostly sound.", "relation_to_broader_scientific_literature": "The authors provide a new training paradigm for NCO that is architecture-agnostic.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "## Strengthens: \n- No need for labels for the training graphs. \n- OOD evaluation at inference. \n- POCO evaluation with different backbone models. \n\n## Weaknesses: \n\n-\tSubpar results when compared to SOTA heuristic Concorde. Results are only good when compared to other NCO methods. Concorde is not used for TSP. Is there a reason? In general, what is the advantage of using this NCO when compared to LKH3 and Concorde?\n\n-\tHow about TSP-1000? \n\n-\tScalability results are missing for TSP? can the authors test their trained model on instances where the ILP fails?", "other_comments_or_suggestions": "See Other Strengths And Weaknesses.", "questions_for_authors": "See Other Strengths And Weaknesses.", "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": "rQLBZLQF8Z", "reviewer": "Reviewer_jKth", "summary": "This paper first introduce the concept of Preference Optimization to the area of NCO. Generally, as the expected advantage of PO, POCO demonstrates instance-efficiency comparing to RL and SLL. (As shown in Figure 2 and Figure 3)\n\n## update after rebuttal:\n\nThis is a novel and inspiring paper, so I keep my positive rating.", "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": "Thank you for your valuable comments.\n\n>**Q1:** I recommend to also includes SL-based POMO as baseline.\n\nWe have added results from the SL-based method [1] to the table E. Since all methods use the same model, differences stem from training algorithms. \n\n**POCO achieves comparable or better performance than SL-based methods without requiring labeled optimal solutions, further demonstrating the superiority of POCO**. Results show that on TSP20, SL-based and POCO perform identically. On TSP50, SL-based slightly outperforms POCO (0.001% vs 0.01%). However, on TSP100, POCO is superior (0.04% vs 0.05%).\n\n**Table E: Gaps (%) on TSP Instances** \nMethod|TSP20|TSP50|TSP100\n-|-|-|-\nPOMO(aug)|0.00|0.03|0.14\nSLIM(aug)|0.01|0.15|1.17\nSL(aug)|**0.00**|**0.00**|0.05\nPOCO(aug)|**0.00**|0.01|**0.04**\n\n[1] Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem. ACM Transactions on Evolutionary Learning, 2024.\n\n>**Q2:** the preparation stage for POCO can be time-consuming compared to RL-based methods. Can you provide a preparation time for each instance?\n\nThis problem is mainly caused by us sampling more solutions (larger $B$). We provide the following clarification:\n\n1. **POCO does not necessarily require sampling a large number of solutions to maintain performance**. As noted in our response to Reviewer upvg Q4, POCO still achieved superior performance when sampling the same number of solutions as POMO, although we recommend an best value of 256 for $B$.\n2. **Training time does not significantly increase with larger** $B$. Table F shows the approximate training time per epoch for different problem scales and $B$. For small-scale problems, the training time has hardly changed. For larger problems like TSP100, even if $B$ is increased by 2.5 times, the training time only increases by 1.6 times.\n\n**Table F: Training Time Per Epoch** \n$B$|TSP20|TSP50|TSP100\n-|-|-|-|\n20/50/100|2m30s|4m30s|12m\n128|2m30s|5m|-\n256|-|-|20m\n\n>**Q3:** As far as I know, there is not much work using PPO in NCO training, so is this part of the description a bit redundant?\n\nWe acknowledge that REINFORCE is the dominant training algorithm for routing problems. However, as noted in our paper, PPO is a typical method for scheduling problems [2-4]. We remain open to further refinements to enhance clarity and relevance.\n\n[2] Learning to dispatch for job shop scheduling via deep reinforcement learning. NeurIPS 2020. \n\n[3] Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 2023. \n\n[4] Solving flexible job shop scheduling problems via deep reinforcement learning. Expert Systems with Applications, 2024.\n\n>**Q4:** Will using raw scaling factors lose stability on different problems? Can rank-based factors or factors after normalization be better?\n\nThis is a very interesting question. We agree this is a valuable direction for future research.\n\n1. We observed that scaling factors vary across different problems, with distributions differing significantly. For some challenging problems, such as those where objective values have large or minimal gaps, raw scaling factors might fail. This is an important area for further exploration.\n2. Rank-based factors offer stability in any scenario but may not accurately reflect true solution differences, potentially leading to suboptimal performance. Normalized factors, however, seem promising, with techniques like normalization, clipping, or compression functions offering potential improvements.\n\n>**Q5:** Can POCO generalize to NCO models other than POMO on TSP?\n\nWe would like to emphasize that POCO, like POMO, is a general and fundamental training algorithm. POMO serves as the backbone for most SOTA methods, so naturally, the backbone of these SOTA methods can also be replaced with the superior POCO. To further showcase this potential, we conducted additional experiments on InViT [5].\n\nSpecifically, we adopt POCO to train InViT, but due to memory constraints, we set the batch size to 64 for InViT (also $B$ for InViT+POCO), with $K=8$. We retrained InViT with identical parameters. Results in Table G shows that InViT+POCO outperformes InViT on various distributions and larger-scale problems.\n\n**Table G: Gaps (%) on TSP**\nMethod|U-1k|U-5k|U-10k|C-1k|C-5k|C-10k\n-|-|-|-|-|-|-\nInViT-2V|6.49|8.21|6.61|10.01|10.36|9.23\nInViT-2V+POCO|**5.98**|**7.67**|**6.00**|**9.58**|**9.81**|**9.18**\n\nMethod|E-1k|E-5k|E-10k|I-1k|I-5k|I-10k\n-|-|-|-|-|-|-\nInViT-2V|9.61|11.58|9.72|7.95|9.42|7.39\nInViT-2V+POCO|**8.67**|**10.59**|**8.94**|**7.38**|**8.88**|**7.04**\n\nDistribution: Uniform (U), Cluster (C), Explosion (E), Implosion (I). The numbers behind represent the problem scales. Note that we report the results both for 300 epochs due to extended training time. Full results for 800 epochs will be provided in the subsequent discussion phase.\n\n[5] InViT: A generalizable routing problem solver with invariant nested view transformer. ICML 2024.", "claims_and_evidence": "Some claims in the paragraph ``Comparison with Other Losses.`` are not clear. The reference model is actually a constraint for LLM, I do not agree that this can be a characteristic of the POCO loss. Instead, the Adaptive Scaling part can distinguish DPO and the POCO loss. POCO loss excludes the target reward margin term in SimPO but this is not discussed in that paragraph.", "methods_and_evaluation_criteria": "Generally okay.", "theoretical_claims": "This paper do not contain theoretical claims.", "experimental_designs_or_analyses": "I recommend to also includes SL-based POMO as baseline. [1]\n\n[1] Yao S, Lin X, Wang J, et al. Rethinking Supervised Learning based Neural Combinatorial Optimization for Routing Problem[J]. ACM Transactions on Evolutionary Learning, 2024.", "relation_to_broader_scientific_literature": "This paper discuss a new training paradigm for NCO, i.e., Preference Optimization. POCO shows advantages in intance-efficiency and final performance.", "essential_references_not_discussed": "This paper has included prior related findings.", "other_strengths_and_weaknesses": "Strength:\n\n1. Introducing Preference Optimization to NCO is novel.\n\n2. Compared to RL-based and SLL-based baselines, POCO exhibits instance-efficiency in training.\n﻿\nWeakness:\n\nGenerally, there are no major weaknesses in this paper. One minor weakness of this paper is that the preparation stage for POCO (i.e., ``Preference Pair Construction``) can be time-consuming compared to RL-based methods. So POCO can hardly be extended to train on large-scale CO.", "other_comments_or_suggestions": "Please refer to Questions For Authors.", "questions_for_authors": "1. Section 3.1. Neural Combinatorial Optimization (NCO) provides a detailed introduction to RL methods. As far as I know, there is not much work using PPO in NCO training, so is this part of the description a bit redundant?\n\n2. The design of Adaptive Scaling is reasonable, but my concern is that the distribution of objective function values is often different over different CO problems. Will using raw scaling factors lose stability on different problems? Can rank-based factors or factors after normalization be better?\n\n3. Can you provide a rough preparation time (used for ``Preference Pair Construction``) for each instance?\n\n4. Can POCO generalize to NCO models other than POMO on TSP? It would be great if POCO could still demonstrate its performance on other models.", "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": "beGqdijXfx", "reviewer": "Reviewer_Madu", "summary": "The paper proposes to use (a specific variant of) preference-based RL losses instead of regular reward-based policy gradients for combinatorial optimization problems.\n\nThe primary finding is that this Preference Optimization for Combinatorial Optimization (POCO) loss improves sample complexity and asymptotic performance over standard (PPO) and specialized baselines (SLIM), over multiple different combinatorial optimization problems.\n\nThis is a surprising result, because the original reason preference losses are used is due to lack of precise rewards (e.g. with human feedback). I would've thought that for combinatorial optimization which indeed has precise rewards, using preferences (which is imprecise) can be worse.", "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": "Thank you for your valuable comments.\n\n>**Q1:** I would've thought that for combinatorial optimization which indeed has precise rewards, using preferences (which is imprecise) can be worse.\n\nWe agree that precise rewards are also crucial to combinatorial optimization. **Meanwhile, we would like to clarify that POCO, unlike standard preference optimization techniques used in LLM, incorporates the precise objective value (i.e., reward in RL) into our loss function.** As highlighted in our submission, this key contribution stems from our insight into the critical role of precise rewards in combinatorial optimization.\n\nSpecifically, the proposed POCO loss is $\\log\\sigma\\left(\\frac{g(y_l)}{g(y_w)}\\left(\\frac{\\log\\pi_\\theta(y_w|x)}{|y_w|}-\\frac{\\log\\pi_\\theta(y_l|x)}{|y_l|}\\right)\\right)$, where $\\frac{g(y_l)}{g(y_w)}$ is a scaling factor derived from precise objective values for the best solution and the inferior one.\n\nThe results in Table 6 and discussions in Section 5.4 demonstrate the effectiveness of incorporating precise objective values into the POCO loss, e.g., POCO reduces the gap to 12.9% on the DMU benchmark, outperforming its variant without this scaling factor (gap 13.2%).\n\n\n>**Q2:** I'm inclined to think of possible subtle numeric effects which led to this result.\n\nWhile we acknowledge that numerical artifacts can sometimes confound comparisons, we emphasize that our core contribution, a novel preference-based training framework, is not attributable solely to such effects.\n\n* **By leveraging preference learning between the best solution and diverse inferior ones, POCO guides the model toward promising decision trajectories and discern suboptimal choices, demonstrating its clear advantage against RL methods.** POCO exhibits significantly superior solution quality and higher training efficiency ($48\\times$ speedup for JSP), as shown in the response to Reviewer upvg Q5 and Q1, respectively. Note that POMO, a REINFORCE-based method, uses terminal rewards and computes baselines via means, eliminating value-head estimation and minimizing numeric effect risks.\n    * Here is a closer look at policy gradient. POMO uses a baseline to distinguish positive/negative optimization signals for each sample:\n$(g(y) - b) \\nabla_\\theta \\log \\pi_{\\theta}(y|x).$\nIn contrast, POCO directly distinguishes based on exact preferences:\n$\\frac{g(y_l)}{g(y_w)}\\frac{(1-\\sigma(z))}{|y_w|}\\nabla_\\theta\\log\\pi_\\theta(y_w|x)-\\frac{g(y_l)}{g(y_w)}\\frac{(1-\\sigma(z))}{|y_l|}\\nabla_\\theta \\log\\pi_\\theta(y_l|x),$\nwhere $z=\\frac{g(y_l)}{g(y_w)}\\left(\\frac{1}{|y_w|}\\log \\pi_\\theta(y_w|x)-\\frac{1}{|y_l|}\\log\\pi_\\theta(y_l|x)\\right)$. The optimization signal strength correlates with the log-likelihood difference $z$, requiring the model to maximize the probabilities gap between $y_w$ and $y_l$. This results in faster convergence and better performance.\n* **POCO's advantage primarily stems from pairwise preference learning, rather than simply being a RL variant with the proposed filtering method.** To demonstrate this point, we compare POCO with a POMO variant employing our Hybrid Rollout and Uniform Filtering (denoted as POMO+). The key difference lies in the loss: while POCO uses pairwise loss, POMO+ calculates a standard POMO loss based on the filtered $K$ solutions, as it lacks the pairwise mechanism. Results in Table H show that POMO+ is inferior to POCO, demonstrating the effectiveness of the preference learning of POCO. Moreover, POMO+ is even inferior to POMO, underscoring that the filtering method is tightly adapted to POCO and may not be applicable to general RL methods.\n\nBased on the above two points, we would like to reiterate that POCO's unique advantages stem from its preference learning and the two tightly coupled designs (the pair construction method and the loss function based on objective values), rather than simply relying on subtle numeric effects.\n\n**Table H: Gaps (%) on TSP**\nMethod|TSP20|TSP50\n-|-|-\nPOMO|0.002|0.042\nPOMO+|0.005|0.081\nPOCO|**0.000**|**0.009**\n\n>**Q3:** Mainly Section C, to verify what types of RL losses are being used. \n\nWe have stated typical RL losses in Section 3.1, including REINFORCE for routing problems and PPO for scheduling problems. According to your suggestions, we will add a detailed description and analysis of these RL losses to Appendix C.\n\n>**Q4:** The current presentation of the paper makes the contribution incremental and not fundamental ...\n\nOur main contribution is a novel training framework, distinctly different from traditional RL, that not only improves performance but also convergence speed. We will thoroughly proofread the paper to highlight this core contribution.\n\n>**Q5:** ..., the gains are fairly incremental, and overall combinatorial optimization has become very saturated.\n\nIn the NCO field, such improvements are considered significant. POCO delivers substantial performance gains and faster convergence, as demonstrated in our responses to Reviewer upvg Q5 and Q1, respectively.", "claims_and_evidence": "Because of how unintuitive the results are (i.e. even with precise rewards, preference-based loss leads to better outcomes), I'm inclined to think of possible subtle numeric effects which led to this result. For example:\n  * Reward normalization can be tricky with exact rewards, and training the value-head to predict advantages typically can cause problems if not careful.\n  * For $n$ objective evaluations, preference optimization uses ${n \\choose 2}$ pairs, while policy gradient would only use $n$, so preference optimization performs more gradient updates due to more data. The paper proposes filtering methods (uniform filtering and best-anchored pairing) to reduce the data size and only focus on diverse or high quality solutions. \n    * If this is crucial to improving performance, I'm wondering if there would've also been a policy gradient variant (e.g. add a numeric transformation to upweight large rewards) that would've equally done well.\n\nI'm not asking the authors to ablate these (since this could require a lot of work), but I'm just stating that the devil's in the details.", "methods_and_evaluation_criteria": "Yes, the paper evaluates over multiple different combinatorial optimization problems (Job-shop scheduling problem, Traveling Salesman Problem, Flexible Job-shop scheduling problem), with multiple baselines. \n\nI do think the presentation could be improved however (too many abbreviations and large tables, and too many random details in the text). It's possible to improve the experimental presentation pictorially using bars or graphs.\n\nOverall it's not a priority IMO to show outperformance over very domain-specific combinatorial optimization baselines - what is a priority, like I mentioned earlier, is the conclusion that preference-based RL beats exact-reward RL.", "theoretical_claims": "Not applicable, no theory.", "experimental_designs_or_analyses": "Please see my \"Claims and Evidence\" part. I'm sure that the authors did a solid job on running multiple experiments and baselines, but experimental RL requires a lot of small little subtle details which can strongly affect results.", "relation_to_broader_scientific_literature": "It is interesting to see how some of the RL-HF literature (preference-based learning) can be adopted to classic RL (e.g. combinatorial optimization). Originally, preference-based losses were only created to deal with the noisiness of human feedback, but I would've never expected it to do better than traditional policy gradients for exact rewards.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "# Strengths\nUsing RL-HF techniques like DPO for exact-reward problems, outside of human feedback, is an important topic for linking the field of LLM alignment with traditional RL, and I applaud this paper in doing so.\n\n# Weaknesses\nThe current presentation of the paper makes the contribution incremental and not fundamental - i.e. due to lots of random details and abbreviations stuffed into the writing, the overall read can look like \"We tried a different tweak and got slightly better results in a very specific domain\". I would strongly encourage the authors to avoid this style of writing.", "other_comments_or_suggestions": "I'm not particularly for or against this paper - i.e. I'm pretty lukewarm about it, because:\n\n1. When it comes to the actual combinatorial optimization improvements, the gains are fairly incremental, and overall combinatorial optimization has become very saturated.\n\n2. The result that preference-based optimization outperforms exact rewards, _is_ interesting, but the paper isn't investigating this fundamental result in-so-much-as applying it for combinatorial optimization", "questions_for_authors": "See my concerns 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": {}}]

Author rebuttal:

Meta-review: This paper focuses on neural combinatorial optimization and addresses the issue of sparse rewards. The paper's contributions are to use multiple solutions and provide the information about ordering of the solutions. The empirical evaluation shows clear improvement. All the reviewers viewed the contributions of the paper as significant enough to warrant acceptance.
Decision: Accept (poster)