acceptodds
Under review as a conference paper at ICLR 2027

Learning to compile relaxed decision diagrams by optimizing the bound

Abstract

Relaxed decision diagrams certify lower bounds for discrete optimization by merging states under a per-layer width cap. Bound quality depends on which states remain separate, a decision made by hand-designed ranking rules. We study learning this ranking for the traveling salesman problem with a drone. The natural approach ranks states by accumulated cost plus a learned cost-to-go fitted to backward values from a wider relaxed diagram. We show these targets are systematically biased: a relaxed node inherits the most optimistic completion of every state it represents, so its value reflects how much merging occurred rather than the quality of the state, and more data does not remove the bias. Exact targets do not close the gap either: the same policy trained directly on the bound beats exact-target imitation by points at the size where exact targets are computable and by at a larger one, on and of held-out instances. We therefore discard targets and optimize a -parameter ranking policy against the bound compilation produces, which needs no solved instances and preserves validity for every policy. Averaged over optimizer seeds, it improves over imitation by – gap points and over the hand-designed rule it corrects by –, on at least of test instances in every configuration from to customers, and by – over root distance; it reaches in one compilation what a model-free self-guided baseline needs about three times the arc cost to match. Frozen and applied to an independently defined distribution, it is not overtaken by root distance at five times its compilation budget in three of four configurations.

Primary area:
optimization
Keywords:
decision diagrams, dual bounds, combinatorial optimisation, learning to optimise, unsupervised learning, black-box optimisation, discrete optimisation, vehicle routing, certified bounds, relaxation

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_3gNUOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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.

  2. How should the claim that stronger sources worsen the bias be understood alongside the improvement after correcting the cost mismatch?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 3gNU

Thank you. Both of your criticisms were correct.


W1, Q1 – How scores set each bucket's share – hh moves whole buckets across the cut-off.

The compiler scans all candidates of a layer by fλ+hf_\lambda+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 hh 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=15m=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=8m=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=8m=8, the only size where exact targets exist, and evaluates it at m=15m=15. The 10.31 in Table 2 is the policy trained at m=15m=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.

Reviewer_YZV5OpenReview ↗
Rating
3
Confidence
1
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies state-retention ranking during the compilation of relaxed decision diagrams (DDs), aiming to obtain tighter lower bounds under a limited computational budget. The authors identify limitations of supervised cost-to-go targets extracted from wider relaxed diagrams, including relaxation-induced optimism, minimum aggregation bias, and mismatched Lagrangian multipliers.

To address these limitations, the paper proposes directly optimizing the bound produced by compilation using a 22-parameter linear ranking policy trained with a derivative-free evolution strategy. Experiments on the traveling salesman problem with a drone (TSP-D) compare various supervision targets, exact cost-to-go values, model capacities, and computational budgets. The results demonstrate improvements in bound quality and generalization across instance sizes and distributions.

Critical strengths

S1. Systematic analysis of limitations in cost-to-go supervision.

The paper examines how relaxation-induced optimism, target aggregation, and Lagrangian multiplier mismatch affect cost-to-go supervision for relaxed DD compilation. Comparisons involving exact targets, alternative aggregation schemes, and per-state value lookups provide meaningful evidence that accurate intermediate supervision does not necessarily translate into effective state-retention decisions or tighter lower bounds.

S2. Effective direct bound optimization with meaningful experimental controls.

The proposed 22-parameter linear ranking policy achieves consistently tighter bounds than the evaluated heuristic and supervised imitation baselines across multiple instance sizes and distributions. By accounting for auxiliary compilation costs and comparing against iterative self-guided refinement, the experiments also provide evidence of improved bound quality under comparable computational budgets.

Critical weaknesses

W1. The mechanism by which the learned scoring function affects state retention is insufficiently clarified.

The paper states that states are eligible for merging only within the same (ic,it)(i_c,i_t) bucket, while the learned cost-to-go term hθ(k,ic,it)h_\theta(k,i_c,i_t) is constant for all states within a bucket at a given layer. Consequently, this term cannot change the relative ordering of states within that bucket. The current description does not sufficiently clarify how the learned policy changes the resulting state-retention decisions. If the actual mechanism involves global ranking or allocation of retention capacity across buckets, this should be explicitly explained, as it is central to understanding the proposed method.

W2. Limited validation beyond the specific optimization problem and relaxation framework.

Although the paper provides extensive evaluations across instance sizes and distributions, all core experiments focus on TSP-D and a particular relaxed DD construction. Since state representations and merging operators can differ substantially across combinatorial optimization problems, it remains unclear whether the identified limitations of cost-to-go supervision and the benefits of direct bound optimization extend to other DD applications.

