PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Branch

Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, Ellen Vitercik

arXiv:1803.10150v2cs.AIcs.DS

TL;DR

Tree-search performance depends strongly on branching choices, yet no theory identifies a universally optimal strategy. The paper learns distribution-specific mixtures of branching rules from samples and provides sample-complexity guarantees for this configuration problem. Experiments and theory show substantial tree-size blowups under distribution mismatch, including exponential blowup, while learned mixtures can achieve nearly optimal expected cost.

  • Problem

    Branching parameters can dramatically affect tree size, but no universally optimal strategy or prior sample-complexity theory for tree-search configuration is available.

  • Method

    The paper adaptively partitions parameter space into regions with invariant training-set tree sizes and uses empirical risk minimization to learn a branching-rule mixture.

  • Results

    Distribution mismatch can cause substantial tree-size blowups, including exponential blowup, while empirical costs of mixtures can be close to expected costs with few samples.

  • Takeaways & Limitations

    Learning branching policies for the instance distribution at hand is both theoretically analyzable and practically beneficial for reducing search-tree size.

  • Takeaways & Limitations

    The analysis assumes a cost cap κ and instances over n binary variables, while some scoring-rule definitions can be too slow to compute exactly.

Abstract

from arXiv · show

Tree search algorithms, such as branch-and-bound, are the most widely used tools for solving combinatorial and nonconvex problems. For example, they are the foremost method for solving (mixed) integer programs and constraint satisfaction problems. Tree search algorithms recursively partition the search space to find an optimal solution. In order to keep the tree size small, it is crucial to carefully decide, when expanding a tree node, which question (typically variable) to branch on at that node in order to partition the remaining space. Numerous partitioning techniques (e.g., variable selection) have been proposed, but there is no theory describing which technique is optimal. We show how to use machine learning to determine an optimal weighting of any set of partitioning procedures for the instance distribution at hand using samples from the distribution. We provide the first sample complexity guarantees for tree search algorithm configuration. These guarantees bound the number of samples sufficient to ensure that the empirical performance of an algorithm over the samples nearly matches its expected performance on the unknown instance distribution. This thorough theoretical investigation naturally gives rise to our learning algorithm. Via experiments, we show that learning an optimal weighting of partitioning procedures can dramatically reduce tree size, and we prove that this reduction can even be exponential. Through theory and experiments, we show that learning to branch is both practical and hugely beneficial.

1 Introduction

The paper frames branching-policy selection as a difficult algorithm-configuration problem and learns policies tailored to distributions of problem instances. It combines adaptive empirical optimization with sample-complexity guarantees and reports substantial distribution-dependent tree-size differences.

  • Motivation: Branch-and-bound partitions feasible regions by adding variable constraints, but no universally optimal variable-selection strategy is known.Finding an approximately optimal branching variable can be NP-hard even at the root.
  • Approach: The paper learns a variable-selection policy from samples so expected search-tree size is minimized for a given application-domain distribution.The application domain is modeled as an unknown distribution over problem instances with sample access.
  • Approach: Adaptive parameter-space partitioning identifies regions with invariant training-set tree sizes and returns the empirically optimal parameter.This procedure performs empirical risk minimization, while data-independent discretization can fail badly.
  • Theory: Small parameter changes can cause discontinuous changes in tree size, preventing standard function-class complexity arguments from directly applying.The analysis therefore tracks how parameters affect each step of the search procedure.
  • Theory: The paper gives the first sample-complexity guarantees for automated tree-search configuration, with worst-case bounds growing quadratically in instance size.The bounds establish that relatively few samples can suffice despite the complexity of the algorithms studied.
  • Evidence: Experiments show that parameters effective for one problem distribution can produce dramatic tree-size blowups on another, while data-dependent guarantees can reduce sample requirements for well-structured data.The paper also situates its contribution relative to prior experimental and theoretical work lacking comparable guarantees.

2 Tree search

