acceptodds
Under review as a conference paper at ICLR 2027

Hindsight Supervision for Learning to Branch

Abstract

Learned branching rules for mixed-integer programming are usually trained by imitation: a network is fit to the choices of strong branching, whose score for a candidate is the immediate improvement in its children's LP bounds. That score is a one-step proxy. It ignores how the subtrees below the children are actually solved, so imitating it optimizes agreement with a heuristic rather than the size of the proof, and the label carries no information about how much each alternative would have cost. We instead supervise branching with the quantity of interest itself. On solved training instances, the known optimum fixes the objective cutoff, and each candidate branch is followed by a fixed continuation rule until its subtree is complete or a node budget is reached; completed rollouts give exact proof costs and interrupted rollouts give certified lower bounds. These observations define hard, soft, and set-valued training targets. A performance-difference identity for finite, subtree-local proof trees shows when such local improvements compose into a smaller proof, and a simple counterexample shows why a stateful solver calls for closed-loop evaluation instead. Controlled experiments on three MILP families show that hindsight targets reduce held-out tree size relative to matched behavior cloning on every family, by up to 45%, and information-source controls locate the origin of the gain: correct cost-to-action assignment on multidimensional knapsack, a cheap multi-action target on combinatorial auctions, and the composition of the proposal set on set cover. Hindsight targets also beat a compute-matched Branch Ranking collector given the same cutoff, transfer to a harder auction cohort, and cut solving time by 7% over behavior cloning in a practical SCIP configuration that receives no test optimum.

Primary area:
optimization
Keywords:
Branch-and-Bound, MILP, Branching Rules, Learning to Branch

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_P24aOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes hindsight supervision for learning branching rules in MILP. From solved training instances, it restores a common solver state, evaluates candidate branches under a fixed optimal cutoff and continuation policy, and uses completed rollouts as exact proof costs or interrupted rollouts as certified lower bounds. The paper develops hard, soft, and set/ranking targets, gives a proof-tree performance-difference identity under subtree-local dynamics, and discusses why stateful solvers require closed-loop evaluation. Experiments on multidimensional knapsack, combinatorial auction, and set-cover instances show consistent reductions in held-out tree size over matched behavior cloning, improvements over a compute-matched Branch Ranking baseline, transfer to larger auction instances, and a modest wall-clock improvement in one practical SCIP configuration.

Critical strengths
  1. The labeling procedure is carefully specified. The supervision signal is well defined.

  2. The attribution experiments are unusually useful. The controls distinguish cost assignment from proposal support and multi-action supervision, and the paper is appropriately honest that the dominant source of improvement differs across instance families.

Critical weaknesses
  1. The gains are not always due to cost supervision. Proposal support and multi-action targets explain much of the improvement on some families.
  2. The experiments are mostly on synthetic/custom settings; practical validation is limited to one SCIP configuration and a small number of instance families.
Questions for authors
  • How much of the improvement remains when proposal generation does not use the training optimum?
  • How sensitive are the results to the continuation policy and rollout budget?
2 comments
AuthorsOpenReview ↗

Response by Authors

We thank the reviewer and apologize for the delayed response while completing the checks and additional experiments. See also our general comment on paper update. All references below are to the revised PDF.

Ratios are paired closed-loop comparisons (lower is better); brackets give 95% intervals.

How much remains without optimum-guided proposals?

On set cover, where proposals matter most, we removed the x⋆x^\star-aware component, re-collected labels with the same seeds, budget and cap, and retrained each target (Table 9, lines 897-913).

Targetx⋆x^\star-free / BCx⋆x^\star-free / full
Proposal-uniform0.921 [0.733, 1.096]1.062 [0.989, 1.145]
Soft0.879 [0.717, 0.979]1.028 [1.001, 1.073]
Set+rank0.898 [0.743, 0.995]1.023 [1.006, 1.044]

Soft and Set+rank retain reductions of about 12% and 10% over BC; optimum guidance adds 2-3%. Proposal-uniform still beats SB-uniform, but its interval against BC includes one.