Questions for authors

Q1. How does the learned cost-to-go term influence state-retention decisions?

Since hθ(k,ic,it)h_\theta(k,i_c,i_t) is constant within each (ic,it)(i_c,i_t) bucket at a fixed layer, could the authors clarify whether state retention is determined by a global ranking across buckets or independently within each bucket? In particular, how does changing hθh_\theta alter the set of states retained separately? A small illustrative example or pseudocode would be helpful.

Q2. How broadly does the identified supervision bias apply?

The analysis is developed for the particular relaxed DD construction used for TSP-D. Could the authors clarify which conclusions depend on the specific state-merging operator and which are expected to hold more generally across relaxed decision diagram formulations?

Q3. How well does compilation arc count reflect actual computational cost?

The paper primarily compares methods using matched compilation arc counts, including converted costs for auxiliary computations. Could the authors provide representative wall-clock runtime comparisons or discuss how accurately arc counts reflect actual computational costs across methods and instance sizes?

Q4. Can tighter lower bounds benefit complete exact optimization?

Although improving bound quality is a valid objective in its own right, could the authors discuss how the proposed ranking policy might be integrated into a complete exact optimization framework, and whether the resulting tighter bounds could improve search efficiency or overall solving time?

3 comments
AuthorsOpenReview ↗

Response to Reviewer YZV5

Thank you for the careful reading.


W1, Q1 – How h acts if it is constant in a bucket – You are right. hh decides how many exact nodes each bucket gets.

You are right. The paper described the wrong thing. hh never reorders a bucket's members. It decides how many exact nodes each bucket gets (General comment, item 1). Section 3.1 now gives Algorithm 1 and a small example. With two buckets of three states and W=4W=4, equal hh keeps one exact state per bucket. Lowering one bucket's hh by 10 gives it all three exact nodes and merges the other bucket whole. We also measured this on test instances (item 2). Relative to root distance, the learned score changes the exact-node count of 13% to 29% of buckets, and a shuffled table that moves at least as many states gives a much worse bound.


W2, Q2 – Dependence on the merge operator – Table 11 lists this per claim.

The inequality and the min-aggregation bias need only a relaxation and a table coarser than the state. The multiplier result needs a Lagrangian bound, and the allocation result a bucketed compiler. The magnitudes are specific to TSP-D. Table 11 lists this per claim. On the asymmetric TSP (Appendix T), the bias appears more strongly and round 0 still beats root distance, but the learned correction adds nothing because that relaxation is already tight.


Q3 – Arcs versus wall-clock – Arc counts are a fair proxy.

We timed every method in isolation (Appendix R). The width-one precompute of h0h_0 runs in its own process, and its seconds, arcs and memory are added to every method that uses it, exactly as its arcs are charged in the paper. Seconds track arcs with R2R^2 of 0.99 at each size. The learned policy is slightly cheaper per arc than root distance (1.27 to 1.35 against 1.41 to 1.47 seconds per million arcs) and uses less memory per arc. Arc counts are therefore a fair proxy, and if anything they favor the baseline.


Q4 – Exact search – We have not run a branch-and-bound study. It is the natural next step.

Branch-and-bound with decision diagrams computes a relaxed bound at every search node. A tighter bound at the same cost prunes more. The learned table applies unchanged to any subproblem. We have not run a branch-and-bound study and do not claim one, but it is the natural next step.


We hope these changes address your concerns and would be grateful if you would reconsider your score.

Thank you for the detailed responses and additional experiments. The clarifications regarding the role of the learned score, the dependence on the merge operator, and the relationship between arc counts and wall-clock time help address several of my concerns.

I also appreciate the authors' acknowledgment that the impact on end-to-end branch-and-bound performance remains unevaluated.

As I indicated in my review, this topic is somewhat outside my primary area of expertise, which is reflected in my low confidence score. Given these clarifications, I do not have further technical objections that I can assess with sufficient confidence, and I will leave the remaining specialized judgments to the AC and other reviewers with greater expertise in decision diagrams.

Thank you again for the constructive rebuttal.

Thank you for reading our responses, and for the kind words. We are glad they addressed your concerns.

We understand that you prefer to leave the specialized points to the AC and the other reviewers. If your own concerns are resolved, we would appreciate it if your score could reflect that.

Thank you again.

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

This paper studies how to improve lower bounds for discrete optimization problems using relaxed decision diagrams with the Traveling Salesman Problem with a Drone being the target example. Instead of focusing solely on the lower bound itself, the paper proposes directly optimizing a state-ranking policy against the lower bound produced by decision-diagram compilation. The paper argues that learning cost-to-go from relaxed diagrams introduces systematic bias, potentially producing poor rankings even when exact cost-to-go targets are available.

