Learning to Branch

Abstract

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.

Cited by in corpus (22)

• Deep Graph Matching via Blackbox Differentiation of Combinatorial Solvers
• Reinforcement Learning for Integer Programming: Learning to Cut
• Statistically-Robust Clustering Techniques for Mapping Spatial Hotspots: A Survey
• Learning Space Partitions for Nearest Neighbor Search
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• (Learned) Frequency Estimation Algorithms under Zipfian Distribution
• Branch and Bound in Mixed Integer Linear Programming Problems: A Survey of Techniques and Trends
• A General Large Neighborhood Search Framework for Solving Integer Linear Programs
• CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints
• Empirical Bayes Regret Minimization
• Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration
• Pandora's Box with Correlations: Learning and Approximation
• LORM: Learning to Optimize for Resource Management in Wireless Networks with Few Training Samples
• Guarantees for Tuning the Step Size using a Learning-to-Learn Approach
• Learning Branching Heuristics for Propositional Model Counting
• Curriculum learning for multilevel budgeted combinatorial problems
• Data driven semi-supervised learning
• Learning Complexity of Simulated Annealing
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability
• Semi-bandit Optimization in the Dispersed Setting
• Data-driven Algorithm Selection and Parameter Tuning: Two Case studies in Optimization and Signal Processing