Only proposals are x⋆x^\star-free; the cutoff remains z⋆z^\star. On MKP all admissible actions fit within eight proposals, so optimum guidance cannot change support. On CA, SB-uniform uses no x⋆x^\star in target construction and already provides most of the gain; the full mixture has no detectable advantage for a uniform target.

How sensitive are results to the continuation policy?

The main continuation is the behavior rule, ρ=μ\rho=\mu (lines 154-155). We relabeled the same MKP S1 behavior trees under two alternative rules, re-evaluated the behavior action under each, and retrained policies (Table 12, lines 956-981).

Rule (main: SB, 15 probes)Winner agreementHard, relabeled / mainSoft, relabeled / main
SB, 5 probes99.9%1.001 [0.994, 1.009]1.003 [0.997, 1.009]
Cut-aware83.3%1.008 [1.003, 1.013]1.001 [0.990, 1.016]

Performance point estimates change by under 1%. Cut-aware labels cause a small detectable loss for Hard, but both targets retain their advantage over BC. These tests concern MKP S1; relabeling on CA and set cover has not been run because it is more expensive.

How sensitive are results to the rollout budget?

Two budgets matter. Lowering the per-rollout cap from 1.5S1.5S to SS (SS: reference subtree size), with other settings fixed, worsens Set+rank trained on exact pairs by 24% on set cover, where completed costs of inferior alternatives are lost. No degradation is detected on CA (Table 10, lines 921-927).

For the total budget, we re-collected MKP S1 and retrained BC, Hard and Soft (Table 13, lines 971-1000). Halving the budget from 20×20\times to 10×10\times the behavior proof's LP solves retains 45% of the training states and changes Hard/Soft performance point estimates by under 1%. At 5×5\times, about four labeled states per training instance remain; every policy, BC included, performs worse than full-budget BC, consistent with a training-set-size limitation.

Are gains due to costs or support?

Both, with different dominant sources by family (Figure 2; Table 8, lines 870-886). States and encoder are matched within each comparison; cost-assignment contrasts also preserve support and target concentration.

ContrastCASet coverMKP S1
SB-uniform / BC0.8031.9811.370
Proposal-uniform / SB-uniform1.0190.4380.789
Hard / Random one-hot0.832not run0.811
Soft / Cost-shuffled0.9830.9470.839

These contrasts test multi-action support, proposal/completion support, and hard/soft cost assignment, respectively (Section 4.3). CA benefits mainly from multi-action supervision, with an additional benefit from identifying the winner; set cover from proposal composition; MKP from correct cost assignment, while uniform targets hurt.

In practical SCIP, Soft is 5% faster than SB-uniform (lines 428-431). This measures hindsight labels as a whole, not cost assignment alone, because support also differs.

How broad is practical validation?

The main families are generated, and practical timing uses one SCIP configuration. Proof-only SCIP covers MKP at three sizes (Tables 1 and 4). Practical SCIP receives no test optimum: on CA, Soft is 6% faster than BC and 18% faster than the default branching rule relpscost at training size (Table 5, lines 437-447), and 13% faster than relpscost on a 1.5x larger held-out cohort (Table 19). Against BC on that larger cohort, the additional speedup is not statistically resolved (0.946 [0.884, 1.011]). Presolve and restarts are off to preserve the policy's variable space (lines 452-454). Appendix F adds an exploratory test on heterogeneous MILP-S instances.

Thanks for your reply. I appreciate your additional experiments and maintain my positive rating.

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

