Preference-Guided Multi-Policy Optimization for Flexible Job Shop Scheduling

1 Introduction

The rise of the mass-customization paradigm has significantly increased the complexity of modern production systems. Within this paradigm, the Flexible Job Shop Scheduling Problem (FJSSP) has attracted considerable attention, as it can model contemporary production environments with diverse product types, flexible processing routes, and heterogeneous machine capabilities [Song et al., 2022]. The goal of this problem is generally to minimize the makespan, defined as the completion time of all jobs. Solving the FJSSP not only improves operational performance but also supports higherlevel decisions, including manufacturing equipment selection and production planning [Dauz`ere-P´er`es et al., 2024]. However, as one of the most complex scheduling tasks, the FJSSP is particularly difficult to solve. Therefore, developing highquality scheduling algorithms solely through human expertise has become increasingly challenging, increasing the need for automated algorithm design frameworks.

∗Corresponding author

Recently, Deep Reinforcement Learning (DRL) has emerged as a promising avenue for automating the design of algorithms for the FJSSP [Han and Yang, 2021; Feng et al., 2021; Du et al., 2022; Zeng et al., 2022; Zhao et al., 2022; Chen et al., 2022; Zhao and Deng, 2024; Yuan et al., 2024; Zhao et al., 2025; Huang et al., 2025a; Huang et al., 2025b]. These approaches typically model the sequential decision process of dispatching rules as a Markov Decision Process (MDP) and train a parameterized policy that maps states to actions using rewards obtained through repeated interactions with the environment, thereby avoiding the need for costly labeled data for supervised learning. The learned policy represents a novel dispatching rule that effectively captures the overall factory state and produces highquality solutions within short computation times.

However, despite substantial progress in policy network design, comparatively little attention has been paid to policy optimization methodologies, which still typically rely on single-policy optimization with standard Proximal Policy Optimization (PPO) [Schulman et al., 2017] or the REINFORCE [Williams, 1992]. In fact, current DRL-based methods for the FJSSP face two key challenges. First, parameterized policies struggle to sufficiently explore the solution space. Due to the combinatorially large solution space of the FJSSP, effective exploration is essential for finding high-quality solutions. Intuitively, a more diverse set of solutions increases the chance of discovering better ones. Nevertheless, existing research typically trains a single policy, which often generates less diverse solutions due to a relatively deterministic policy distribution [Xin et al., 2021]. Second, standard reward functions often fail to accurately capture the quality of policy decisions. Many DRL-based FJSSP methods use the change in the makespan lower bound before and after each decision to evaluate actions [Zhang et al., 2020; Wang et al., 2023]. However, this lower bound considers only partial information, such as precedence constraints, and overlooks complex machine conflicts among operations, leading to inaccurate estimates. Moreover, as shown in Figure 1, we find that this reward function yields zero rewards in approximately 84% of the steps in each trajectory, making it difficult to provide informative feedback during training.

This paper introduces PGMPO (Preference-Guided Multi- Policy Optimization), a novel learning framework for the FJSSP. Specifically, we aim to train multiple decision-makers rather than relying on a single policy. For this purpose, we propose a simple yet effective population-modeling approach, called bit-conditioned policies, that enables a single network to represent multiple policies using bit (multi-hot) vectors. We also introduce a multi-policy optimization algorithm that leverages preference relations among policies, derived from the objective values of their solutions, as learning signals. PGMPO effectively addresses the limitations of existing DRL-based methods in two ways. First, it encourages multiple policies to explore different promising solution subspaces, enabling them to learn diverse and specialized solution patterns and thereby improving search capability. Second, it trains the model using natural preference relations among solutions generated by different policies, avoiding reliance on reward functions that are difficult to design properly. Consequently, PGMPO enables multiple decision-makers to rapidly generate diverse and high-quality schedules for the FJSSP.

