- 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
-
The labeling procedure is carefully specified. The supervision signal is well defined.
-
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
- The gains are not always due to cost supervision. Proposal support and multi-action targets explain much of the improvement on some families.
- 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
Thanks for your reply. I appreciate your additional experiments and maintain my positive rating.
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⋆-aware component, re-collected labels with the same seeds, budget and cap, and retrained each target (Table 9, lines 897-913).
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⋆-free; the cutoff remains z⋆. On MKP all admissible actions fit within eight proposals, so optimum guidance cannot change support. On CA, SB-uniform uses no x⋆ 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, ρ=μ (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).
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.5S to S (S: 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× to 10× the behavior proof's LP solves retains 45% of the training states and changes Hard/Soft performance point estimates by under 1%. At 5×, 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.
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.