acceptodds
Under review as a conference paper at ICLR 2027

Beyond Decoupled Decisions: Jointly Learning Label Extension and Column Selection in Column Generation for Vehicle Routing Problems

Abstract

Column generation (CG) is a powerful framework for large-scale routing optimization that avoids exhaustive enumeration by iteratively solving master and pricing problems. However, its efficiency is constrained by two coupled bottlenecks: the labeling-based pricing problem spends substantial computation exploring labels and uncovering many redundant candidate columns, while only a small, complementary subset materially improves the master problem. We study CG with routing pricing subproblems solved by labeling algorithms and formulate label-extension ordering and column selection as two sequential decisions within a shared Markov decision process. We consider a practical setting that learns from rich pre-collected CG trajectories without solving CG online during training, using data generated by existing CG solvers. We propose Coupled-CG, a two-stage offline Q-learning framework with stage-specific conservative regularization that combines support-aware value learning for extension ordering, relation-conditioned marginal column selection, and coupled Bellman updates that propagate value across the two stages and successive CG iterations. Experiments on public CVRPTW benchmarks demonstrate substantial reductions in labeling effort and end-to-end CG runtime. Ablation studies quantify the additional gains from jointly learning the two decisions, while instance-level analyses identify the structural characteristics of instances that benefit most from Coupled CG.

Primary area:
reinforcement learning
Keywords:
Column Generation, Offline Reinforcement Learning, Labeling Augmented Optimization, Vehicle Routing, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_z2ziOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This papr focuses on how to improve the efficiency and effectiveness of CG algorithm on the VRP with time-window constraints. They apply the MDP in the offline reinforcement learning scenario to explore how to unify the ordering and column selection in the CG. In experiments, they show that compared to the standard CG, their proposed method and framework can achieve better results on the benchmark.

Critical strengths

The motivation is clear and strong: current CG based methods are somewhat inefficient and time-consuming. So the authors propose a method that formulates the CG in the view of offline reinforcement learning, which unifies the operations that are critial to the efficiency and performances of CG.

Critical weaknesses

I think the authors may miss one important reference: Shen, Yunzhuang, et al. "Adaptive stabilization based on machine learning for column generation." ICML 2024. This paper also cares about the CG and applies it for some combinatorial optimization problems. Although their task is less relevant to the VRP, I suggest you compare with it.

Questions for authors
  1. Can you compare with the paper Shen, Yunzhuang, et al. "Adaptive stabilization based on machine learning for column generation." in method/experiment (if possible).

  2. Why using the offline reinforcement learning for CG to solve the VRP? As far as I know, methods in VRPTW mostly use the online RL to conduct the solving. For instances, POMO, MVMoE and Route-Finder all apply online RL to solve various kinds of VRPTW. So I want to know why the offline reinforcement learning is necessary here?

  3. A lot other neural solvers like POMO/MVMoE/Route-Finder also test on the Solomon benchmark. Is there any possibility that you can compare your method with these methods?

4 comments
  1. Can you compare with the paper Shen, Yunzhuang, et al. "Adaptive stabilization based on machine learning for column generation." in method/experiment (if possible).

1. Method comparison. The two methods act on different parts of a CG iteration.

ASCG-ML (Shen et al., 2024)Coupled-CG (ours)
What is learnedA prediction of the optimal dual solution, made once per instanceTwo policies applied at every iteration: label-extension ordering and column selection
Where it actsDual side of the RMP: the predicted duals are the stabilization center, and a penalty keeps the RMP duals close to itPricing search and primal side of the RMP: how labeling explores, and which generated columns enter the RMP
How it adaptsThe penalty weight is updated from the current reduced cost and removed when no improving column is foundBoth policies observe the current RMP state (columns and duals) at each iteration
LearningSupervised regression on optimal dualsOffline RL on logged CG trajectories
Source of speed-upFewer CG iterations, by damping dual oscillationLess labeling effort per iteration and more useful columns
ExactnessFinal exact pricing under the unstabilized dualsFinal exact pricing

2. The two methods are complementary. ASCG-ML changes the dual vector that is sent to pricing. Coupled-CG takes the dual vector it is given and decides how the pricing search is ordered and which returned columns are added. Neither method modifies the component the other controls, so both can run in the same CG loop.