Experimental results show that PGMPO substantially improves solution diversity without any explicit diversityenforcing mechanism, while consistently enhancing model performance. Ablation studies further confirm its superiority over existing multi-policy and preference-based approaches.

2 RelatedWork

Learning-Based Approaches for FJSSP

Early DRL-based methods rely on simple state vectors or matrices, which compress information excessively and fail to reflect the structural nature of the FJSSP [Waschneck et al., 2018; Park et al., 2019]. In contrast, recent approaches [Han and Yang, 2021; Lei et al., 2022; Song et al., 2022; Wang et al., 2023; Ho et al., 2024; Zhao et al., 2025] represent states as disjunctive or heterogeneous graphs and apply Graph Neural Networks (GNNs) to effectively capture structural information, enabling richer state representations and improving model performance.

Despite these advances in network architectures, the model training methodology has received little attention. Specifically, existing methods train only a single policy, thereby limiting exploration and leading to suboptimal performance. Although entropy regularization [Kim et al., 2021] and softmax temperature strategies [Berto et al., 2025] can introduce a certain degree of stochasticity, computing entropy over the entire trajectory is computationally intractable, and additional hyperparameters require careful calibration to balance exploration and exploitation. In addition, most DRL-based methods use rewards based on loose makespan lower bounds, which often fail to provide effective decision guidance. Although DOAGNN [Zhao et al., 2025] redesigns the reward function to mitigate the impact of estimated makespan on decision evaluation, designing accurate evaluators requires substantial expert knowledge, which contradicts the goal of learning-based algorithm design: reducing dependence on human knowledge. To eliminate dense action evaluation, some studies have employed the REINFORCE algorithm, which directly uses the makespan as the reward for policy gradient [Iklassov et al., 2023; Ho et al., 2024]. However, the REINFORCE algorithm suffers from high variance, leading to unstable training and slow convergence.

Multi-Policy Optimization

Similar to our work, some studies have introduced a multipolicy paradigm to improve exploration capability for Combinatorial Optimization (CO) problems. MDAM [Xin et al., 2021] utilizes multiple decoders to learn diverse policies for vehicle routing problems, encouraging distinct strategies by maximizing the Kullback-Leibler (KL) divergence among initial action distributions. Poppy [Grinsztajn et al., 2023] introduces a "winner-takes-all" strategy, where only the topperforming policy (decoder) is updated during each iteration. However, these methods require a separate decoder for each policy, which is computationally expensive.

COMPASS [Chalumeau et al., 2023], PolyNet [Hottung et al., 2025], and MP-ASIL [Choi et al., 2025] leverage latent variables to represent multiple policies in a single model. However, latent variable conditioning is applied only at the decision-making layer, which makes it challenging to disentangle problem representations across policies. In addition, these methods update the model only with the best solution, resulting in low sample efficiency.

Preference Optimization

Preference Optimization (PO) is a prevalent strategy for aligning large language models with human preferences [Rafailov et al., 2023; Gheshlaghi Azar et al., 2024; Meng et al., 2024; Song et al., 2024; Hong et al., 2024]. Instead of relying on explicit reward signals, PO trains models using preference information, which is particularly useful when rewards are sparse or difficult to specify [Wirth et al., 2017]. This advantage of PO has recently motivated research aimed at addressing CO tasks using PO [Liao et al., 2025; Pan et al., 2025], as many CO problems, including the FJSSP, involve sparse-reward characteristics. However, existing studies focus on single-policy optimization, which fundamentally differs from PGMPO. PGMPO defines preference relations among policies, rather than among solutions sampled from the same policy, thereby encouraging distinct behavioral patterns across policies.

3 Preliminaries

3.1 Flexible Job Shop Scheduling Problem

An FJSSP instance g of size n × m consists of a set of jobs J = {J1, . . . , Jn} and a set of machines M =