Critical strengths

The analysis of systematic bias in cost-to-go imitation is interesting, and the improvements over the tested baselines at matched computational cost are promising.

Critical weaknesses
  • The empirical claims in this paper are mostly limited to smaller problem sizes, which leads to doubts about the scalability and reliability of the approach. The paper admits that at larger sizes the performance advantage over root distance narrows when computational costs are matched. It seems like the experiments are incomplete at larger sizes (e.g., m=30) but the paper does not seem to clearly address why this is the case.

  • The paper is quite terse in its exposition, which impacts readability.

  • The novelty and generality seem to be somewhat limited. Existing strategies seem to serve as the foundation, but it is not demonstrated how the linear correction proposed in the paper extends beyond the TSP-D problem. The optimization procedure is also relatively heuristic, and its sensitivity to initialization and computational budget is not thoroughly investigated.

Questions for authors
  • What sensitivity does this approach have to the initialization of theta?
  • Where did the 120 number come from in the optimization strategy, what happens if it is increased?
  • Does this process expand beyond the TSP-D problem, and what evidence or speculation can be made on whether it can improve other problems?
3 comments
AuthorsOpenReview ↗

Response to Reviewer wtde

Thank you. Your three questions asked for experiments we had not run. All three now have results.


W1 – Scalability – The m=30m=30 cell is complete, and we added an m=40m=40 row.

The m=30m=30 cell is complete (General comment, item 5). On the narrowing, we agree and the paper now names two causes. The precompute grows faster than the compilation, and we charge it to the policy, so gains at matched arcs shrink while gains at equal width grow up to m=25m=25 (Sections 5.2 and 6.2). At fixed WW, the spare width also shrinks as mm grows (item 2). We added an m=40m=40 row at width 2048 with 30 instances. There, the m=25m{=}25-trained policy beats ridge by 4.92 and root distance at twice the width by 10.22, both on 30/30. That root distance uses more arcs than the policy (237M against 222M). The margin over ridge is not monotone in mm (3.54, 5.16, 5.75, 2.97 and 4.92 from m=15m=15 to 40). It is smallest at m=30m=30, where only 6% of the width is spare, against 18% at m=40m=40 after the step to W=2048W=2048. We state in Section 7 that we do not know where the advantage reaches zero.


W2 – Exposition – We rewrote Section 3.1 and added Section 6.7.

Section 3.1 is rewritten with Algorithm 1 and an example, and Section 2.2 now matches it. The new Section 3.1 states what the score decides, gives the allocation as Algorithm 1, and works a six-state example. The extra page holds the new Section 6.7, which reports in the main text what the score moves and the optimizer sensitivity. A new scope table (Table 11) lists what each claim needs. Details that repeated table values moved to the appendix, where every number remains. Beyond these, we refined the text throughout the paper to improve its readability and completeness.


W3, Q1 – Initialization – The ridge start is worth at most two tenths of a point.

From ridge, zero and random starts, the policy reaches 10.31, 10.48 and 10.37 at m=15m=15, all better than ridge (14.68) on 100/100 instances. The ridge start is worth at most two tenths of a point (Section 6.7, Table 4).


Q2 – 120 steps – We continued the runs to 480 steps and keep 120.

The budget was fixed before testing, but the paper did not justify it. The training logs show 95% of the final improvement by step 81 (median over 19 runs). We also continued the paper's five runs to 480 steps. The test gap is 10.65, 10.31, 10.31 and 10.04 at 60, 120, 240 and 480 steps. We keep 120 and report the rest in Appendix Q.


W3 – Step size – We ran the sweep. All five step sizes land within 0.33 points.

The sweep was in our protocol file but was never run, which was our mistake. It is now run with five seeds each. All five step sizes land within 0.33 points of the paper's result and beat ridge by at least 4.0 points.


W3 – Novelty – The policy and optimizer are simple on purpose.

The policy and optimizer are simple on purpose, so the training signal is the only thing that differs between methods. Our contribution is the bias in the usual imitation target, shown three ways (Sections 4.2 to 4.4), and evidence that the bound itself can replace that target.


Q3 – Beyond TSP-D – We added a scope table and a second problem.

See items 6 and 9 of the General comment. The bias arguments hold for any relaxed diagram with a tabular hh. On the asymmetric TSP the bias appears, but the learned correction adds nothing because that relaxation is already tight. We report this as the method's scope.


We hope these changes address your concerns and would be grateful if you would reconsider your score.