In the branch-and-bound method of solving the MILP, the key decision is which variable to split (branch) on at each step. The paper's motivation is that strong branching (i.e., selecting the branching variable based on maximum gain in the immediate next step) in MILP solving looks only one step ahead. Therefore, training the network with this heuristic may not make the final tree small. The authors train the network on problems that are already solved, so the true optimum is known. The labelling pipeline restores a common solver state, evaluates every candidate branch under the same optimal cutoff and continuation rule, and records each outcome as an exact node count or a certified lower bound. If a rollout runs too long, they stop it. They record at least n nodes, which is a guaranteed lower bound instead of a guess. Then the authors trained the network with several kinds of labels: hard (pick the cheapest candidate), soft (assign probability over candidates, with more weight on cheaper ones), and set-and-ranking targets (use certified orderings). In an idealised solver where subtrees don’t affect each other, authors prove that if every local choice is at least as good as the baseline, the whole tree is no worse. They also show with a small example that real solvers break this assumption, because shared statistics can make a locally good choice hurt later. Finally, the source of the gain is identified from a) the measured costs themselves, b) simply showing the network several good options instead of one, or c) which candidates were put on the menu.

Critical strengths

The positive points about the paper are a) the labels measure actual tree size, not a one-step proxy, b) each label is either an exact count or a certified lower bound, c) it clearly shows that the answer differs by problem family, which is a useful lesson for the field, d) results are represented with statistics and are reproducible, and d) there is no deployment cost, as the optimum and rollouts are only used offline.

Critical weaknesses

The negative points about the paper are: a) the problem sizes used are small, b) the real-world speedups are small, c) the solver model used is violated by the real solvers, d) labelling is expensive, and d) novelty is incremental.

Questions for authors

The detailed comments are given below.

  1. The problem sizes used are small. Knapsack has 32–56 items, and set cover has 70×140. Many trees have only hundreds of nodes. It’s unclear whether the gains survive on hard, industrial-size problems.
  2. The real-world speedups are small. Solve times are around 1 second, so 7% is about 0.2 s per instance.
  3. The theoretical proof is not valid for real applications. The guarantee needs a solver model that real solvers violate, so it is mainly motivation.
  4. For application, solved training instances plus many rollouts, about 36.7 CPU-hours in total are required for the auction family alone. Clearly, the labelling is expensive, which restricts the application of the developed methodology.
  5. The novelty of the work is incremental, as rollout-based labels (Branch Ranking, lifted branching) and the fixed optimal cutoff already exist. The contribution is mainly the careful combination and the evaluation.
1 comment
AuthorsOpenReview ↗

Response by Authors

We thank the reviewer for the detailed review. We apologize for the delayed response: it took us time to re-evaluate the experimental setup and to run the experiments. Please see the updated version of the PDF and the general comment on the updated paper for details; line numbers below refer to the updated PDF.

1. Problem size

Our experiments do not yet establish industrial-scale performance, but the results provide encouraging evidence beyond the smallest tested instances. On MKP, the gains over BC are larger at both larger sizes (Table 4, lines 417–423), while frozen CA policies retain their advantage on 1.5× larger held-out instances without retraining (lines 408–410).

The moderate problem sizes reflect our experimental design: we aim to obtain mostly completed counterfactual proof costs within a fixed labeling budget, enabling controlled comparisons on matched states. The practical SCIP evaluation also disables presolve and restarts to preserve the learned policy's variable space, while the heterogeneous MILP-S experiment remains exploratory. These are limitations of the current validation, not evidence that the method cannot benefit larger, industrial-scale problems.

2. Magnitude and relevance of the practical speedups

Here, the absolute saving is small Its role is not to show a large speedup but to test whether the effect measured in a controlled fixed-cutoff environment survives in SCIP with an evolving incumbent, cuts, heuristics and conflicts, without the test optimum, inference included. It does, with less search work than BC (Table 17).

The two baselines answer different questions: the comparison with BC isolates what the supervision adds, while the larger gain over SCIP's default rule also contains the saving from replacing strong-branching probes, which BC already obtains. On a harder cohort with five times longer solves, the gain over the default rule remains; against BC the point estimate is also favorable (Table 19).

3. Scope and practical role of the theoretical guarantee

We agree that real solvers could violate Assumption 1, and the paper does not use Theorem 1 as a guarantee for SCIP. Three statements are separate:

  • The theorem: under its assumptions, local advantages at the states the learned policy visits add up to the change of the whole proof tree.
  • Its limit: shared solver state can break this composition; Section 5 gives a counterexample and calls the labels a training signal, not a guarantee (lines 278-286).
  • The practical claim: improvement in SCIP is established by closed-loop experiments, never derived from the theorem (Table 1).

