- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper introduces ALTER, a neural solver for hard-constrained routing that repeatedly alternates cost-oriented exploration and feasibility-oriented repair, coordinated through accumulated disagreement and learned state-dependent coupling. The paper characterizes coupling intervals for feasible cost improvement with finite candidate pools and evaluates ALTER on TSPTW, TSPDL, and CVRPBLTW.
Critical strengths
- The split between cost-oriented exploration and feasibility-oriented repair is intuitive.
- The coupling-interval analysis is helpful for explaining how the two roles interact.
- The results on TSPDL Hard and CVRPBLTW are impressive.
Critical weaknesses
- On TSPTW Hard, ALTER has a higher instance infeasibility and longer runtime than LMask [1]. Although the authors acknowledged it, the paper still lacks sufficient analysis of the reasons for this disadvantage.
- Native inference configurations and method-specific successful-instance subsets make the reported cost improvements harder to judge.
- The ablation study does not isolate the contribution of disagreement memory, leaving its independent benefit unclear.
Questions for authors
- Do the reported advantages over LMask [1] and CaR [2] persist under matched time budgets? Please also report gaps in the subset of instances solved successfully by all three methods.
- How much does disagreement memory contribute when all other components are kept unchanged?
- How does adaptive penalty control compare with a tuned fixed penalty, beyond the reported fixed consensus setting of ?
References:
[1] Li, Tianyou, et al. LMask: Learn to solve constrained routing problems with lazy masking. ICLR 2026.
[2] Bi, Jieyi, et al. Towards efficient constraint handling in neural solvers for routing problems. ICLR 2026.
8 comments
Response to QzwZ — W2 & Q1: Matched inference-time budgets and common solved subset
For the comparison under matched inference-time budgets, please see our response to Reviewer 2 (W2 & Q2). ALTER achieves the lowest gap in five of the six TSPTW/TSPDL settings.
Table vii shows the gap over the instances on which all compared methods return a feasible route. ALTER achieves the lowest gap in seven of the eight problems.
Table vii. Average gap (%) on the common instances for which all compared methods return feasible routes.
| Setting | Common instances | ALTER | LMask | CaR |
|---|---|---|---|---|
| TSPTW-50 Medium | 9,999 | 1.58 | 1.68 | 2.61 |
| TSPTW-100 Medium | 10,000 | 3.04 | 3.92 | 8.97 |
| TSPTW-50 Hard | 9,978 | 0.13 | 0.10 | 0.02 |
| TSPTW-100 Hard | 7,686 | 0.15 | 0.21 | 0.76 |
| TSPDL-50 Hard | 9,945 | 1.32 | 2.21 | 6.39 |
| TSPDL-100 Hard | 9,603 | 2.76 | 4.18 | 10.31 |
| CVRPBLTW-50 | 974 | – | 2.12 | |
| CVRPBLTW-100 | 969 | – |
Response to QzwZ — W3 & Q2: Independent contribution of disagreement memory
We evaluate the contribution of disagreement memory by disabling it at inference while retaining both search roles and adaptive penalty control. Table viii compares the two configurations on the four TSPTW/TSPDL Hard settings.
Table viii. Memory ablation with adaptive penalty control. Entries are solution infeasibility (%) / instance infeasibility (%) / gap (%).
| Setting | Without memory | With memory |
|---|---|---|
| TSPTW-50 Hard | 2.17 / 0.27 / 0.132 | 1.83 / 0.21 / 0.126 |
| TSPTW-100 Hard | 27.69 / 8.48 / 0.156 | 19.14 / 5.02 / 0.160 |
| TSPDL-50 Hard | 0.13 / 0.00 / 1.396 | 0.14 / 0.00 / 1.323 |
| TSPDL-100 Hard | 0.21 / 0.03 / 2.779 | 0.24 / 0.03 / 2.755 |
On TSPTW-50 Hard, memory improves all three reported metrics. On TSPTW-100 Hard, it reduces instance infeasibility from 8.48% to 5.02%, yielding 346 more solved instances overall out of 10,000 and a 40.8% reduction in failed instances. On TSPDL-50 Hard, both variants solve all 10,000 instances, and memory reduces the gap from 1.396% to 1.323%. These results demonstrate the contribution of disagreement memory to feasibility recovery and route quality within the full adaptive solver.
Response to QzwZ — W1: Feasibility and runtime on TSPTW Hard
TSPTW Hard has a visit-order structure that LMask can exploit directly during route construction. Its generator first samples a random tour and then constructs each customer's time window around its arrival time on that tour, whereas Medium samples time windows independently [1]. Our TSPTW-50 diagnostic shows that two-step look-ahead leaves an average of 1.14 next-node choices on Hard, compared with 4.51 on Medium, when evaluated along reference-route prefixes. This indicates substantially tighter restrictions on the next visit in Hard.
LMask applies these restrictions before selecting the next customer: if visiting a customer would make another unvisited customer miss its deadline, two-step look-ahead excludes that choice. Backtracking then revises earlier choices when construction reaches a dead end [1]. This allows LMask to use the order information encoded in the time windows explicitly throughout construction.
ALTER's feasibility is handled through learned route generation, candidate scoring and selection, and iterative repair. Recovering the tightly constrained visiting order therefore relies on its learned policies and successive repair steps. This makes LMask particularly well matched to the ordering structure of TSPTW Hard and helps explain its higher feasibility on this distribution.
References
[1] Li, Tianyou, et al. LMask: Learn to solve constrained routing problems with lazy masking. ICLR 2026.