Tree search recursively partitions optimization problems and prunes subproblems using feasibility and bound information. In branch-and-bound, node and variable selection policies determine the search order and can strongly affect tree size.

  • Tree search: Tree search partitions a feasible set into subproblems and organizes those partitions in a tree whose root is the original problem.The framework applies broadly, including mixed integer linear programs and constraint satisfaction problems.
  • Branch-and-bound: Branch-and-bound uses lower and upper bounds to prune infeasible subproblems or subproblems that cannot improve the best known feasible solution.For MILPs, upper bounds come from linear-programming relaxations.
  • Branch-and-bound: At each iteration, branch-and-bound selects an unfathomed leaf, chooses a variable, and creates child MILPs by imposing xi = 1 and xi = 0.The algorithm terminates when every leaf has been fathomed and returns the best known feasible solution.
  • Node selection: The best-bound node policy selects the unfathomed leaf with the largest LP-relaxation objective value, whereas depth-first search follows tree order.These policies control which leaf is expanded next, independently of the variable-selection rule.
  • Example: In the illustrative MILP, branch-and-bound explores the pink node after comparing child LP objectives of 136 and 135, then compares the orange node against the pink node’s children.The example uses the best-bound policy for node selection.
  • Variable selection: A score-based variable-selection policy branches on the unbranched variable with the maximum score at the selected leaf.Common scores include most fractional, linear, and product rules; the linear rule parameter µ balances optimistic and pessimistic branching.

3 Guarantees for data-driven learning to branch

The paper formalizes learning convex combinations of branching scoring rules from sampled MILP instances, while establishing impossibility results for data-independent parameter discretization. It develops sample-complexity guarantees and an adaptive learning approach whose guarantees depend on scoring-rule structure or bounded tree size.

  • Problem statement: The goal is to learn a convex combination of variable-selection scoring rules that minimizes expected tree-search cost over a distribution of MILPs.The remaining tree-search components are fixed, and the cost function is assumed to be tree-constant and capped by κ.
  • Impossibility results: Any data-independent discretization of [0, 1] can be defeated by distributions where every discretized parameter has exponential expected tree size, although infinitely many parameters achieve O(1) cost.This demonstrates that parameter regions producing good search trees may be missed by fixed grids.
  • Impossibility results: For every threshold µ* ∈ (0, 1), constructed MILP families yield O(1)-node trees below the threshold and 2^(n−4)/2-node trees above it.The construction combines a hard Jeroslow-style instance with an easy three-variable instance, so branching order determines whether the search terminates quickly or explores the large subproblem.
  • Sample complexity guarantees: For two path-wise scoring rules, each instance has at most 2n(n−1)/2^n intervals over [0, 1] within which the resulting search tree is invariant.Path-wise rules depend on the path from the root to the current node, and this structure supports pseudo-dimension and generalization analyses.
  • Sample complexity guarantees: For arbitrary scoring rules and tree-size cap κ̄, the guarantees use a parameter-space partition induced by at most n^2(κ̄+1) hyperplanes, with pseudo-dimension O(dκ̄ log n + d log d).The resulting bounds apply to convex combinations of d scoring rules and depend on the allowed search-tree size.

4 Experiments

The experiments evaluate how the B&B variable-selection parameter affects average tree size across application domains and investigate generalization guarantees. Results show strong application dependence, while data-dependent guarantees are significantly better than worst-case guarantees.

  • Experimental results: Variable-selection parameters can dramatically change average B&B tree size, and no single value is effective across multiple natural distributions.The relationship between the parameter and tree size varies substantially by application, motivating per-application tuning.
  • Experimental setup: The experiments average B&B tree sizes over independent samples for every possible value of the linear scoring parameter µ.A CPLEX branch callback also identifies a finite set of parameter values producing all possible trees for each instance, avoiding skipped parameter choices.
  • Experimental setup: The study evaluates combinatorial auction winner determination, facility location, clustering, and agnostically learned linear separators formulated as MILPs.The auction experiments use binary MILPs, while the linear-separator study generates 500 instances with 50 points and flips 10 labels in each instance.
  • Experimental results: The optimal parameter is close to 1 for regions combinatorial auctions, facility location, and clustering, but severely suboptimal for arbitrary combinatorial auctions.This comparison illustrates why parameter values cannot be selected universally across domains.
  • Generalization guarantees: Data-dependent generalization guarantees are significantly better than worst-case guarantees in the comparison shown in Figure 7.The analysis relates the guarantees to the finite set of parameter-induced trees and uses Rademacher-complexity results for the data-dependent bound.

5 Constraint satisfaction problems