3. Combined algorithm (Coupled-CG + ASCG-ML). Let π^\hat{\pi} be the predicted duals and ρt\rho_t the penalty weight. At each iteration tt:

  • Step 1 (stabilized RMP). Solve the RMP with penalty ρt\rho_t around π^\hat{\pi}; obtain the stabilized duals π~t\tilde{\pi}_t and objective ZtZ_t.
  • Step 2 (pricing stage). Encode the RMP state with π~t\tilde{\pi}_t, select the extension-ordering rule gt=arg⁡max⁡g∈GQP(ht,g)g_t=\arg\max_{g\in\mathcal G}Q^P(h_t,g), and run labeling under π~t\tilde{\pi}_t to obtain the candidate set Ct\mathcal C_t.
  • Step 3 (column-selection stage). Select Ot⊆CtO_t\subseteq\mathcal C_t with ∣Ot∣≤k\lvert O_t\rvert\leq k using QCQ^C, and add OtO_t to the RMP.
  • Step 4 (penalty update). Update ρt+1\rho_{t+1} with the ASCG rule from the best reduced cost found in Step 2.
  • Step 5 (termination). If Ct=∅\mathcal C_t=\emptyset, set ρ=0\rho=0, re-solve the RMP, and run exact pricing under the unstabilized duals. Stop if no column with negative reduced cost exists; otherwise add the columns and continue.

Step 5 is the termination test used by each method alone, so the combined algorithm returns the same LP optimum. We include this variant in the comparison below.

4. Empirical comparison.

We implemented the adaptive stabilization method of Shen et al. (ASCG-ML) in our CVRPTW CG code and trained it on our training instances. ASCG-ML uses three seeds per instance; means are over instances on which all methods finished (289 small, 207 large), and all reach the same LP optimum.

SetMethodMean iterationsMean labelsMean time (s)Median time (s)
SmallPlain CG37.3125,2772.730.077
SmallASCG-ML34.6123,4812.980.034
SmallCoupled-CG33.837,8542.130.07
SmallCoupled-CG + ASCG-ML27.536,5921.870.05
LargePlain CG278.11,019,798142.475.31
LargeASCG-ML231.1933,473115.684.71
LargeCoupled-CG219.797,86579.263.98
LargeCoupled-CG + ASCG-ML201.898,30165.983.01

Coupled-CG uses 69% (small) and 90% (large) fewer labels than ASCG-ML and is 29% and 31% faster. The combination is best on iterations and time: against ASCG-ML it needs 21% and 13% fewer iterations and 37% and 43% less time, and against plain CG 26% and 27% fewer iterations and 32% and 54% less time. The two methods are therefore complementary.

  1. Why does COUPLED-CG use offline rather than online RL, as used in routing methods such as POMO, MVMoE, and RouteFinder?

We use offline RL for two reasons.

1. Logged CG trajectories are available in practice, and online interaction with a CG solver is costly. POMO, MVMoE, and RouteFinder are constructive neural solvers: one training episode is a single rollout of the policy network, so online RL is natural for them. In our setting the environment is an exact CG solver. One episode is a complete CG run, with a labeling algorithm and an LP re-solve at every iteration, and takes seconds to minutes per instance. Online RL would have to run the solver under an exploring policy for every training sample. In contrast, organizations that solve routing problems with CG repeatedly already produce solver runs that can be logged as a by-product. Offline RL learns from these logs without running exploratory policies inside a production solver.

2. Offline training is cheaper than online training. We measured the training time of the learning-based CG methods on the same training instances, with three runs per method. Yuan (PPO) and FFCG (DQN) train online, with CG running inside the training loop.

MethodTrainingDecisions learnedMean training time (h)Relative to Coupled-CG
Coupled-CG (ours)Offline RL on logged trajectoriesPricing and column selection1.441.441.0×1.0\times
FFCGOnline RL, CG in the loopColumn selection3.803.802.6×2.6\times
YuanOnline RL, CG in the loopColumn selection18.8218.8213.0×13.0\times

Coupled-CG learns two policies in 1.44 h, against 3.80 h and 18.82 h for the online methods, which each learn one. The Coupled-CG time excludes the one-time collection of the logged trajectories, which come from ordinary solver runs.

  1. A lot other neural solvers like POMO/MVMoE/Route-Finder also test on the Solomon benchmark. Is there any possibility that you can compare your method with these methods?

Yes, on solution quality. Both approaches return a feasible routing solution for the same instance, so the distance of that solution can be compared directly, measured against the CG lower bound. Solve time is not a fair comparison: a neural solver only constructs a solution, whereas CG also proves the LP bound and certifies the gap of its solution. CG-specific measures, such as iterations and labels, do not exist for neural solvers.