{M1, . . . ,Mm}. Each job Jj ∈ J has nj operations Oj = {Oj1, . . . ,Oji, . . . ,Ojnj } that must be processed in a predefined order. Each operation Oji can be assigned to exactly one machine from its set of compatible machines, Mji ⊆ M, with a processing time of pjik ∈ R>0 on machine Mk ∈ Mji. Each machine can only process one operation at a time. Solving the FJSSP requires assigning each Oji to Mk and determining its start time Sji. The goal of the FJSSP is to minimize the makespan Cmax = maxj,i Cji, where Cji = Sji + pjik is the completion time of Oji.

3.2 Learning Neural Schedulers for FJSSP

We formulate the FJSSP as a sequential decision-making problem, where a policy autoregressively selects scheduling actions until all operations are scheduled. Each action is defined as selecting an operation-machine (Oji,Mk) pair, assigning Oji to Mk at the earliest feasible start time Sji. The policy πθ is modeled by a neural network parameterized by θ. At each step t, given g and state st, the policy outputs a distribution πθ(·|st, g) over candidate actions. An action at is then sampled from this distribution. Feasibility is guaranteed by a masking mechanism that eliminates infeasible actions (e.g., precedence or eligibility violations) during solution construction. The overall policy πθ(τ | g) that generates a solution τ = (a1, . . . , a|O|) for g is formulated as follows, where O = ⋃nj=1 Oj is the set of all operations:

4 PGMPO: Preference-GuidedMulti-Policy Optimization

This section introduces a novel learning framework, named PGMPO. We begin by explaining the multi-policy representation, followed by the training method.

4.1 Bit-Conditioned Policies

Multi-Policy Representation

To address the limitations of a single decision-maker, we aim to train C different decision-makers while sharing a single network. This is realized by conditioning the policy network on an auxiliary input Z = {zc |c = 1, 2, . . .C}, which indexes different policies as follows:

where Φ is a set of policies. In this study, we define z1 , z2 , . . . , zC using a set of unique bit vectors. This design enables a single model to efficiently represent multiple schedulers without requiring separate networks for each policy.

Multi-Policy Implementation

We describe the implementation of multiple policies using DAN [Wang et al., 2023], a state-of-the-art neural FJSSP solver, as the backbone. The proposed method is not tied to DAN and can be readily plugged into other neural architectures; see Appendix A. DAN consists of L operation message attention blocks (OMBs) and L machine message attention blocks (MMBs). Initially, the raw operation and machine features (xOji ∈ RdO and xMk ∈ RdM ) are projected into a dh-dimensional embedding space through linear layers:

where W1 ∈ Rdh×dO and W2 ∈ Rdh×dM are learnable model parameters. The initial embeddings are then updated through the OMB and MMB modules.

Each OMB layer l ≥ 1 computes operation hidden embeddings h(l) Oji for operations Oji ∈ Otu , where Otu is a set of unassigned operations at step t, through a multi-head selfattention as follows (for readability, time index t is omitted):

Similarly, each MMB layer l ≥ 1 outputs machine hidden embeddings h(l) Mk for machines Mk ∈Mu, whereMu is the set of assignable machines. The embeddings are computed using a multi-head self-attention mechanism, conditioned on the operation hidden embeddings, as follows:

Then, the network calculates a logit µ(Oji,Mk) for each candidate action (operation-machine pair) using a MultiLayer Perceptron (MLP):

where || is a horizontal concatenation operator, h(L) g = ([ 1 |Ou| ∑Oji∈Ou h(L) Oji || 1 |Mu| ∑Mk∈Mu h(L) Mk ]) is a graph feature, and h(Oji,Mk) denotes operation-machine pair features. Finally, we apply the softmax function to the logits to obtain an action distribution πθ, and an action is then sampled from this distribution. We refer readers to [Wang et al., 2023] for a more detailed procedure and feature definition.

