- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper learns a scoring rule for building relaxed decision diagrams for the traveling salesman problem with a drone. The rule is trained directly to improve the lower bound produced by the diagram. The experiments show better bounds than the tested imitation and hand-designed rules, with gains that also carry over to larger instances and another distribution.
Critical strengths
-
The improvement is consistent across unseen instances. For example, on the 15-customer instances, the mean gap drops from 16.42% with the coarse scoring rule to 10.31% with the learned rule.
-
Training does not require optimal solutions, and the learned rule preserves the validity of the lower bounds. This makes the approach useful for problems that are expensive to solve exactly.
Critical weaknesses
-
I had difficulty following how the learned score changes state selection. States in the same group receive the same learned correction, so it cannot change their order within that group. Yet the method is described as learning which states within a group should remain separate. The global width budget could allow the score to give more space to some groups than others, but this allocation step is not clearly explained. This is central to understanding what the model actually controls.
-
Some conclusions about imitation are stronger than the results support. The experiments show that direct training works better than the tested remaining-cost targets. They do not establish that the bias grows in proportion to the amount of merging or that a stronger source generally makes imitation worse. The authors themselves report that a stronger source helps once the source and evaluation costs are made comparable. The conclusion should reflect this qualification and stay closer to what the experiments demonstrate.
Questions for authors
-
How do the learned scores determine how much of the width budget each group receives? A short description of the full selection and merging procedure would help.
-
How should the claim that stronger sources worsen the bias be understood alongside the improvement after correcting the cost mismatch?
Response to Reviewer 3gNU
Thank you. Both of your criticisms were correct.
W1, Q1 – How scores set each bucket's share– h moves whole buckets across the cut-off.The compiler scans all candidates of a layer by fλ+h and keeps them as exact nodes until the width is used. Each bucket's remainder becomes one merged node. A bucket's share is the number of its states that fall before the cut-off, and h moves whole buckets across it. On test instances, relative to root distance, the learned score changes the share of 29%, 21% and 13% of buckets at m=15, 20 and 25. Shuffling the same values across buckets moves at least as many states but makes the bound worse than root distance on every instance (General comment, item 2). So the gain comes from which buckets are favored.
W2 – "Proportional to merging" and "stronger source worsens"– We rewrote both sentences.Both sentences are rewritten (Sections 4.1, 4.3 and 7). The inequality says that merging more states into one node can only lower its value. It says nothing about a rate across nodes. We then measured it at m=8, where exact values exist (Appendix S). At fixed depth, a node's bias is negatively correlated with the number of states it absorbs, in every layer (Table 16 gives the bucket-level values). Exact single-state nodes in early layers carry the largest bias, which can only come from the relaxed part below them. So the bias depends on how much relaxation lies under a node, not on its group size. None of the three confirmations of the bias (Sections 4.2 to 4.4) relied on the withdrawn sentence.
Q2 – Stronger source against the wide-lam0 result– The two did not fit, and that was our error.The two did not fit, and that was our error. Two things change together in Table 1, the source strength and the multipliers. Under the source's own multipliers the gap goes from 15.20 to 16.75. Under the inference multipliers (Min/Eval. in the revised Table 1, formerly wide-lam0) it goes from 15.26 to 14.45. What grows with source strength is the multiplier mismatch, not the relaxation bias. Section 4.3 now says this, and the general sentence is gone from Section 7. Even the best relaxed target (14.45) stays well behind the learned policy (11.20). Table 1 trains every policy, including ours, at m=8, the only size where exact targets exist, and evaluates it at m=15. The 10.31 in Table 2 is the policy trained at m=15. Both are five-seed means on the same 100 test instances at width 1024.
We hope these changes address your concerns and would be grateful if you would reconsider your score.