1. Different directions. MTPOMO, MVMoE, and RouteFinder are end-to-end constructive heuristics with no bound on solution quality. Coupled-CG accelerates an exact method that returns the LP lower bound of the set-partitioning formulation and, from the generated columns, an integer solution with a certified gap to that bound.

2. How the comparison is made.

  • Same instances. All methods are run on our test split of 300 small and 300 large Solomon-type instances.
  • Instance conversion. Each instance is converted to the input convention of the neural solvers: coordinates, time windows, and service durations are scaled by a common factor of 100, and demands by the vehicle capacity.
  • Models. We use the released size-50 checkpoints with 8-fold augmentation, both zero-shot and after fine-tuning on our training instances (50 epochs).
  • Common objective. Every method minimizes total travel distance; costs are mapped back to the original scale.
  • Metric. We report the gap to the CG LP lower bound, (z−zLP)/zLP(z-z_{LP})/z_{LP}. This bound holds for every feasible solution, and every exact CG variant attains the same bound, so the reference does not depend on which CG method computes it. The gap is reported on the instances where CG terminated exactly within the time limit (299 small, 185 large).

3. Results.

MethodSmall: mean gapSmall: median gapSmall: at the boundLarge: mean gapLarge: median gapLarge: at the bound
MTPOMO, zero-shot20.99%15.62%14/29933.72%17.27%2/185
MVMoE, zero-shot26.76%21.10%10/29936.19%22.76%1/185
RouteFinder, zero-shot16.39%12.80%12/29923.52%16.85%0/185
MTPOMO, fine-tuned11.29%7.18%43/29918.83%13.43%2/185
MVMoE, fine-tuned13.17%9.65%40/29922.80%18.55%0/185
RouteFinder, fine-tuned8.03%5.83%43/29914.63%11.55%0/185
Traditional CG, integer solution from generated columns0.66%0.00%248/2991.86%0.09%88/185
Coupled-CG, integer solution from generated columns0.56%0.00%288/2991.87%0.10%133/185

The best neural solver, fine-tuned RouteFinder, is on average 8.03% (small) and 14.63% (large) above the lower bound. Coupled-CG is within 0.56% and 1.87%, and its generated columns reach the bound on 288 of 299 small and 133 of 185 large instances, against 248 and 88 for traditional CG. Coupled-CG terminates with exact pricing, so it attains the same LP bound as traditional CG. The neural solvers are also sensitive to the instance distribution: their released checkpoints have mean gaps of 16-36% zero-shot and reach 8-23% only after fine-tuning on our training instances. Coupled-CG needs no such adaptation, because its exactness does not depend on the learned policy.

I think added experiments address my concerns. I suggest authors polish the writings and motivations of the paper to a more clear state. Good Luck! I raise my score to 3.

Reviewer_BdoZOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper addresses limitations in column generation (CG) optimization methods for routing problems. Within the standard master-pricing decomposition scheme, the paper considers a pricing problem solved via a labeling algorithm, which involves both generating feasible solutions (here, routes) through label-extension decisions and selecting a subset of the resulting columns to incorporate as new columns in the master problem. While existing methods allows improving those two steps independently to accelerate CG, the authors argue that their interdependency has been overlooked. To unlock potential speedups by accounting for this interdependency, they propose coupled-GC, a method that jointly learns a policy for label-extension ordering and a policy for column selection, using offline reinforcement learning (RL). They additionally propose to refine the proposed vanilla RL formulation in two ways: (i) by adding a support-aware penalty when selecting label-extension ordering actions that are weakly supported by the offline data (support-aware extension ordering), and (ii) by introducing a structured Q-value model for column selection that accounts for both the individual value of candidate columns and their pairwise interactions (relation-conditioned marginal column selection). Finally, they empirically validate the method on Solomon CVRPTW instances, comparing with four CG baselines (one classical method and three learning-based methods for column selection), reporting improvements across several efficiency metrics, including end-to-end wall-clock time.

Critical strengths
  • The paper addresses a computational challenge in a core operations research method, column generation, through a conceptually simple two-policy offline RL framework that jointly coordinates label-extension ordering and column selection. While prior work has studied both components and combined learned approaches, the authors distinguish their method through the joint training of the two policies.

  • The proposed method accelerates optimization for routing problems, with experiments on Solomon CVRPTW instances showing improvements over several CG baselines across multiple efficiency metrics.

