- 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
-
Can you compare with the paper Shen, Yunzhuang, et al. "Adaptive stabilization based on machine learning for column generation." in method/experiment (if possible).
-
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?
-
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
- 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.
| Method | Training | Decisions learned | Mean training time (h) | Relative to Coupled-CG |
|---|---|---|---|---|
| Coupled-CG (ours) | Offline RL on logged trajectories | Pricing and column selection | ||
| FFCG | Online RL, CG in the loop | Column selection | ||
| Yuan | Online RL, CG in the loop | Column selection |
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.
- 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, . 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.
| Method | Small: mean gap | Small: median gap | Small: at the bound | Large: mean gap | Large: median gap | Large: at the bound |
|---|---|---|---|---|---|---|
| MTPOMO, zero-shot | 20.99% | 15.62% | 14/299 | 33.72% | 17.27% | 2/185 |
| MVMoE, zero-shot | 26.76% | 21.10% | 10/299 | 36.19% | 22.76% | 1/185 |
| RouteFinder, zero-shot | 16.39% | 12.80% | 12/299 | 23.52% | 16.85% | 0/185 |
| MTPOMO, fine-tuned | 11.29% | 7.18% | 43/299 | 18.83% | 13.43% | 2/185 |
| MVMoE, fine-tuned | 13.17% | 9.65% | 40/299 | 22.80% | 18.55% | 0/185 |
| RouteFinder, fine-tuned | 8.03% | 5.83% | 43/299 | 14.63% | 11.55% | 0/185 |
| Traditional CG, integer solution from generated columns | 0.66% | 0.00% | 248/299 | 1.86% | 0.09% | 88/185 |
| Coupled-CG, integer solution from generated columns | 0.56% | 0.00% | 288/299 | 1.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.
1. Method comparison. The two methods act on different parts of a CG iteration.
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 π^ be the predicted duals and ρt the penalty weight. At each iteration t:
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.
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.