Hindsight Supervision for Learning to Branch

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.