Critical weaknesses
  • The method combines several design choices whose individual contributions do not appear to be isolated experimentally, nor supported by theoretical guarantees (Prop. 1 is rather straightforward and, as the authors note, does not cover the final proposed algorithm). In particular, the benefit of joint learning remain somewhat unclear to me. The ablations in Fig. 2 seem to change more than the coupling alone, since one decision is either fixed or handled by an external selector. Additionally, the benefit of the proposed refinements to the vanilla offline RL formulation (support-aware extension ordering and relation-conditioned marginal column selection) does not seem to be experimentally validated. Finally, unless I missed something, all baselines use fixed pricing, so the proposed learned extension ordering is not compared against existing learning-based pricing methods.

  • The effectiveness of the proposed components is demonstrated only on CVRPTW, although they appear applicable to a broader range of column generation problems, at least those with labeling-based pricing. While this is consistent with the paper's stated scope, prior learning-based approaches for labeling-based pricing, such as Morabit et al. (2023), which is cited but not included as a baseline, have been evaluated on several problem classes (vehicle and crew scheduling, and VRPTW). It is therefore unclear to me whether the contribution is sufficiently broad relative to existing work.

Questions for authors
  • Fig. 2 compares COUPLED-CG with variants that learn only one decision or combine learned pricing with existing column-selection methods. However, these comparisons do not isolate the benefit of coupled training. Could the authors clarify how they assess this benefit against independently trained policies?

  • The paper reports inference-time gains but not training costs. Could the authors provide some indication of how the training time of Coupled-CG compares with that of the learning-based baselines and decoupled variants? This would help assess the overhead relative to the runtime savings.

  • All baselines in Table 1 use fixed pricing and differ only in column selection, while several learning-based pricing approaches are discussed in the related work. Could the authors comment on why none of these are included as baselines?

  • Could the authors clarify the individual contributions of the two proposed refinements, support-aware extension ordering and relation-conditioned marginal column selection, to the reported gains? For instance, ablations removing the support-aware penalty or the pairwise interaction terms could help assess their respective impact.

--------------- Miscalleneous

  • the acronym CVRPTW could be properly defined in the introduction
  • Several important quantities are not introduced in the main text (\mathcal G, Z_t, Q_t, y_t)
  • The methodological sections would benefit from explicitly citing the RL methods they build on, e.g., CQL (Kumar et al., 2020) for the conservative regularizers, and relevant work on reward shaping.
  • L.283 and l.302: hth_t and h~t\tilde{h}_t are re-defined unnecessarily.
  • Neither g^t\hat{g}_t (logged extension-ordering action) nor ξg\xi_g (rule prototype) appears in the notation table (Table 3).
  • A brief introduction of the baselines in the main text, and of how they differ from the proposed method, could help interpret the results.
2 comments

W1 & Q1. Fig. 2 compares COUPLED-CG with variants that learn only one decision or combine learned pricing with existing column-selection methods. However, these comparisons do not isolate the benefit of coupled training. Could the authors clarify how they assess this benefit against independently trained policies?

Fig. 2 already compares Coupled-CG with independently trained policies (Section 5.2, Appendices O-P).

  • Independent training (Appendix P). Pricing Only and Column Selection Only keep the architectures, rewards, regularizers, and γ=1\gamma = 1 of Coupled-CG and change only the Bellman target to a within-stage one: QtP←Qt+1PQ_t^P \leftarrow Q_{t+1}^P and QtC←Qt+1CQ_t^C \leftarrow Q_{t+1}^C (Eqs. 58, 62-63), instead of the cross-stage QtP←QtC←Qt+1PQ_t^P \leftarrow Q_t^C \leftarrow Q_{t+1}^P (Eq. 64).

  • What Fig. 2 measures. Each single-decision variant isolates the benefit of learning one decision. The three hybrids pair the same independently trained pricing policy with FFCG, Yuan, or Morabit (Appendix O). Since the only difference from Coupled-CG is the cross-stage target, the gap between Coupled-CG and these variants is the benefit of coupled training: Coupled-CG gives the most consistent gains in CG time, labels, and iterations, while the hybrids show larger variance.

  • Revision. We will state this protocol in the caption of Fig. 2.

Q2. The paper reports inference-time gains but not training costs. Could the authors provide some indication of how the training time of Coupled-CG compares with that of the learning-based baselines and decoupled variants? This would help assess the overhead relative to the runtime savings.

We measured offline training time on the same training data, three runs per method.

