PaperlayerView exact revision on arXiv

Source-linked AI summary

Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies

Giulia Zarpellon, Jason Jo, Andrea Lodi, Yoshua Bengio

arXiv:2002.05120v4cs.LGcs.AIstat.ML

TL;DR

Learning to branch has largely imitated strong branching and specialized to problem classes, while branching-variable selection is crucial to B&B. This paper uses candidate-variable representations and explicit tree-state gating in an imitation-learning framework; TreeGate improves test accuracy and reduces test-tree size relative to NoTree on heterogeneous MILPs.

  • Problem

    Most learned branching policies imitate strong branching and generalize to similar instances within a class, leaving systematic generalization across heterogeneous MILPs as a target.

    Source: §1 · p. 1

  • Method

    The framework imitation-learns branching from candidate-variable representations and uses a parameterized B&B tree state to gate those representations in TreeGate.

    Source: §1 · p. 2, §3.2 · p. 3, §3.3 · p. 4

  • Results

    27% less nodes on test instances for TreeGate than the best NoTree policy, alongside a 19% improvement in test accuracy over NoTree.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Tree-state parameterization supports learned branching across generic unseen MILP instances, where the evaluated GCNN models often fail to solve test instances.

    Source: §1 · p. 2

    The study evaluates generalization from a controlled training set rather than seeking to comprehensively outperform relpscost, tuned over thousands of proprietary instances.

    Source: §4 · p. 5

Abstract

from arXiv · show

Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs). Learning branching policies for MILP has become an active research area, with most works proposing to imitate the strong branching rule and specialize it to distinct classes of problems. We aim instead at learning a policy that generalizes across heterogeneous MILPs: our main hypothesis is that parameterizing the state of the B&B search tree can aid this type of generalization. We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching. Experiments on MILP benchmark instances clearly show the advantages of incorporating an explicit parameterization of the state of the search tree to modulate the branching decisions, in terms of both higher accuracy and smaller B&B trees. The resulting policies significantly outperform the current state-of-the-art method for "learning to branch" by effectively allowing generalization to generic unseen instances.

1 Introduction

Branching-variable selection is central to B&B, but learned policies have generally targeted generalization within problem classes. This paper uses search-tree state to pursue branching policies that generalize across heterogeneous MILPs.

1 Introduction

  • MILPs include discrete decision variables, and B&B solves them through exact tree search that branches on variable values and prunes regions using bounds.Modern MILP solvers rely on B&B as a fundamental component.Source: §1 · p. 1
  • BVS is crucial to B&B success, while most learned branching policies imitate strong branching and specialize to problem classes, with generalization often limited to similar instances.The GCNN approach frames BVS as classification of strong-branching decisions.Source: §1 · p. 1
  • The paper targets systematic generalization across heterogeneous MILPs without restricting problem class, formulation structure, or size, by parameterizing BVS with B&B search trees.The authors note that tree properties already inform successful heuristic branching rules.Source: §1 · pp. 1–2
  • The proposed framework represents candidate-variable roles and their changing input dimensions, then TreeGate uses tree state to gate candidate features across the policy network.NoTree is the baseline policy using candidate representations; TreeGate adds tree-state context as a learned control signal.Source: §1 · p. 2
  • The authors test imitation-learned policies on curated heterogeneous benchmark instances, using SCIP’s relpscost branching scheme as the expert.The framework is integrated with SCIP.Source: §1 · p. 2
  • TreeGate achieves 19% improvement in test accuracy and explores test trees with 27% less nodes than the best NoTree policy.Both learned policies compare well with state-of-the-art branching rules; GCNN models often fail to solve heterogeneous test instances and explore considerably larger trees.Source: §1 · p. 2

2 Background

B&B repeatedly branches on fractional variables and prunes subtrees using bounds. Branching rules score candidate variables using bound gains and other search-related signals.