The paper extends its tree-search configuration theory from MILPs to CSPs, where branching assigns values to variables and pruning follows infeasible partial assignments.

  • CSP formulation: A CSP consists of variables, their domains, and constraints that map assignments of selected variables to feasibility values.The formal representation is a tuple (X, D, C), with each constraint applying to a subset of variables.
  • Example 5.1: The graph k-coloring example models vertices as variables, colors as domain values, and adjacency restrictions as not-equal constraints.A satisfying assignment is illustrated using three colors for four vertices.
  • CSP tree search: CSP tree search branches on a variable by creating one branch for each possible value in its domain.A branch is pruned when the constraints are infeasible under the partial assignment along that branch.
  • Variable selection: CSP variable-selection policies score candidate variables, and the algorithm branches on the variable with the highest score.Examples include degree divided by domain size, dynamic degree divided by domain size, and smallest domain.
  • Scope: The paper’s theory applies to tree search in both MILPs and constraint satisfaction problems.It also covers learning weights for two-child lookahead decisions and mixtures of several scoring rules.

6 Conclusions and broader applicability

The paper concludes that machine learning can configure mixtures of branching rules effectively, with theoretical guarantees and experiments showing substantial, potentially exponential, benefits.

  • Conclusions: The method learns a nearly optimal mixture of branching rules for tree-search algorithm configuration.The mixture can combine variable-selection or other branching rules.
  • Conclusions: Using an optimal parameter from one application domain on another can cause substantial tree-size blowup, and the paper proves this blowup can be exponential.The conclusion connects the cross-domain mismatch observed experimentally with the theoretical worst case.
  • Conclusions: The paper provides the first sample-complexity guarantees for tree-search algorithm configuration.With a small number of samples, empirical cost for mixtures of two scoring rules is close to expected cost, and empirical Rademacher complexity can tighten the bounds.
  • Broader applicability: The theory also applies to other tree-growing applications, including learning variable-selection rules for decision trees and taxonomies.The paper gives customer segmentation as an example of a taxonomy application.

A Additional related work

Related work applies machine learning and data-driven methods to branching and other B&B decisions, but the cited approaches differ in objective and theoretical guarantees.

  • Variable selection: Khalil et al. learn variable-selection strategies that mimic strong branching while running faster than strong branching.Their procedure trains on part of a single MILP instance and observes strong-branching choices.
  • Other B&B policies: Other work studies machine learning for B&B node selection and pruning policies rather than the variable-selection configuration addressed here.The cited work focuses on speeding node selection and learning whether to fathom a node.

B Variable selection policies

The generic variable-selection procedure evaluates candidate variables with a scoring rule and branches on the highest-scoring candidate.

  • The procedure receives the current subproblem Q as input.
  • It defines candidate variables as those whose LP-relaxation values are nonintegral.
  • It computes score(Q, i) for every candidate and outputs the candidate with maximum score.

C Proofs from Section 3

The proofs establish that weighting two scoring rules can create sharp phase transitions in branch-and-bound tree size, including constant-versus-exponential separations. They construct MILP families where branching order determines whether infeasibility is detected quickly or only after extensive search.

  • Theorem 3.2: For every even n ≥6 and threshold µ∗, an instance family yields O(1) nodes below µ∗ but 2^(n−4)/2 nodes above it.
  • Construction: Branching first on {x_n−2, x_n−1, x_n} detects infeasibility in a tree of size at most 2^3 = 8, whereas branching first on {x_1, …, x_n−3} creates exponential size.
  • Lower bound: For µ > µ∗, every constructed instance has a branch-and-bound tree of depth at least 2^(n−5)/4.
  • Distributional separation: A complementary family reverses the weighting behavior: one side produces Ω(2^(n−5)/4) nodes while the other produces O(1) nodes.
  • Node selection: The resulting theorem applies to any node-selection policy because path-wise scoring makes the search tree independent of node-selection policy.

C.1 Empirical Risk Minimization Algorithm

The empirical risk minimization algorithm searches over the mixing parameter while tracking intervals that preserve the current search behavior, then selects the best mixture on the training instances.

  • The algorithm seeks the best mixture of two variable-selection scoring rules for a given set of problem instances.
  • For each mixing parameter, it tracks the largest interval of parameters producing identical algorithm behavior on the current run.
  • The interval bookkeeping is valid because parameters that preserve the highest-scoring variable produce the same branching choice at that node.