MethodLearningDecisions learnedMean (h)Median (h)
MorabitSupervised classifierColumn selection0.340.30
Coupled-CGOffline RLPricing and column selection1.440.91
FFCGOnline RLColumn selection3.803.82
YuanOnline RLColumn selection18.8218.61

Among the RL methods, Coupled-CG trains fastest, 2.6×2.6\times faster than FFCG and 13.0×13.0\times faster than Yuan, while learning two decisions instead of one, since it never runs CG during training. Morabit trains faster because it is supervised: it fits a classifier to fixed expert labels, whereas RL bootstraps long-horizon values and needs repeated target updates to converge. Its time also excludes generating the expert labels (0.30 h). In return, Coupled-CG optimizes the labeling effort of the whole CG run across both decisions, while a classifier imitates per-iteration labels for one decision.

Q3. All baselines in Table 1 use fixed pricing and differ only in column selection, while several learning-based pricing approaches are discussed in the related work. Could the authors comment on why none of these are included as baselines?

Coupled-CG keeps pricing exact, so Table 1 compares it with methods that do the same and differ only in column selection. Learned pricing methods prune or replace the pricing network; alone they do not certify the LP optimum, so their effort was not directly comparable. We now make them comparable with an exact pricing fallback, so all methods reach the same LP optimum. We add three in the same CG code (M=10M=10, K=5K=5, 900s900 s): arc selection (Morabit et al., 2023), RLHH (Xu et al., 2025), and POMO-CG (Abouelrous et al., 2025). Means are over instances all exact methods solve (299 small, 105 large).

SetMethodExact terminationTime limitMean iterationsMean labelsMean time (s)Median time (s)
SmallTraditional CG299/300116.8103,32312.840.04
SmallMorabit arc selection300/300016.622,7420.850.07
SmallXu RLHH300/300026.724,4841.000.07
SmallPOMO-CG (hybrid)300/300015.648,9907.510.10
SmallCoupled-CG300/300014.821,8952.340.06
LargeTraditional CG185/30011550.0119,70812.020.96
LargeMorabit arc selection126/30017449.5393,52435.385.35
LargeXu RLHH126/30012970.1300,70018.253.65
LargePOMO-CG (hybrid)106/30019449.6585,669118.7716.01
LargeCoupled-CG239/3006145.287,8148.761.01

On large instances, the learned pricing methods solve fewer instances than traditional CG (106-126 vs. 185), so their small-instance gains do not generalize; Coupled-CG solves 239/300 with fewer labels and less time. POMO-CG without exact fallback gives no certificate.

Q4. Could the authors clarify the individual contributions of the two proposed refinements, support-aware extension ordering and relation-conditioned marginal column selection, to the reported gains? For instance, ablations removing the support-aware penalty or the pairwise interaction terms could help assess their respective impact.

We trained three ablated models with the same data, architecture, and schedule: support-aware pricing only, relation-conditioned selection only, and neither. Removing support-aware pricing replaces it with a standard CQL argmax; removing relation-conditioned selection replaces it with independent per-column scores and top-kk selection. Results are on the 300 test instances (seed 43); means are over successful runs.

Support-aware pricingRelation-conditioned selectionExact terminationTime limitMean iterationsMean labelsMean time (s)
YesYes (full Coupled-CG)300/300014.821,8952.34
YesNo274/3002616.9537,8261.20
NoYes266/3003417.43116,5355.42
NoNo260/3004017.05119,1896.44

The full model solves all 300 instances with the fewest iterations and labels; removing either technique increases labeling effort by 73-432%.

Q5. Miscalleneous

We will address all these points in the revision as follows:

  • define CVRPTW at its first use in the Introduction;
  • introduce G\mathcal G, ZtZ_t, QtQ_t, and yty_t in the main text where they first appear;
  • cite CQL (Kumar et al., 2020) for the conservative regularizers and Ng et al. (1999) for reward shaping;
  • remove the repeated definitions of hth_t and h~t\widetilde h_t (l.283 and l.302);
  • add gtg_t and g^t\hat{g}_t to the notation table (Table 3);
  • add a brief description of each baseline, and of how it differs from Coupled-CG, to the main text.

W2. The effectiveness of the proposed components is demonstrated only on CVRPTW, although they appear applicable to a broader range of column generation problems, at least those with labeling-based pricing. While this is consistent with the paper's stated scope, prior learning-based approaches for labeling-based pricing, such as Morabit et al. (2023), which is cited but not included as a baseline, have been evaluated on several problem classes (vehicle and crew scheduling, and VRPTW). It is therefore unclear to me whether the contribution is sufficiently broad relative to existing work.