2 Background

  • At a node, B&B relaxes integrality, branches on a fractional candidate when needed, and prunes subtrees by infeasibility, integrality, or bounds until global bounds converge.The selected variable creates two child nodes, and node selection chooses the next open leaf to explore.Source: §2 · p. 2
  • Branching rules typically choose a score-maximizing candidate; strong branching computes bound gains explicitly but is expensive, while pseudo-cost uses historical gains as a faster proxy.Reliability branching switches from strong branching to pseudo-cost when the latter is deemed reliable.Source: §2 · pp. 2–3
  • Hybrid branching combines pseudo-cost scores with measures of variables’ roles in inference and conflict clauses.It is one of several approaches that combine signals about candidate effectiveness across search components.Source: §2 · p. 3
  • Branching signals can reflect candidate effectiveness across search tasks, and their importance may change dynamically as the tree is explored.The paper’s approach aims to account for candidate roles and tree evolution when making BVS decisions.Source: §2 · p. 3

3 Parameterizing B&B Search Trees

The framework parameterizes branching variable selection with candidate-variable features and an explicit B&B tree state, then uses neural architectures to combine them. It investigates whether this representation supports systematic generalization across heterogeneous MILPs.

3 Parameterizing B&B Search Trees

  • The framework combines hand-crafted candidate-variable features and an explicit tree-state representation with neural architectures for learning branching variable selection.The tree state provides context for candidate selection as the search evolves.Source: §3 · p. 3

3.1 Hand-crafted Input Features

  • Candidate features describe bounds, solution values, and search participation; 61 tree-state features summarize the current node, tree growth and composition, bounds, scores, feasible solutions, and open nodes.The representations are not explicitly dependent on instance parameters, and fixed-length vectors accommodate candidate sets of varying sizes.Source: §3.1 · p. 3

3.2 Architectures to Model Branching

  • NoTree processes candidate features to score variables, while TreeGate embeds the tree state and uses it to gate candidate representations across network layers.The candidate-set dimension is handled as a batch dimension, allowing shared network parameters across branching sets of different sizes.Source: §3.2 · p. 3, Figure 2 · p. 4

3.3 Imitation Learning

  • The policies use behavioral cloning of SCIP’s relpscost branching decisions, with the parameterized candidate set and tree state approximating the solver state.The expert decisions are collected by rolling out SCIP on MILP instances.Source: §3.3 · p. 4

3.4 Systematic Generalization

  • The study targets systematic generalization by training in hand-crafted, tree-oriented features and evaluating policies on never-seen heterogeneous MILP instances.The authors hypothesize that TreeGate’s learned gating can compose tree-state and candidate-variable representations for flexible generalization.Source: §3.4 · p. 4

4 Experiments

The experiments assess whether tree-state parameterization helps branching policies generalize across heterogeneous MILPs, using a curated benchmark and both prediction and solver evaluations. TreeGate outperforms NoTree on test accuracy and explored tree size.

4 Experiments

  • The experiments target generalization from a controlled training set, not beating relpscost, which is tuned on thousands of proprietary solver instances.The authors frame comprehensive improvement over relpscost as impossible to guarantee in their research setting.Source: §4 · p. 5
  • The curated benchmark contains 27 heterogeneous problems from real-world MILP libraries, split into 19 training and 8 test instances with known optima and manageable search trees.The experiments deliberately use heterogeneous train/test instances and a restricted training set to test learning of higher-order branching factors rather than class-specific rules.Source: §4 · p. 5
  • Training data are diversified with solver-seed perturbations and random branching for the first k nodes; the latter augmentation is applied to training instances only.The random-branching runs use k ∈ {0, 1, 5, 10, 15}; test data use only seed-based augmentation from separate MILPs.Source: §4 · p. 5
  • Test instances have a longer tail of candidate-set sizes than training and validation, including sets over 300 candidates, testing generalization to larger, unseen branching sets.Training and validation candidate-set sizes are mostly in the [0, 50] range.Source: §4 · p. 6