D Additional information about experiments

The ERM procedure evaluates how the mixing parameter affects each instance’s piecewise-constant search cost, then selects the interval with the lowest average cost.

  • The ERM algorithm takes problem instances and two variable-scoring rules as input.
  • For each instance, it computes the piecewise-constant cost as a function of the mixing parameter µ.
  • It averages these piecewise-constant cost functions pointwise across instances.
  • The algorithm outputs a µ∗ in an interval minimizing the average cost.
  • The appendix includes MILP formulations for facility location, clustering, and agnostic learning of linear separators.

E Tree search

Tree search recursively builds a tree of partial solutions while using fathoming functions to prune nodes that need not be explored.

  • A tree search algorithm represents an instance with variables, finite domains, a feasibility function, and an objective function.
  • Tree search builds a tree of partial solutions until it finds the optimal solution.
  • The localFathom function decides whether to fathom or explore a node using the instance and its partial solution.
  • The globalFathom function additionally uses the current search tree to decide whether a node should be fathomed.
  • In mixed-integer programming, global fathoming can prune a node when its LP-relaxation bound is no better than the best known integral solution.

E.1 Problem statement

The paper seeks a convex combination of variable-selection scoring rules whose tree-search cost is nearly optimal in expectation over a distribution of problem instances.

  • The goal is to learn a convex combination of scoring rules that is nearly optimal in expected cost over an instance distribution.
  • The scoring rules may be any selected set of variable-selection procedures, and cost measures the quality of tree search on an instance.
  • The paper proves that only a small number of samples suffices for (ϵ, δ)-learnability.
  • The instances are assumed to involve n D-ary variables for natural numbers n and D.
  • The results apply to tree-constant cost functions, including search-tree size.

E.2 Path-wise scoring rules

Path-wise scoring rules depend only on a node, candidate variable, and root-to-node path. For two such rules, mixing weights partition [0, 1] into intervals yielding invariant search trees.

  • E.2 Path-wise scoring rules: A score-based policy selects the unbranched variable with the largest score computed from the partial search tree, partial solution, and variable index.
  • E.2 Path-wise scoring rules: A path-wise scoring rule depends only on the node, variable, and path from the root to the node containing the partial solution.
  • E.2 Path-wise scoring rules: For one instance, mixing two path-wise scoring rules partitions [0, 1] into at most Dn(n−1)/2n^n intervals, each producing the same search tree.
  • E.2 Path-wise scoring rules: The bound is established by analyzing an alternative search procedure without globalFathom and then relating its behavior to the full algorithm.
  • E.2 Path-wise scoring rules: The interval bound follows because each node contributes at most n subdivisions, while path-wise scoring keeps decisions consistent across equivalent paths.
  • E.2 Path-wise scoring rules: The search tree built by the full algorithm is a rooted subtree of the tree built by the alternative procedure for the same mixing parameter.

E.2.1 General scoring rules

This section establishes geometric and complexity guarantees for search trees generated by convex combinations of arbitrary scoring rules. It shows that parameter regions correspond to fixed trees and bounds the pseudodimension of the resulting cost-function class.

  • Geometric structure: For each instance, at most n^2(κ̄+1) hyperplanes partition parameter space into connected regions within which the generated search tree is invariant.The invariant-region result applies to arbitrary scoring rules and search trees capped at size κ̄.
  • Tree-region characterization: Varying the mixing parameters can produce at most n^κ̄ distinct search trees for an instance.Each tree is determined by the sequence of at most κ̄ branching variables, with at most n choices at each position.
  • Tree-region characterization: For any fixed search tree, the mixing parameters that produce it lie exactly in the intersection of at most n^(κ̄+2) halfspaces.The characterization follows by constraining each branching choice under the linear combination of scoring rules.
  • Complexity bound: The class of cost functions induced by d scoring rules has pseudodimension O(dκ̄ log n + d log d).The bound is obtained by combining the hyperplane arrangement with the number of possible trees across parameter regions.
  • Capped tree-size costs: The same framework yields a corollary for tree-size costs capped at an arbitrary bound κ over distributions of problem instances with at most n variables.The corollary uses the tree-count and halfspace characterizations to analyze capped search-tree size.
Loading 1803.10150v2…