We agree that Coupled-CG has the potential to generalize beyond CVRPTW. To evaluate its broader applicability, we conducted additional experiments on two problems: vehicle routing with time windows but without capacity constraints (VRPTW) and airline crew pairing. The comparison with Morabit et al. (2023) is addressed separately under Question 3.

1. VRPTW without capacity. The CVRPTW-trained policy is applied without retraining to 60 small and 60 large instances. The table gives the ratio of means of Coupled-CG to traditional CG over commonly solved instances (Instances).

SetInstancesIterationsLabelsCG time
Small58/600.91×0.91\times0.72×0.72\times1.07×1.07\times
Large36/600.95×0.95\times0.36×0.36\times0.31×0.31\times

On the large set, labeling effort falls by 64% and CG time by 69%.

2. Airline crew pairing. Every flight leg is covered exactly once by pairings: sequences of duties separated by overnight rests that start and end at the same crew base. Pricing is a resource-constrained shortest path solved by labeling. Data: GERAD instances (Kasirzadeh et al., 2017), seven monthly airline schedules (1,013-7,766 legs) cut into day windows; instances 1, 4, 6, and 7 are held out for testing. The same two-stage MDP is used:

MDP elementCVRPTWAirline crew pairing
ColumnVehicle routePairing
RMP rowsCustomer covering, fleet sizeLeg covering
Label resourcesReduced cost, load, timeReduced cost, pairing start, duties used, duty start, duty flying time, duty legs
Pricing action gtg_tOrder labels by reduced cost, time, or loadOrder labels by reduced cost, legs covered, time away from base, or unproductive time
Selection action OtO_tUp to kk routesUp to k=5k=5 of M=10M=10 pairings

An exhaustive pass certifies optimality, so every policy reaches the same LP optimum. Geometric mean of Coupled-CG relative to traditional CG:

SetInstancesIterationsLabelsCG time (pricing + RMP)
Small (132-261 legs)52/520.84×0.84\times0.59×0.59\times0.65×0.65\times
Large (323-1,013 legs)51/510.82×0.82\times0.45×0.45\times0.55×0.55\times
Reviewer_4878OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

COUPLED-CG, a two-stage offline Q-learning framework with stage-specific conservative regularization, was proposed, combining support-aware value learning for extension ordering, relation-conditioned marginal column selection, and coupled Bellman updates that propagate value across the two stages and successive CG iterations.

Critical strengths

Large-scale routing optimization is an important research topic.

Critical weaknesses
  1. The paper’s novelty could be presented with greater clarity and emphasis. Stating the contributions and hypotheses more explicitly may further improve the manuscript. Offline Reinforcement Learning with heuristic algorithms has been reported in much of the literature.
  2. The details of the method are not given. The reward design should be discussed.
  3. The experimental results are not sufficient to validate the algorithm.
  4. The quality of the figures should be enhanced.
  5. The generalization of the proposed algorithm should be discussed.
Questions for authors
  1. The paper’s novelty could be presented with greater clarity and emphasis. Stating the contributions and hypotheses more explicitly may further improve the manuscript. Offline Reinforcement Learning with heuristic algorithms has been reported in much of the literature.
3 comments

We thank the reviewer for the positive feedback. Below, we address each of the questions raised.

W1. The paper’s novelty could be presented with greater clarity and emphasis.

Column generation (CG) is an exact algorithm for linear programs, not a heuristic. Within each CG iteration, pricing and column selection are connected by the algorithm itself: pricing produces the candidate columns from which the selection is made, and the selected columns change the dual variables that define the next pricing problem. This connection is a structural fact of CG, not an assumption of our model. Existing learning-based studies ignore it and learn one decision in isolation. Our novelty is to model this connection explicitly and to identify the gain from learning the two decisions jointly.

Research position. Each line of work below learns one decision and fixes the other. Coupled-CG learns both through cross-stage Bellman updates, keeps pricing exact, and trains offline.

