Learning to Branch in Mixed Integer Programming

By Elias Boutros Khalil, Pierre Le Bodic, Le Song, George L. Nemhauser, Bistra N. Dilkina. 2016

434 citations recorded by the source corpus.

The design of strategies for branching in Mixed Integer Programming (MIP) is guided by cycles of parameter tuning and offline experimentation on an extremely heterogeneous testbed, using the average performance. Once devised, these strategies (and their parameter settings) are essentially input-agnostic. To address these issues, we propose a machine learning (ML) framework for variable branching in MIP.Our method observes the decisions made by Strong Branching (SB), a time-consuming strategy that produces small search trees, collecting features that characterize the candidate branching variables at each node of the tree. Based on the collected data, we learn an easy-to-evaluate surrogate function that mimics the SB strategy, by means of solving a learning-to-rank problem, common in ML. The learned ranking function is then used for branching. The learning is instance-specific, and is performed on-the-fly while executing a branch-and-bound search to solve the MIP instance. Experiments on benchmark instances indicate that our method produces significantly smaller search trees than existing heuristics, and is competitive with a state-of-the-art commercial solver.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “This thread includes machine learning methods for branching [26, 22], tree node selection [16, 34], and heuristic selection [35, 23].”
Mathematical optimization in classification and regression trees (2021, background): “…(Jakaitiene et al. 2016; Pardalos et al. 2007); Business Analytics (Martens et al. 2007; Van Vlasselaer et al. 2017), Computational Optimization (Khalil et al. 2016; Lodi and Zarpellon 2017), Criminal Justice (Ridgeway 2013; Zeng et al. 2017), Cybersecurity (Kaloudi and Li 2020; Martínez Torres…”
Learning to Run Heuristics in Tree Search (2017, methodology): “In the context of MIP, ML has been used to find good parameter configurations for a solver [Hutter et al., 2009], design improved node [Sabharwal et al., 2012] or variable [Khalil et al., 2016] selection strategies, or detect decomposable problem structure [Kruber et al., 2016].”
Optimal randomized classification trees (2021, neutral): “Extracting knowledge from data is a crucial task in Statistics and Machine Learning, which has applications in areas such as Biomedicine [1, 2], Criminal Justice [3, 4, 5], Fraud Detection [6], Privacy Protection [7], Health Care [8, 9, 10, 11], Risk Management [12, 13], Social Networks [14], and Co”
Differentiation of Blackbox Combinatorial Solvers (2019, background): “, 2019), integer programming solvers (often with learning branch-and-bound rules) (Khalil et al., 2016; Balcan et al., 2018; Gasse et al., 2019) and SMT-solvers (satisfiability modulo theories)(Balunovic et al.”
A learning-based algorithm to quickly compute good primal solutions for Stochastic Integer Programs (2019, background): “It is well known that features describing the connection between variables, constraints and other interaction help ML to perform well rather than just providing plain data matrices [3, 5, 8, 12].”
Solving Mixed Integer Programs Using Neural Networks (2020, methodology): “Many of these focus specifically on learning to imitate FSB as we do (Khalil et al. 2016, Alvarez et al. 2017, Gasse et al. 2019, Gupta et al. 2020).”
On learning and branching: a survey (2017, methodology): “In this sense, all procedures ( learned of Marcos Alvarez et al. (2017), olb of Marcos Alvarez et al. (2016) and SB + ML of Khalil et al. (2016)) seem to suffer the same limitation to adapt with respect to the tree evolution.”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, background): “In practice, running strong branching at every node is prohibitive, and modern B&B solvers instead rely on hybrid branching [3; 1] which computes strong branching scores only at the beginning of the solving process and gradually switches to simpler heuristics such as: the conflict score (in the orig”
The voice of optimization (2018, methodology): “In the field of model predictive control (MPC), Klaučo et al. [2019] warm-start an online active set method for solving quadratic optimization problems (QOs).”
Learning Heuristics for the TSP by Policy Gradient (2018, methodology): “Machine Learning (ML) has been successfully used for variable branching in MIP by learning a supervised ranking function that mimics Strong Branching, a time-consuming strategy that produces small search trees [4].”
Optimization Models for Machine Learning: A Survey (2019, background): “Another area of research at the interface of machine learning and operations research is using machine learning to solve hard optimization problems and particularly NP-hard integer constrained optimization [40, 135, 136, 154, 208].”
Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon (2018, methodology): “On the one hand, Marcos Alvarez et al. (2014, 2016, 2017); Khalil et al. (2016) estimate that strong branching is an eﬀective branching strategy but computationally too expensive and build a machine learning model to approximate it.”