We realize multiple policies by inserting lightweight additional layers into the backbone. The initial embeddings in Eq. (3) are used as inputs to the two blocks of the model. In this process, bit vectors are directly added to the initial hidden embeddings, as illustrated in Figure 2. The detailed procedure is as follows, while the other parts of the model remain unchanged:

where W3 ∈ Rdh×dz andW4 ∈ Rdh×dz are learnable model weights. The updated hidden embeddings in Eq. (7) are subsequently fed into the OMB and MMB to output the actions. Through this straightforward approach, we can easily obtain C sets of bit-conditioned hidden embeddings, each representing a bit-specific policy as defined in Eq. (2). We refer to this shallow network (Eq. (7)) as the bit-conditioning block.

Rather than injecting latent vectors only at the decisionmaking layer, we fuse bit vectors into the initial embedding step, enabling the model to effectively learn policy-specific latent representations throughout training. This simple design choice yields substantial performance improvements, as demonstrated in Section 5.2.

4.2 Multi-Policy Optimization Procedure

This section details a multi-policy optimization method that leverages policy preference signals. An overview of the training pipeline is shown in Figure 3.

Step A: Solution Sampling

For an instance g, the C conditioned policies (defined in Eq. (2)) can perform scheduling in parallel, generating C solutions S = {τ 1 , . . . , τ C }. At this point, we can define preference relations among policies according to the objective value of their solutions as follows:

where f(τ c , g) = -Cmax(τ c , g) denotes the negative makespan of solution τ c for notational convenience. These preference relations are then used as training signals for model optimization.

Step B: Generating Preference Pairs

In PO, model performance is highly affected by how preference pairs are defined [Zhao et al., 2016; Rafailov et al., 2023; Song et al., 2024]. One simple approach is to generate all (C2 ) pairwise comparisons among the C solutions. However, using all possible pairs for training makes it difficult to identify the best bit vector for each instance and increases training complexity due to multiple winners. Therefore, inspired by BOPO [Liao et al., 2025], we construct C-1 pairs to effectively emphasize the best-performing policy z∗ for each instance g:

Each pair compares the best solution τ ∗ from z∗ with one of the remaining solutions τ l from zl .

Step C: Model Training Using PGMPO Loss

The generated preference pairs are used to guide each policy toward learning increasingly preferred solutions. However, since f(τ, g) is non-differentiable, it cannot be directly used as a learning signal for model optimization via gradient descent. Thus, we need to transform the current preference relations into a differentiable preference objective. Starting from entropy-regularized reinforcement learning [Peters and Schaal, 2007; Rafailov et al., 2023; Meng et al., 2024; Pan et al., 2025], it is straightforward to reparameterize f(τ c , g) using the log-likelihood of a solution:

where β denotes a scaling parameter. We then leverage the probabilistic preference model to express the preference distribution pθ(τ ∗ ≻ τ l | g). This pairwise preference framework employs a mapping function σ that transforms objective

Algorithm 1 PGMPO training

value differences into preference probabilities, as follows:

In this work, we employ the Bradley-Terry (BT) model [Bradley and Terry, 1952] as the pairwise preference model. The BT model uses the sigmoid function as its mapping function σ. We also define β as f(τ l , g)/(f(τ ∗ , g) · |O|) instead of a fixed value. This adaptively controls β based on solution quality differences, eliminating extensive hyperparameter tuning and avoiding length bias [Liao et al., 2025].

Finally, the preference probabilities pθ are represented with respect to the parameterized policy πθ. We therefore formulate the following maximum likelihood objective, referred to as PGMPO loss:

Mini-batch PGMPO training is summarized in Algorithm 1.

Gradient Analysis

Here, we analyze the gradient of PGMPO loss to better understand how PGMPO guides multiple policies to learn diverse problem-solving strategies. Let u denote β(log πθ(τ ∗ | g, z∗ )-log πθ(τ l | g, zl )). Then, the gradient of LPGMPO with respect to θ can be derived as follows (the detailed derivation is provided in Appendix B):