Line of workPricingColumn selectionLearningLimitation
Column selection: Morabit et al. (2021); Chi et al. (2022); Yuan et al. (2024); Hu et al. (2025)Fixed, exactLearned: one or several columnsSupervised or online RLPricing effort, the main cost, is untouched; needs expert labels or online CG runs
Pricing-network reduction: Quesnel et al. (2022); Morabit et al. (2023); Xu et al. (2023)Learned reduction; exact only through fallbackFixedSupervised or online RLReduced network can miss columns; column selection not chosen
Learned pricing heuristic: Shen et al. (2022); Abouelrous et al. (2025)Learned heuristicFixedSupervised or online RLNo certificate without exact pricing; column selection not chosen
Coupled-CG (ours)Learned extension order; network unchanged, exactLearned, up to k of M, using column relationsOffline RL, support-aware and conservativeNone of these: both decisions learned jointly, exact pricing, no labels or online runs

Hypothesis. Since the coupling is structural, we hypothesize that there exists a state-dependent joint policy for extension ordering and column selection that requires less cumulative labeling effort than fixed rules or independently learned policies, and that this policy can be learned from logged CG trajectories.

Contributions.

  1. Formulation. We cast the two coupled decisions as two stages of one MDP that minimizes cumulative labeling effort, with stage rewards that provably preserve this objective (Proposition 1).

  2. Coupled offline learning. Cross-stage Bellman updates value an ordering rule by the columns it yields and a column set by the pricing problem it creates. Support-aware conservative learning and relation-conditioned marginal selection make this policy learnable from logged data, with no solver interaction; removing either technique raises labeling effort by 73-432% (BdoZ, Q4).

  3. Evidence for the hypothesis. The learned joint policy outperforms fixed rules and independently trained and hybrid variants (Fig. 2; BdoZ, Q1). On 300 large instances it solves 239, against at most 185 for traditional CG and three learned pricing methods, and it transfers without retraining to VRPTW without capacity (64% fewer labels, 69% less time).

We will revise the introduction and the problem formulation (Section 4.1) to state this position, the hypothesis, and these contributions explicitly.

W2: The details of the method are not given. The reward design should be discussed.

1. Method (Sections 4.1-4.3). Coupled-CG casts one CG iteration as a two-stage MDP. The pre-pricing state stPs_t^P is the current RMP, encoded as a bipartite column-constraint graph hth_t. The pricing policy selects an extension-ordering rule gt∈Gg_t\in\mathcal G (minimum reduced cost, minimum or maximum load, minimum or maximum time); labeling under gtg_t yields the candidate set Ct\mathcal C_t and the state stC=(stP,Ct)s_t^C=(s_t^P,\mathcal C_t). The column-selection policy then chooses Ot⊆CtO_t\subseteq\mathcal C_t, ∣Ot∣≤k\lvert O_t\rvert\leq k, and the RMP update gives st+1Ps_{t+1}^P. Ordering changes only the processing order of labels, so the extension, feasibility, and dominance rules, and hence exact CG termination, are unchanged. Table 4 (Appendix E) gives the full specification.

Both policies are learned from fixed CG trajectories logged under a randomized behavior policy, with no further solver interaction. Their value functions are coupled through the cross-stage Bellman targets in Eqs. (9)–(10).

ytP=rtP+(1−donet)VϕˉC(h~t)y_t^P = r_t^P + (1-\mathrm{done}_t)V^C_{\bar{\phi}}(\widetilde{h}_t)

ytC=rtC+(1−donet)VϕˉP(ht+1)y_t^C = r_t^C + (1-\mathrm{done}_t)V^P_{\bar{\phi}}(h_{t+1})

The first target values an extension rule by the candidate columns it yields. The second values a selected column set by the pricing problem it creates in the next CG iteration. For extension ordering, we choose the rule that maximizes the uncertainty-penalized score in Eqs. (11)–(12).

arg⁡max⁡g[QϕP(ht,g)−κPuP(ht,g)]\arg\max_g \left[Q^P_{\phi}(h_t,g) - \kappa_P u^P(h_t,g)\right]

The penalty discourages rules that are weakly supported by the logged data. For column selection, we factor the set value into unary scores and pairwise compatibilities on the candidate relation graph. Starting with the column of lowest reduced cost, we greedily add the column with the highest marginal value until kk columns have been selected (Eqs. (13)–(14)). This avoids enumerating all size-kk subsets. Both value functions are trained with temporal-difference and stage-specific conservative losses (Eq. (15) and Appendix L).

2. Reward design (Section 4.1). The pricing reward penalizes the number of labels explored in each pricing call. The column-selection reward gives intermediate feedback on RMP objective improvement. By Proposition 1 (proof in Appendix F), under a fixed initial RMP, undiscounted returns, and exact CG termination,