Reviewer_wtdeOpenReview ↗

After rebuttal

Many thanks to the authors for their response that helps address my concerns. Some of my concerns in terms of novelty and generality of the approach remains, but I will increase my score.

Thank you for reading our response and for raising your score. We appreciate it. Thank you again.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of changes and new results

We thank the reviewers. YZV5 and 3gNU asked the same question: if hh is constant inside a bucket, how can it decide which states of that bucket stay exact? It cannot, and the paper should have said so. hh decides how the spare width is shared between buckets. We rewrote Section 3.1 around this, added pseudocode and an example, and measured the effect. We also fixed the two overclaims 3gNU found, completed Table 2, reran with five seeds the one experiment that used a single seed, and refined the text throughout. All changes are in blue.


1 – What h does (YZV5 W1/Q1, 3gNU W1/Q1)

States merge only within their bucket (ic,it)(i_c,i_t), and each bucket is charged one node up front for its merged remainder. The compiler scans the layer's candidates by increasing fλ+hf_\lambda+h and keeps them exact until the width WW is used. Since hh is constant inside a bucket, it never reorders a bucket's members. Lowering hh for a bucket moves its states up the scan, so it wins more of the W−nkW-n_k spare nodes. Section 3.1 gives this as Algorithm 1 with a six-state example, and two regression tests check it.


2 – Measurement (Section 6.7, Appendix P)

We re-ran the allocation at every layer on the learned policy's candidates under other scores, over five seeds. Against root distance, the learned score keeps only 26%, 17% and 13% of the same exact states at m=15m=15, 20 and 25, and changes the node count of 29%, 21% and 13% of buckets. As a control, we shuffled the learned values across buckets within each layer. This changes the exact set at least as much, yet the bound is 3.6 to 5.1 points worse than root distance on every instance, for every seed. What matters is which buckets win. At fixed WW, the spare fraction (W−nk)/W(W-n_k)/W falls as mm grows, which helps explain the narrowing wtde noted.


3 – Contribution (iv)

Since hh acts only between buckets, per-state information can only reorder states inside a bucket. This fits the small gain of the per-state policy (0.34 points). Contribution (iv) now says so.


4 – Overclaims (3gNU W2/Q2)

We withdraw "the bias is proportional to merging". The inequality gives a direction, not a rate. Measured at m=8m=8 (Appendix S), a node's bias is negatively correlated with the number of states it absorbs at fixed depth. It comes from the relaxation below the node. We also replaced "stronger sources worsen imitation". Under the source's own multipliers the gap worsens (15.20 to 16.75), under the inference multipliers it improves (15.26 to 14.45). What grows is the multiplier mismatch.


5 – Table 2 (wtde W1)

The m=30m=30 cell now has five seeds (mean 28.25, within 0.69). It beats round 0 by 8.06 (100/100), ridge by 2.66 (88/100) and root distance by 12.36 (100/100). A new m=40m=40 row is added (width 2048, 30 instances). On the Tang and van Hoeve distribution (Section 6.6), now with five seeds, root distance still does not overtake the seed mean at five times its arcs in three of four configurations. Seeds vary more there, and Table 19 gives the ranges.


6 – Scope (YZV5 W2/Q2, wtde Q3)

A new table (Table 11) lists what each claim needs. The inequality holds for any relaxation, the min-aggregation bias for any tabular hh, the multiplier mismatch for Lagrangian bounds and the allocation result for bucketed compilers. The magnitudes are specific to TSP-D.


7 – Optimizer settings (wtde W3, Q1, Q2)

We ran the missing study (Section 6.7, Table 4, Appendix Q): three initializations, five step sizes and four step budgets, five seeds each, on the 100 test instances at m=15m=15. All sixteen settings, including the 60-step checkpoints, beat ridge by at least 3.8 points on at least 99/100 instances. Doubling the budget changes nothing, and quadrupling it gains 0.27 points. Within the tested range, the result does not depend on these settings.


8 – Arcs versus time (YZV5 Q3)

Seconds track arcs with R2=0.99R^2=0.99, at 1.26 to 1.58 seconds per million arcs for every method, precompute included (Appendix R). The learned policy is slightly cheaper per arc than root distance and uses less memory per arc.


9 – A second problem (wtde Q3, YZV5 W2)

Turning the drone off gives the asymmetric TSP on the same compiler, and we ran the full pipeline on it (Appendix T). The bias carries over: ridge is worse than the width-one table by 1.41 points on 99/100 instances, and round 0 still beats root distance. But the learned correction adds nothing, because this relaxation is already tight (4.6% gap). We report this as the limit of the method's scope.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.