Policy update factor

As shown in Eq. (13), PGMPO encourages the policy conditioned on z∗ to assign higher likelihood to the preferred schedule τ ∗ , while reducing the likelihood assigned to dispreferred schedules τ l under zl . As a result, each policy learns distinct preferred solution patterns for different instance sub-distributions, enabling multiple policies to explore diverse favorable regions of the search space. In addition, PGMPO leverages naturally induced preference relations from objective values as training signals, thereby eliminating the need for explicitly designed reward functions. Unlike the REINFORCE algorithm, which directly uses absolute objective values, PO leverages sigmoid-bounded relative log-likelihoods, substantially reducing gradient variance and enabling more stable training.

5 Experiments

This section presents experimental settings and evaluation results for PGMPO. All experiments are conducted on a machine with an Intel i9-14900KS CPU and a single NVIDIA GeForce RTX 4090 GPU with 24GB of memory. Our PyTorch implementation, built on DAN, is publicly available. 1

5.1 Experimental Settings

Training Settings

We train our model on instances with n × m = 10 × 5. Following the well-established SD1 procedure [Song et al., 2022], we sample the training instances from the corresponding discrete uniform distributions as follows: nj ∼ U(4, 6), |Mji| ∼ U(1, 5), and ¯ pji ∼ U(1, 20), where ¯ pji is an average processing time of operation Oji. pjik is then sampled from U (0.8¯ pji, 1.2¯ pji). We set C = 128, which corresponds to 7-dimensional bit vectors, and train the model for 4000 epochs (E) with a batch size (B) of 16. All other hyperparameters follow the original DAN setting [Wang et al., 2023]; we refer readers to the original paper for details.

Test Instances

For evaluation, we use six synthetic SD1 datasets from [Wang et al., 2023], covering sizes 10×5, 20×5, 15×10, 20×10, 30×10, and 40×10, each containing 100 instances. The test datasets follow the distribution shown in Table 1. This setup assesses both in-distribution performance and cross-size generalization.

To further validate cross-distribution generalization, we test the model without retraining on four public benchmark sets: MK [Brandimarte, 1993] and three groups from the Hurink dataset (rdata, edata, and vdata) [Hurink et al., 1994]. The MK dataset consists of 10 instances covering seven different sizes, from 10 × 6 to 20 × 15. Each Hurink group includes 40 instances, covering eight problem sizes from 10×5 to 30 × 10, with five instances per size. These groups mainly differ in the degree of machine flexibility, with an average of 2, 1.15, and 0.5m eligible machines per operation for rdata, edata, and vdata, respectively. The processing time of an operation is the same on all its eligible machines.

1 https://github.com/Ingukchoi/PGMPO

Baseline Algorithms and Evaluation Metrics

We compare PGMPO against several traditional methods and state-of-the-art DRL-based approaches as follows:

• Classic solver: CP-SAT solver from OR-Tools, using a 1800-second (s) time limit per instance.
• Priority dispatching rules (PDRs): First-In-First-Out (FIFO), Most Operations Remaining (MOR), Shortest Processing Time (SPT), and Most Work Remaining (MWKR).
• DRL-based methods: HGNN [Song et al., 2022], MCGA [Huang et al., 2025a], ME-GNN [Huang et al., 2025b], RS [Ho et al., 2024], and DAN [Wang et al., 2023].

At test time, DRL-based baselines employ a sampling strategy that generates 100 solutions using probabilistic sampling from a single policy and reports the best. Similarly, PGMPO generates one solution per policy in parallel and reports the result of the best-performing policy z∗ . For a fair comparison, during inference, PGMPO samples 100 bit vectors out of 128 to generate solutions from 100 policies.

For performance evaluation, we use three metrics: average makespan (MS), average gap (Gap), and average runtime (Time). The gap is calculated as 100 × (Cmax - C RF max )/C RF max , where C RF max denotes the makespan of the reference method.