4.1 Results

  • The study evaluates both test accuracy and solver roll-outs, selecting candidate policies by accuracy before comparing node counts over 135 executions.Solver performance is summarized by shifted geometric means of nodes, overall and for train and test instances.Source: §4.1 · p. 6
  • GCNN averages 15.28% top-1 and 44.16% top-5 test accuracy and explores around three times as many nodes across all instances as the learned policies.GCNN also hits the time limit on 7 instances, 24 times total; its multiple time limits hinder node-count comparisons.Source: §4.1 · p. 6
  • TreeGate explores 27% fewer nodes than NoTree on test instances; its best model improves NoTree’s top-1 (resp. top-5) test accuracy by 19% (resp. 7%).Across all instances, TreeGate explores 14.9% fewer nodes than NoTree; the best TreeGate model has 83.70% top-1 test accuracy.Source: §4.1 · p. 6
  • NoTree and TreeGate solve all instances within the one-hour limit like relpscost; relpscost still produces the smallest trees, though a learned policy beats its fair node count on 11 of 27 instances.The fair node count accounts for side-effects of strong-branching-like explorations.Source: §4.1 · p. 6

5 Related Work

Prior learning-to-branch work includes score prediction, ranking, and classification approaches, often specialized to problem classes or static MILP features. Other studies address node selection or action-space representations in reinforcement learning.

5 Related Work

  • Earlier learning-to-branch methods predict strong-branching scores, rank their associated decisions, or specialize models to particular combinatorial classes; Gasse et al. use GCNN classification of strong-branching decisions.The cited approaches often use static features, whereas this paper aims to capture branching’s temporal and dynamic behavior.Source: §5 · pp. 6–7
  • Related B&B work also learns node-selection policies using imitation learning or reinforcement learning, including a multi-armed-bandit model of tree search.He, Daume III, and Eisner and Song et al. study imitation-learning approaches; Sabharwal, Samulowitz, and Reddy use reinforcement learning.Source: §5 · p. 7
  • Feature gating and top-down modulation have precedents in deep learning, while the branching action set here changes dynamically with the candidate-set size.The paper contrasts its changing action space with related work on static action-space representations.Source: §5 · p. 7

6 Conclusions and Future Directions

The paper concludes that parameterizing candidate variables and B&B search trees helps branching policies generalize across heterogeneous MILPs. It identifies reinforcement-learning extensions as a direction for further study.

6 Conclusions and Future Directions

  • TreeGate’s tree-state context improves test accuracy and reduces explored B&B tree sizes, supporting generalization across heterogeneous problems.The authors report that GCNN alone does not generalize to new instances without training analogs.Source: §6 · p. 7
  • The approach combines candidate-variable and search-tree parameterizations with a DNN architecture that handles candidate sets of varying size.The tree-state data are not currently exploited by state-of-the-art MILP solvers, according to the authors.Source: §6 · p. 7
  • Future work could extend explicit B&B tree-state parameterization to reinforcement learning, including state representations and branching rewards.The paper also points to further experimentation with imitation-learning methods for branching.Source: §6 · p. 7

A Dataset curation

The dataset is curated from standard MILP benchmark libraries and the Mittelmann collection to support fair branching-policy comparisons. It includes 27 heterogeneous problems divided into training and test sets.

A Dataset curation

  • The curation selects instances with known optimal values and relatively contained search trees, excluding problems solved at the root node.Roll-outs use SCIP’s default relpscost and random branching, with a one-hour time limit, to assess instances before selection.Source: A Dataset curation · p. 9
  • The final dataset contains 19 training and 8 test instances, with different constraint types and structures.The 27 problems come from MIPLIB 3, 2010 and 2017, and the Mittelmann collection.Source: A Dataset curation · p. 9

B Hand-crafted input features

The section describes candidate-variable and tree-state features, alongside normalization and summary functions used to make solver inputs comparable. It also identifies the curated dataset table’s instance-level descriptors.

B Hand-crafted input features

  • Candidate-variable and tree-state features are designed to represent variables’ roles in the search and its dynamic evolution.Table 10 groups the hand-crafted features and describes them by the SCIP API functions used to compute them.Source: B Hand-crafted input features · p. 9
  • Table 4 describes each curated instance by variable count and types, constraint count, train/test split, and library of origin.The text notes that the problems have different constraint types and structures.Source: Table 4 · p. 10
  • Branching scores are computed for candidate variables with respect to an average score using the formula implemented in SCIP relpscost.The section also points readers to SCIP’s online documentation for further feature information.Source: B Hand-crafted input features · p. 10
  • Input values spanning different ranges are normalized, while relative-distance and relative-position measures compare commensurable quantities such as upper and lower bounds.The described normalization also uses min, max, mean, standard deviation, and the 25–75% quantiles q1 and q3.Source: B Hand-crafted input features · p. 10