Label validity needs no such assumption: from a fixed snapshot under a fixed continuation rule, a completed rollout gives its exact cost and an interrupted one a lower bound (Proposition 4, line 666). The theorem's role is to say what a label must capture and why stateful solvers need closed-loop evaluation.

4. Offline labeling cost and applicability

The offline cost makes repeated solving within one instance family the relevant setting; amortization depends on the number and difficulty of later solves. The corrected CA label generation costs is 24.6 CPU-hours including optimal solves (see general response); training is reported separately and is small (Appendix E.4, lines 1167-1174). Three results put the cost in context:

  • Frozen-policy transfer to 300x1200 CA requires no labeling at that size.
  • On MKP S1, halving the collection budget changes Hard/Soft closed-loop performance point estimates by less than 1% (Table 13, lines 971-1000).
  • On CA, SB-uniform uses no rollout costs to construct its target and, on the same recorded states, gives most of the node reduction; measured costs are essential on MKP (Figure 2).

5. Contribution beyond existing rollout-based methods

Rollouts and the optimal cutoff are not claimed as new individually; Section 2 credits Branch Ranking, lifted branching, and the optimal-objective cutoff (lines 91-96). Our contribution is an offline proof-cost supervision pipeline with a theoretical analysis and matched empirical validation:

  • Offline labeling: each proposed action is evaluated from the same restored solver state under a fixed optimal cutoff and continuation rule. Exact costs and certified lower bounds define hard, soft, and set-and-ranking targets without estimating unfinished tree sizes (Sections 3-4).
  • Theoretical foundation: the performance-difference identity and headroom-versus-error bound specify when local improvements compose; the counterexample shows the limits in stateful solvers (Section 5).
  • Attribution: matched controls separate multi-action support, proposal composition, and cost assignment, identifying the dominant source on each family (Section 4.3, Figure 2).

Giving Branch Ranking the same cutoff improves it; Soft improves a further 2% under the same budget (Table 3). This compares complete pipelines, not losses on identical observations.

Reviewer_1J3YOpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies hindsight supervision for learning branching policies in mixed-integer programming. Instead of imitating strong branching scores, the authors evaluate alternative branching actions using fixed-optimum-cutoff counterfactual rollouts and construct hard, soft, and set-valued supervision targets from exact or censored proof costs. The paper also presents a performance-difference identity for subtree-local proof trees and conducts extensive information-source ablations across three MILP families.

Critical strengths

The problem is well motivated, and using long-horizon proof costs provides a meaningful alternative to one-step strong-branching supervision.

The information-source controls are particularly valuable. They reveal that the observed improvements have different origins across problem families, including correct cost assignment, multi-action supervision, and proposal-set composition.

The theoretical analysis carefully distinguishes subtree-local guarantees from stateful solver behavior.

The experimental evaluation includes matched encoders, multiple seeds, paired confidence intervals, rollout-based baselines, and practical SCIP measurements.

Critical weaknesses

I have no critical concerns for this paper.

Questions for authors

N/A

1 comment
AuthorsOpenReview ↗

Response by Authors

We thank the reviewer for the positive assessment and for highlighting the information-source controls and the distinction between subtree-local guarantees and stateful solver behavior.

We have revised the presentation to make these aspects easier to follow. Table 1 (lines 302–310) explicitly separates the controlled B&B, proof-only SCIP, and practical SCIP regimes. The targets and controls now have descriptive names throughout; Section 4.3 defines the controls, and Figure 2 summarizes their findings across the three families.

We have also expanded the set-cover ablation without optimum-guided proposals and added continuation-policy and collection-budget sensitivity experiments (Appendices D.1–D.2).

The accompanying general comment on paper update 1 summarizes the experimental corrections and updates. All references above refer to the revised PDF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.