5.2 Experimental Results

Experimental Results on Synthetic Datasets

We first evaluate PGMPO on six synthetic datasets, and the results are summarized in Table 2. From the table, we can observe that PGMPO greatly outperforms all PDRs and DRLbased methods across all instance sizes. In particular, compared with DAN, PGMPO yields statistically significant improvements on 10 × 5 and 20 × 5 datasets at the 5% level, and on the remaining four datasets at the 1% level, as confirmed by the Wilcoxon signed-rank test [Wilcoxon, 1992].

• (a) Performance improvement

(b) Solution diversity

These results show that PGMPO can unlock the potential of the backbone model with minimal modifications. Notably, on unseen large-scale instances (20×10, 30×10, and 40×10), PGMPO even achieves better solution quality than OR-Tools while requiring 109× to 375× less computation time.

Experimental Results on Benchmark Datasets

We next compare PGMPO against the best-performing PDR (MWKR) and DRL-based methods on four benchmark datasets, with results provided in Table 3. As shown in the table, PGMPO considerably surpasses all competitors, demonstrating robust performance in out-of-distribution scenarios. Concretely, with only minimal computational overhead, PGMPO reduces the performance gap of DAN by 32.8%, 11.9%, 24.6%, and 43.5% on the MK, rdata, edata, and vdata datasets, respectively.

Applicability to Other Objectives

PGMPO is not restricted to makespan minimization. To evaluate its applicability to other objectives, we also consider minimizing total tardiness. Specifically, total tardiness is computed as ΣJj∈Jmax(Cj -Dj , 0), where Cj denotes the completion time of job Jj, and Dj is its deadline. Following [Smit et al., 2026], we set Dj = ΣOji∈Oj (minMk∈Mji pjik). Using these deadlines, we train both PGMPO and DAN with PPO on 10×5 instances from SD1, and evaluate them across six problem sizes. For the PPO baseline, we adopt the lowerbound-based reward function from [Smit et al., 2026]; details of the reward design are provided in the original paper. All other experimental settings follow Section 5.1.

Figure 4a shows that PGMPO consistently outperforms DAN with PPO under the total tardiness objective. This suggests that PGMPO can be easily applied to different objectives without requiring the redesign of reward functions for each one.

Exploration Capability

Our main claim is that PGMPO effectively guides multiple policies to learn diverse solution patterns. To empirically verify this claim, we compare PGMPO and PPO with an entropy bonus (the original DAN training approach) in terms of the sum of step-wise entropy (trajectory entropy) and the unique solution ratio. From Figure 4b, we can see that PGMPO generates 100% unique solutions. Even without any diversityenforcing term, PGMPO exhibits significantly higher trajectory entropy than PPO with an entropy bonus. These results provide clear evidence that the policies learned with PGMPO exhibit distinct behavioral patterns.

Preference Model

We examine the impact of the preference model, a crucial component of PO. For comparison, we train the model using an unbounded exponential function (Exp) as the preference model σ(·) = exp(·) and report the training curves in Figure 4c, while keeping all other settings unchanged. As shown in the figure, BT matches the performance of Exp in approximately 2.5× fewer epochs. Based on this result, we use the BT function as the PGMPO preference model.

Sensitivity Analysis

We analyze the effect of C on model performance by training our model with different values of C, where C ∈ {16, 32, 64, 128}. For each model, we draw 100 bit vectors during inference. Table 4 shows the results on four benchmarks. As illustrated, training with a larger C consistently produces stronger models. These results may stem from the fact that a larger C increases the likelihood of finding a better anchor, τ ∗ , for generating preference pairs.

Ablation Study

This section presents ablation study results that analyze the impact of each component of PGMPO. For the bitconditioning block ablation (w/o BcB), we inject the bit vectors into the MLP in Eq. (6), following prior work [Chalumeau et al., 2023; Choi et al., 2025]. For the bestreference strategy ablation (w/o BR), we generate all possible (C2 ) pairs for model training. We further compare PGMPO