=\beta\frac{Z_1-Z_{T+1}}{\max\{1,|Z_1|\}},$$ which is independent of the learned policies because exact CG termination yields the same final LP optimum. The RMP-improvement reward therefore does not change the optimizer of the cumulative labeling-effort objective. Empirically, compared with $\beta = 0$, positive coefficients reduce mean CG time by approximately **4%-9%** (Appendix R, Table 6). >W3: The experimental results are not sufficient to validate the algorithm. We added five experiments on a common test split of 300 small (6-18 customers) and 300 large (20-60 customers) instances, 50 per Solomon family, and two tests beyond CVRPTW. These experiments validate the method from complementary perspectives: comparisons with alternative learning-based methods establish effectiveness, ablation studies isolate the contributions of key components, training-time analysis assesses computational overhead, and the tests on VRPTW without capacity and airline crew pairing examine generalizability. Coupled-CG performs best or matches the best in each: | Experiment | Key result for Coupled-CG | Full table | |---|---|---| | Learning-based pricing baselines | Large set: solves 239/300 instances, against 106-185 for traditional CG, arc selection, RLHH, and POMO-CG, with the fewest labels and the least time (8.76 s vs. 12.0-118.8 s) | BdoZ, Q3 | | Ablation of the two offline techniques | Only the full model solves all 300 instances; removing either technique raises labeling effort by 73-432% | BdoZ, Q4 | | ML-based adaptive stabilization (ASCG-ML) | 69% (small) and 90% (large) fewer labels than ASCG-ML; combining both cuts time by a further 37% and 43% | z2zi, Q1 | | Neural solvers (MTPOMO, MVMoE, RouteFinder) | Gap to the LP bound 0.56% (small) and 1.87% (large), against 8.03% and 14.63% for the best neural solver | z2zi, Q3 | | Training time | Fastest RL method: 1.44 h, against 3.80 h (FFCG) and 18.82 h (Yuan) | BdoZ, Q2 | | VRPTW without capacity, no retraining | Large set: 64% fewer labels and 69% less time than traditional CG | W5 | | Airline crew pairing (GERAD instances) | 41% (small) and 55% (large) fewer labels, 35% and 45% less CG time than traditional CG | W5 |

W4. The quality of the figures should be enhanced.

We will revise the figures. Fig. 2: shared method labels across panels, clipped axes with outliers annotated, a legend for the mean and median markers, and colours that separate Coupled-CG, single-decision variants, and hybrids. Fig. 3: separate colour scales for the two panels, quintile ranges on the axis, and a caption note on why the mean reduction and the share of faster instances differ.

W5. The generalization of the proposed algorithm should be discussed.

Coupled-CG is not specific to CVRPTW: it applies to any CG algorithm in which pricing is a resource-constrained shortest path solved by labeling and several columns are added per iteration, which covers vehicle routing variants and crew pairing and scheduling. We test one problem from each class below.

We applied the policy trained on CVRPTW, without retraining, to a different problem variant: VRPTW without the capacity constraint. The test uses 60 small and 60 large instances (10 per family), M=10M=10, K=5K=5, and a 900 s limit. Traditional CG uses the same solver with the minimum-reduced-cost rule and the KK most negative columns. The table gives the ratio of Coupled-CG to traditional CG in mean iterations, labels, and time over the instances both solve exactly (Instances), where both reach the same LP optimum.

SetInstancesIterationsLabelsCG time
Small (60)58/600.91×0.91\times0.72×0.72\times1.07×1.07\times
Large (60)36/600.95×0.95\times0.36×0.36\times0.31×0.31\times

On the large set, the transferred policy reduces labeling effort by 64% and mean CG time by 69% on the 36 commonly solved instances, and solves two more instances within the time limit (38 against 36; time limit reached on 19 against 21).

Airline crew pairing. Coupled-CG requires only labeling-based pricing and the insertion of several columns per iteration, so we also implemented it for airline crew pairing on the GERAD instances (Kasirzadeh et al., 2017). Flight legs are covered by pairings, and the pricing action orders labels by reduced cost, legs covered, time away from base, or unproductive time. Test windows come from four held-out monthly schedules. Geometric mean of Coupled-CG relative to traditional CG:

SetInstancesIterationsLabelsCG time (pricing + RMP)
Small (132-261 legs)52/520.84×0.84\times0.59×0.59\times0.65×0.65\times
Large (323-1,013 legs)51/510.82×0.82\times0.45×0.45\times0.55×0.55\times

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.