C Solver setting and hardware

The experiments use SCIP 6.0.1 with a one-hour limit and specified solver settings; the GCNN benchmark uses adjusted batch sizes and a separate hardware setup.

C Solver setting and hardware

  • SCIP 6.0.1 evaluations use a one-hour limit, retain presolve and cut separation, and disable primal heuristics and reoptimization.Additional settings control strong-branching side effects, and the known optimal solution is provided as a cutoff.Source: C Solver setting and hardware · p. 10
  • The GCNN benchmark uses the described SCIP setting rather than Gasse et al.’s original setting, with smaller training and test batch sizes to avoid memory issues.The state buffer is deactivated at evaluation because cuts are present in the solver setting.Source: C Solver setting and hardware · p. 10
  • The IL experiments, SCIP branching-rule evaluations, and GCNN benchmark ran on separately specified CPU/GPU hardware.Table 5 summarizes the SCIP parametric setting.Source: C Solver setting and hardware · p. 10, Table 5 · p. 11

D Data augmentation

The authors diversify the dataset through random seeds and initial random branchings. Both approaches appear effective, with measured variability in node counts across runs and branching choices.

D Data augmentation

  • Dataset augmentation uses different random seeds and k random branchings at the top of the tree before switching to SCIP’s default branching rule.The effects are quantified using coefficients of variation of performance measurements.Source: D Data augmentation · p. 11
  • 0.03–1.70 is the observed range of node-count variability coefficients across five runs, with most instances at least 0.20; training-set variability across k values ranges 0.07–0.79.The authors conclude that both random-seed runs and random branchings at the top of the tree appear effective for dataset diversification.Source: D Data augmentation · p. 11
  • Explored tree size generally grows with k, although the opposite occurs in a few cases.The training-set variability of shifted geometric mean node counts across k values supports the authors’ assessment that initial random branchings diversify the data.Source: D Data augmentation · p. 11

E IL optimization dynamics

TreeGate outperforms NoTree on aggregate test accuracy and B&B rollout nodes, though instance-level comparisons remain mixed. Batch normalization proved unreliable for NoTree in this setting and was omitted from the reported framework.

E IL optimization dynamics

  • TreeGate is reported to improve test accuracy over the NoTree policy on both top-1 and top-5 metrics, although the cited passage does not state the size of either improvement.Source: E IL optimization dynamics · p. 11
  • TreeGate optimization is better conditioned than NoTree, although their top-5 validation accuracy curves are quite close.Figure 3 shows training loss and Figure 4 shows validation top-1 and top-5 accuracy for the best policies.Source: E IL optimization dynamics · p. 11, Figure 3 · p. 13, Figure 4 · p. 13
  • Candidate-set sizes range from fewer than 10 to over 300, leaving batch-normalization reliability uncertain for these variable batch sizes.The authors note that batch normalization can struggle in small-batch settings.Source: E IL optimization dynamics · p. 11
  • NoTree+BN either showed wildly varying validation accuracy or hit the 1h limit on neos-476283, exploring 66170.66 nodes; BN was omitted and local-minima effects left for future work.The time-limit case occurred with hidden size h = 64 and LR = 0.001 across all five runs.Source: E IL optimization dynamics · p. 11
  • TreeGate is at least 10% better on 10 instances and at least 25% better on 8, while NoTree is better on 6 and 3, respectively.The source reports that overall tree-size reductions are more pronounced for TreeGate.Source: E IL optimization dynamics · p. 11, Table 9 · p. 14
  • 83.08 ± 0.86 vs 65.90 ± 1.6 top-1 test accuracy, and 1126.97 ± 46.85 vs 1336.12 ± 73.32 B&B rollout nodes, favor TreeGate over NoTree.Table 7 reports the best trained models; these averages cover the reported models and rollout nodes.Source: E IL optimization dynamics · p. 11, Table 7 · p. 12

Related papers

Loading 2002.05120v4…