5.0

4.8

4.6

4.4

4.2

4.0

4.81

4.79

4.85

★

4.36

4.58

4.66

4.66

PGMPO

Poppy

w/o_BR

MP-ASIL

rdata

7.80

★

7.54

7.11

7.43

7.24

7.15

6.85

PGMPO

Poppy

w/o_BR

MP-ASIL

edata

Figure 5: Ablation study results on four benchmark datasets.

with two representative multi-policy optimization methods, Poppy [Grinsztajn et al., 2023], and MP-ASIL [Choi et al., 2025], by training DAN with each method. Finally, to assess the benefit of multi-policy modeling, we train DAN with POCO [Pan et al., 2025] and BOPO [Liao et al., 2025]. These two recent PO-based methods for CO problems optimize a single policy. We evaluate all variants on four benchmark datasets, with results shown in Figure 5.

As shown in the figure, PGMPO consistently achieves the best performance across all benchmarks. Specifically, the results clearly indicate that both the BcB and BR strategies contribute to performance improvements. Moreover, PGMPO demonstrates stronger effectiveness in multi-policy optimization than Poppy and MP-ASIL. In comparison with POCO and BOPO, PGMPO successfully learns diverse schedule generators in the multi-policy setting, leading to significant performance gains.

6 Conclusion and FutureWork

We propose PGMPO, a novel learning framework for the FJSSP that integrates multi-policy modeling with preferencebased population optimization to learn diverse and specialized scheduling strategies. Extensive experiments on synthetic and benchmark datasets demonstrate that PGMPO significantly improves the performance of existing DRL-based solvers. Moreover, PGMPO maintains its effectiveness across different objective functions, highlighting its broad applicability. Ablation studies further provide strong empirical evidence supporting the contributions of the proposed method. For future work, we aim to extend PGMPO beyond FJSSP to a broader range of realistic scheduling scenarios.

A Applicability to Other Models

To evaluate the model-agnostic nature of PGMPO, we apply it to HGNN [Song et al., 2022] as an additional backbone. Following Section 4.1, we add the projected bit embeddings to the initial operation and machine embeddings. We retain the original HGNN settings (e.g., embedding dimension), except for introducing multi-policy modeling and PO-based optimization. We train the model on the synthetic dataset SD1 [Song et al., 2022] using only 10 × 5 instances. The training parameters follow those described in Section 5.1.

Table 5 provides the evaluation results on the SD1 dataset. Despite being trained only on small-scale instances, PGMPO consistently enhances HGNN across all problem sizes, highlighting its versatility.

B Gradient of PGMPOLoss

In this section, we derive the gradient of the PGMPO loss following the procedure in [Liao et al., 2025]. Let u denote β(logπθ(τ ∗ | g, z∗ ) - logπθ(τ l | g, zl )). The gradient of LPGMPO with respect to θ can be expressed as:

The derivative of - log σ(u) can be written as:

The gradient of u with respect to θ is:

Putting these together, the total gradient of LPGMPO is obtained as follows:

Acknowledgments

This work was supported in part by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (RS-2024-00334171) and in part by the IITP(Institute of Information & Communications Technology Planning & Evaluation)-ITRC(Information Technology Research Center) grant funded by the Korea government(Ministry of Science and ICT) (IITP-2026-RS-202400437268).

w/o_BcB

POCO

BOPO

w/o_BcB

POCO

BOPO

8.00

7.75

7.50

7.25

7.00

6.75

6.50

6.25

6.00

0.60

0.55

0.50

0.45

0.40

0.35

0.30

0.25

0.57

★ 0.48

0.42

0.51 0.52

0.50

0.43

PGMPO

Poppy

w/o_BR

MP-ASIL

vdata

w/o_BcB

POCO

BOPO