Learning to Search in Branch and Bound Algorithms

He He, Hal Daumé Iii, Jason EisnerNeurIPS 2014 · OpenReview

Introduction

Branch-and-bound (B&B) is the workhorse of combinatorial optimization, widely used in applications ranging from logistics and scheduling to structured prediction in machine learning. However, the efficiency of B&B relies heavily on node ordering: deciding which subproblem to solve next and which ones to discard (prune).

Traditionally, these strategies are hand-crafted heuristics designed by domain experts. These heuristics are often "static"—they do not adapt to the specific structure of a new problem family or the current state of the search. This paper introduces a method to automatically learn search heuristics for B&B algorithms using imitation learning. By training a model to mimic an "omniscient" oracle, the authors developed adaptive node selection and pruning policies that can solve Mixed Integer Programming (MIP) problems significantly faster than standard solvers while maintaining high solution quality.

Methods: Imitation Learning for B&B

The authors frame B&B search as a sequential decision-making process and use Imitation Learning to solve it. Instead of relying on trial-and-error manual tuning, the system learns from experience.

  1. The Oracle: To train the system, the authors define an "ideal" oracle that already knows the optimal solution. This oracle only expands nodes that lead directly to that solution and prunes everything else.
  2. Two-Policy System: The framework learns two distinct policies to guide the search:
  3. Node Selection Policy: A ranking function that decides which node in the active queue is most promising.
  4. Node Pruning Policy: A binary classifier that decides if a popped node is worth expanding or if it should be discarded to save time.
Flowchart of the modified Branch-and-Bound process integrating the learned ranking and pruning policies.
  1. DAgger (Dataset Aggregation): The policies are trained using the DAgger algorithm. DAgger is crucial because it exposes the learner to states it might actually encounter at test time (including its own mistakes), rather than just the "perfect" path the oracle takes.
  2. Features: The model uses a variety of features, including node-specific data (lower bounds, depth), branching data (pseudocosts), and global tree statistics (integrality gap, number of solutions found).

Key Insights and Ideas

The approach was evaluated on four Mixed Integer Linear Programming (MILP) libraries: MIK (knapsack constraints), Regions & Hybrid (combinatorial auction winner determination), and CORLAT (real-world wildlife corridor construction).

  • Pruning is the Powerhouse: An ablation study revealed that the pruning policy contributes more to speedups than the selection policy. By aggressively discarding unpromising subtrees, the algorithm avoids massive amounts of redundant work.
  • Adaptivity Matters: The search strategy learns to behave differently at different stages. For example, it might act like a Depth-First Search (DFS) early on to find a feasible solution quickly, then switch strategies as the search tree grows deeper.
  • The "Hot Diagonal": A cross-generalization analysis—testing a policy trained on one dataset against another—showed that policies are highly specialized. A policy trained on "knapsack" problems performs poorly on "wildlife corridor" problems, confirming that "one-size-fits-all" heuristics are suboptimal.
  • Imitation as Optimization: Instead of trying to prove optimality (which is slow), the authors focused on finding "good enough" solutions quickly. This shift in priority allows for much more aggressive pruning.

Key Results

The researchers compared their "Learning to Search" (L2S) approach against SCIP (a top-tier open-source solver) and Gurobi (a leading commercial solver).

Performance comparison of the proposed method against SCIP and Gurobi across four datasets.
  • Speed: L2S achieved speedups of up to 4.7x compared to SCIP (specifically on the MIK dataset).
  • Solution Quality: On the CORLAT dataset, L2S found better solutions faster than both SCIP and Gurobi when given the same node/time limits.
  • Efficiency: The learned policies are computationally "cheap." The time spent making decisions (inference) accounted for less than 0.05% of the total runtime.

Limitations and Future Work

While highly effective, the method requires a set of "solved" instances for training. While these are often available in industrial settings where similar problems are solved daily, it makes the tool less "plug-and-play" for entirely new problem types. Furthermore, the current approach prioritizes finding good solutions quickly over providing a rigorous mathematical proof of optimality. For applications requiring a certificate of absolute optimality, this method might need to be paired with more conservative pruning.

Future directions suggested by the authors include incorporating a "time budget" directly into the model to allow users to explicitly trade off solution quality for search time, and using multi-task learning to help policies generalize better across different types of problems.

Summary updated

Abstract

Branch-and-bound is a widely used method in combinatorial optimization, including mixed integer programming, structured prediction and MAP inference. While most work has been focused on developing problem-specific techniques, little is known about how to systematically design the node searching strategy on a branch-and-bound tree. We address the key challenge of learning an adaptive node searching order for any class of problem solvable by branch-and-bound. Our strategies are learned by imitation learning. We apply our algorithm to linear programming based branch-and-bound for solving mixed integer programs (MIP). We compare our method with one of the fastest open-source solvers, SCIP; and a very efficient commercial solver, Gurobi. We demonstrate that our approach achieves better solutions faster on four MIP libraries.
BibTeX
@inproceedings{he2014learning,
  author = {He He and Hal Daumé III and Jason Eisner},
  title = {{Learning to Search in Branch and Bound Algorithms}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=Bk4k7dW_ZB},
}
Figure