Learning to Branch with Tree MDPs

Lara ScavuzzoFeng Yang ChenDidier ChételatMaxime GasseAndrea LodiNeil Yorke-SmithKaren I. Aardal

article2022NeurIPS87 citations

Proposes a tree Markov Decision Process framework and an associated policy gradient theorem that improve credit assignment and convergence when training reinforcement learning agents from scratch to make branching decisions in Mixed Integer Linear Programming solvers.

Listen

Combinatorial optimization problems, widely modeled as Mixed Integer Linear Programs (MILPs), are vital for decision-making across supply chain logistics, finance, and industrial engineering. Modern solvers rely on the Branch-and-Bound algorithm to solve these problems by recursively dividing the search space into a tree structure. A critical component of this process is variable selection, or the branching rule, which decides how to split the problem at each step. While current solvers use hand-crafted heuristics or imitate expensive expert rules, these approaches hit performance ceilings and struggle when linear relaxations fail to provide useful signals.

The article develops and evaluates a reinforcement learning framework, termed tree Markov Decision Processes (tree MDPs), to learn effective branching policies directly from scratch without relying on expert imitation. The authors introduce a policy gradient theorem adapted for tree structures and establish practical conditions—specifically depth-first search and providing an optimal objective limit—to make training computationally viable.

To evaluate this framework, the authors conducted computational experiments across five standard synthetic optimization benchmarks, including set covering, combinatorial auctions, maximum independent set, capacitated facility location, and multiple knapsack problems. Using Graph Neural Networks to represent problem states, the authors trained branching policies using standard policy gradient methods over 10,000 instances per benchmark and evaluated them on both standard test sets and transfer sets with larger, more complex problems.

The analysis reveals three main findings. First, formulating the problem as a tree MDP significantly improves credit assignment during learning, leading to faster training convergence and equal or superior performance compared to standard temporal reinforcement learning. Second, on the multiple knapsack benchmark, where traditional expert-based rules fail due to poor linear relaxations, the tree MDP reinforcement learning models outperformed both default solver heuristics and imitation learning models. Third, on the remaining four benchmarks, reinforcement learning methods still trailed behind expert-tuned heuristics and imitation learning in final tree size, showing that training from scratch remains challenging.

These findings demonstrate that reinforcement learning can discover novel branching strategies where classical heuristics struggle, validating the theoretical framework of tree MDPs for divide-and-conquer algorithms. However, because training from scratch requires significant computation and generally achieves lower performance on well-behaved problems, the authors recommend viewing this approach as a foundation for specialized optimization problems rather than an immediate replacement for mature commercial solvers. Future research should prioritize improving sample efficiency, refining generalization across diverse real-world benchmarks, and exploring hybrid methods that combine reinforcement learning with existing solver heuristics.

Cornell Tech and Technion - IIT Delft University of Technology Jacobs Technion-Cornell Institute Mila Polytechnique Montréal integer linear programs reinforcement learning mdp tree MDPs optimal branching tree policy gradients

arXiv: 2205.11107 lascavana/rl2branch

Paper: Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon, Yoshua Bengio et al. (2018). This seminal survey establishes the conceptual and methodological foundation for integrating machine learning into combinatorial optimization solvers and branch-and-bound decision frameworks.
Paper: Learning Combinatorial Optimization Algorithms over Graphs, Elias Boutros Khalil et al. (2017). This foundational work demonstrates how Graph Neural Networks and reinforcement learning combine to learn greedy heuristics over graph optimization problems, directly motivating the state representations used in the source.
Paper: Policy Gradient Methods for Reinforcement Learning with Function Approximation, Richard S. Sutton et al. (1999). This work establishes the fundamental Policy Gradient Theorem that the source generalizes and adapts to tree Markov Decision Processes.
Paper: Neural Combinatorial Optimization with Reinforcement Learning, Irwan Bello et al. (2016). This paper introduces policy-gradient reinforcement learning for combinatorial optimization problems without expert supervision, establishing the from-scratch RL paradigm extended by the source.

Paper: Combinatorial Optimization and Reasoning with Graph Neural Networks, Quentin Cappart et al. (2023). This comprehensive survey contextualizes dual-side exact solver enhancements—including learned branching and variable selection—within the broader landscape of Graph Neural Networks for combinatorial reasoning.
Paper: Recursive Agent Optimization, Apurva Gandhi et al. (2026). This work extends tree-structured reinforcement learning and credit assignment principles to recursive, dynamically generated agent execution trees for complex decomposition tasks.

Cover for Learning to Branch with Tree MDPs

Abstract

State-of-the-art Mixed Integer Linear Program (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as the branching rule. The idea of learning branching rules from data has received increasing attention recently, and promising results have been obtained by learning fast approximations of the strong branching expert. In this work, we instead propose to learn branching rules from scratch via Reinforcement Learning (RL). We revisit the work of Etheve et al. [11] and propose tree Markov Decision Processes, or tree MDPs, a generalization of temporal MDPs that provides a more suitable framework for learning to branch. We derive a tree policy gradient theorem, which exhibits a better credit assignment compared to its temporal counterpart. We demonstrate through computational experiments that tree MDPs improve the learning convergence, and offer a promising framework for tackling the learning-to-branch problem in MILPs.

Topics

integer linear programs reinforcement learning mdp

Keywords

tree MDPs optimal branching tree policy gradients strong branching reinforcement learning combinatorial optimization integer programming Markov decision processes variable selection node selection

1 Introduction
2 Background
2.1 The B&B algorithm
2.2 Temporal MDPs
2.3 The branching temporal MDP
3 Approaches to learning to branch
3.1 Learning to branch with imitation learning
3.2 Learning to branch with reinforcement learning
4 Branching as a tree MDP
4.1 Tree MDPs
4.2 The branching tree MDP
4.2.1 B&B tree transitions
4.2.2 B&B tree reward
4.3 Efficiency of tree MDP
4.4 Theoretical limitations
4.5 Connections with hierarchical RL
5 Experiments
5.1 Setup
5.2 Results
6 Conclusions and Future Directions
Acknowledgements
References

Knowls

Knowl 1 — Tree Markov Decision Processes
definition
A Tree Markov Decision Process (Tree MDP) is an augmented Markov Decision Process defined as a tuple:
$tM = (\mathcal{S}, \mathcal{A}, p_{init}, p^-_{ch}, p^+_{ch}, r, l)$
where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $p_{init}(s_0)$ is the initial state distribution, $p^-_{ch}(s_{ch^-_i} | s_i, a_i)$ and $p^+_{ch}(s_{ch^+_i} | s_i, a_i)$ are transition probability distributions to the left and right child states respectively, $r : \mathcal{S} \to \mathbb{R}$ is the reward function, and $l : \mathcal{S} \to \{0, 1\}$ is a leaf indicator function.

Every non-leaf state $s_i$ (where $l(s_i) = 0$ ), upon taking action $a_i$ , generates two child states: a left child $s_{ch^-_i}$ and a right child $s_{ch^+_i}$ . A generated episode $\tau$ forms a binary tree with node set $\mathcal{N} = \{0, \dots, |\tau|\}$ and leaf set $\mathcal{L} = \{i \in \mathcal{N} \mid l(s_i) = 1\}$ . An action $a_i \sim \pi(\cdot | s_i)$ is taken at each non-leaf node $i \in \mathcal{N} \setminus \mathcal{L}$ .

The probability distribution over tree trajectories under a policy $\pi$ is given by:
$p_\pi(\tau) = p_{init}(s_0) \prod_{i \in \mathcal{N} \setminus \mathcal{L}} \pi(a_i | s_i) p^-_{ch}(s_{ch^-_i} | s_i, a_i) p^+_{ch}(s_{ch^+_i} | s_i, a_i)$
A tree MDP satisfies the tree Markov property:
$S_{ch^-_i}, S_{ch^+_i} \perp\!\!\!\perp S_{nd_i} \mid S_i, A_i, \quad \forall i$
where $nd_i$ denotes the set of all non-descendants of node $i$ in the search tree. This ensures that the subtrees rooted at the children of node $i$ depend solely on the immediate state $s_i$ and action $a_i$ .
Knowl 2 — Tree Policy Gradient Theorem
theoretical result
For any Tree Markov Decision Process $tM = (\mathcal{S}, \mathcal{A}, p_{init}, p^-_{ch}, p^+_{ch}, r, l)$ with cumulative reward objective $V^\pi = \mathbb{E}_{\tau \sim p_\pi}\left[ \sum_{i \in \mathcal{N}} r(s_i) \right]$ , the gradient of the expected return with respect to policy parameters is given by:
$\nabla_\pi V^\pi = \mathbb{E}_{\tau \sim p_\pi} \left[ \sum_{i \in \mathcal{N} \setminus \mathcal{L}} \nabla_\pi \log \pi(a_i | s_i) \sum_{j \in d_i} r(s_j) \right]$
where $\mathcal{N}$ is the set of tree nodes, $\mathcal{L}$ is the set of leaf nodes, and $d_i$ denotes the set of all descendants of node $i$ in the tree episode $\tau$ .

In standard temporal MDP policy gradients, an action $a_t$ is credited with all rewards occurring after step $t$ in time: $\sum_{t' = t+1}^{|\tau|} r(s_{t'})$ . In contrast, the tree policy gradient credits action $a_i$ solely with rewards in its descendant subtree $\sum_{j \in d_i} r(s_j)$ , which is a strict subset of the temporal post-step rewards. This restricts credit assignment strictly to causal subtrees, reducing variance in policy gradient estimation.
Knowl 3 — Branch-and-Bound Formulation as a Tree MDP
model/method
The Branch-and-Bound (B&B) algorithm for solving Mixed Integer Linear Programs (MILPs) can be formulated as a Tree MDP where episodes $\tau$ mirror the B&B search tree:
1. State: Each tree node $i$ holds a state $s_i = (\text{MILP}_i, \text{GUB}_i)$ , where $\text{MILP}_i$ is the local subproblem at node $i$ and $\text{GUB}_i$ is the Global Upper Bound (the objective value of the best feasible integer solution found so far, or $\infty$ ) at the time node $i$ is processed.
2. Action: At each non-leaf node $i$ , the action $a_i = (j, x_j^*)$ selects a fractional variable index $j$ and its fractional value $x_j^*$ to generate binary child subproblems by adding constraints $x_j \le \lfloor x_j^* \rfloor$ (left child) and $x_j \ge \lceil x_j^* \rceil$ (right child).
3. Reward: The reward decomposes across nodes with $r : \mathcal{S} \to \mathbb{R}$ . To minimize the total B&B tree size, the reward is set to $r(s_i) = -1$ for all nodes.
4. Transition Condition: State transitions must decompose into independent left and right child transitions $p^-_{ch}$ and $p^+_{ch}$ . This requires that the global upper bounds at the child nodes, $\text{GUB}_{ch^-_i}$ and $\text{GUB}_{ch^+_i}$ , can be computed strictly from the current state and action $(s_i, a_i)$ without depending on the exploration history of un-related tree branches.
Knowl 4 — Conditions for Tree Markovian Transitions in Branch-and-Bound
theoretical result
Vanilla Branch-and-Bound violates the tree Markov property in general because the Global Upper Bound (GUB) at a child node depends on whether an integer feasible solution was discovered earlier in another subtree, which depends on global node selection order. Two specific configurations ensure the tree Markov property holds:
1. Optimal Objective Limit B&B (ObjLim B&B): When the optimal objective value $GUB^*$ of the MILP instance is known in advance and set as the initial bound ( $GUB_0 = GUB^*$ ), the upper bound remains constant throughout solving. Consequently, child transitions are completely local and deterministic based on $(s_i, a_i)$ .
2. Depth-First-Search B&B (DFS B&B): When nodes are processed strictly in depth-first, left-first order, the GUB at any child node depends deterministically only on the subproblems traversed along that DFS lineage, making transitions strictly tree-Markovian without requiring pre-solved bounds.
Knowl 5 — Tree REINFORCE Training Loop for Learning to Branch
algorithm
The Tree REINFORCE algorithm trains a parameterized branching policy $\pi_\theta$ using tree policy gradients computed over B&B episodes.
Input: Training set of MILP instances and pre-computed optimal values $\mathcal{D}$ , max epochs $K$ , time limit $\zeta$ , entropy bonus weight $\lambda$ , learning rate $\alpha$ , sample rate $\beta$
Output: Trained branching policy parameters $\theta$
Initialize policy $\pi_\theta$ with random parameters $\theta$
for epoch from 1 to $K$ do
    if elapsed time > $\zeta$ then break
    Sample 10 MILP instances from $\mathcal{D}$
    for each sampled instance do
        Collect one tree episode $\tau$ by running B&B to optimality with policy $\pi_\theta$
        Extract randomly $\beta \times |\tau|$ tuples $(s, a, G)$ from $\tau$ , where $G = \sum_{j \in d_i} r(s_j)$ is the local subtree return
    end for
     $n \leftarrow$ total number of collected tuples
     $L \leftarrow 0$
    for each collected tuple $(s, a, G)$ do
         $L \leftarrow L - G \cdot \frac{1}{n} \log \pi_\theta(a|s)$
         $L \leftarrow L - \lambda \cdot \frac{1}{n} H(\pi_\theta(\cdot|s))$
    end for
     $\theta \leftarrow \theta - \alpha \nabla_\theta L$
end for
return $\pi_\theta$
The local subtree return $G$ for every node in tree $\tau$ is computed efficiently in $O(|\tau|)$ using a bottom-up post-order tree traversal. $H(\pi_\theta(\cdot|s))$ denotes the policy entropy at state $s$ .
Knowl 6 — Experimental Setup for Reinforcement Learning Branching Rules
experimental setup
Evaluations are conducted on five NP-hard synthetic MILP benchmarks: Combinatorial Auctions, Set Covering, Maximum Independent Set, Capacitated Facility Location, and Multiple Knapsack. For each benchmark, 10,000 instances are used for training, 20 for validation tracking, 40 for testing (same size as training), and 40 for transfer evaluation (larger, more difficult instances).

Branching policies are parameterized via a bipartite Graph Neural Network (GNN) representing variable and constraint nodes. Policies are trained using REINFORCE with entropy bonus under four training regimes:
1. IL: Imitation learning from the Strong Branching expert rule.
2. MDP: RL with standard temporal policy gradients.
3. tMDP+DFS: RL with tree policy gradients under depth-first search node selection.
4. tMDP+ObjLim: RL with tree policy gradients using the known optimal objective limit.
Training uses PyTorch Geometric and Ecole interfacing with the SCIP 7.0 solver with GPU compute nodes, running up to 15,000 epochs or 6 days. Restarts and cutting planes after the root node are deactivated. Final evaluation is performed on standard SCIP with its default node selection policy (without DFS or ObjLim constraints) using a 1-hour time limit over 5 random seeds.

Knowl 7 — Branching Performance Across Synthetic MILP Benchmarks

data/table

The table compares final B&B tree sizes (geometric mean $\pm$ average per-instance standard deviation percentage across 40 instances $\times$ 5 seeds) of SCIP's default rule, imitation learning (IL), and three RL methods (temporal MDP, tMDP+DFS, tMDP+ObjLim) evaluated on test and transfer benchmarks.

Model	Comb. Auct.	Set Cover	Max.Ind.Set	Facility Loc.	Mult. Knap.
Test Set (Same size as training)
SCIP default	7.3 $\pm$ 39%	10.7 $\pm$ 24%	19.3 $\pm$ 52%	203.6 $\pm$ 63%	267.8 $\pm$ 96%
IL	52.2 $\pm$ 13%	51.8 $\pm$ 10%	35.9 $\pm$ 36%	247.5 $\pm$ 39%	228.0 $\pm$ 95%
RL (MDP)	86.7 $\pm$ 16%	196.3 $\pm$ 20%	91.8 $\pm$ 56%	393.2 $\pm$ 47%	143.4 $\pm$ 76%
RL (tMDP+DFS)	86.1 $\pm$ 17%	190.8 $\pm$ 20%	89.8 $\pm$ 51%	360.4 $\pm$ 46%	135.8 $\pm$ 75%
RL (tMDP+ObjLim)	87.0 $\pm$ 18%	193.5 $\pm$ 23%	85.4 $\pm$ 53%	325.4 $\pm$ 41%	142.4 $\pm$ 78%
Transfer Set (Larger instances)
SCIP default	733.9 $\pm$ 26%	61.4 $\pm$ 19%	2867.1 $\pm$ 35%	344.3 $\pm$ 57%	592.3 $\pm$ 75%
IL	805.1 $\pm$ 9%	145.0 $\pm$ 6%	1774.8 $\pm$ 38%	407.8 $\pm$ 37%	1066.1 $\pm$ 101%
RL (MDP)	1906.3 $\pm$ 18%	853.3 $\pm$ 27%	2768.5 $\pm$ 76%	679.4 $\pm$ 52%	518.4 $\pm$ 79%
RL (tMDP+DFS)	1804.6 $\pm$ 17%	816.8 $\pm$ 25%	2970.0 $\pm$ 76%	609.1 $\pm$ 47%	495.1 $\pm$ 81%
RL (tMDP+ObjLim)	1841.9 $\pm$ 18%	826.4 $\pm$ 26%	2763.6 $\pm$ 74%	496.0 $\pm$ 48%	425.3 $\pm$ 64%

On all five benchmarks, Tree MDP formulations (tMDP+DFS and tMDP+ObjLim) yield equal or smaller tree sizes than standard temporal RL (MDP). Furthermore, on Multiple Knapsack, all RL methods outperform both SCIP default and Imitation Learning (IL).

Knowl 8 — Advantage of RL Branching over Strong Branching on Problems with Weak Relaxations
empirical result
On the Multiple Knapsack benchmark, branching rules learned via Reinforcement Learning outperform both SCIP's default heuristic and Imitation Learning (IL) of Strong Branching. On the transfer dataset, RL (tMDP+ObjLim) achieves a geometric mean tree size of 425.3 nodes, compared to 592.3 for SCIP default and 1066.1 for IL.

This behavior occurs because Multiple Knapsack formulations exhibit weak Linear Programming (LP) relaxations that produce little to no dual bound improvement upon branching. Because Strong Branching and SCIP default rely heavily on LP dual bound improvements to score variables, their scores become non-discriminative. In contrast, RL directly optimizes end-to-end tree size reduction and learns effective branching behavior even when LP dual bounds provide poor guidance.
Knowl 9 — Convergence and Sample Efficiency of Tree MDPs
empirical result
When measuring validation B&B tree size against the cumulative number of collected training samples (a hardware-independent proxy for training effort), Tree MDP formulations (tMDP+ObjLim and tMDP+DFS) achieve substantially faster convergence and better sample efficiency than standard temporal MDP policy gradients (MDP). On benchmarks like Set Covering, tMDP+ObjLim demonstrates clear domination, reaching lower validation tree sizes in fewer total samples due to localized credit assignment.
Knowl 10 — Environment Mismatch and Exploration Bottlenecks in RL for Branching
limitation
The Tree MDP branching formulation exhibits two primary limitations:
1. Train-Evaluation Environment Mismatch: Enforcing the tree Markov property requires altering the training solver dynamics (either imposing depth-first search or supplying the optimal objective limit $GUB^*$ ). However, evaluation is conducted in default B&B solver environments lacking these constraints, introducing a transfer learning gap.
2. Performance Gap Relative to Expert Heuristics: On 4 of the 5 evaluated benchmarks (Combinatorial Auctions, Set Covering, Maximum Independent Set, Facility Location), RL trained from scratch underperforms imitation learning (IL) and SCIP default. Training without expert guidance in large combinatorial action spaces suffers from severe sample complexity and exploration difficulty, leaving a performance gap on general MILP instances.

Coverage note — No substantial contributed material was omitted. The knowls cover the Tree MDP formulation, tree Markov property, tree policy gradient theorem, ObjLim and DFS B&B conditions, the REINFORCE training algorithm, experimental setup, benchmark data, empirical findings on weak relaxations, sample efficiency analyses, and limitations.

References

1.Tobias Achterberg. Constraint Integer Programming. PhD thesis, Technischen Universität Berlin, 2007.
2.Tobias Achterberg and Timo Berthold. Hybrid branching. In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 309–311. Springer, 2009.
3.Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress. In Facets of Combinatorial Optimization, pages 449–481. Springer, 2013.
4.Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In Combinatorial Optimization, pages 37–60. Springer, 1980.
5.Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 2020.
6.David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization, volume 1. Springer, 2016.
7.Antonia Chmiela, Elias B Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch-and-bound. arXiv preprint arXiv:2103.10294, 2021.
8.Gérard Cornuéjols, Ranjani Sridharan, and Jean-Michel Thizy. A comparison of heuristics and relaxations for the capacitated plant location problem. European Journal of Operational Research, 50(3):280–297, 1991.
9.Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. A theoretical and computational analysis of full strong-branching. arXiv preprint arXiv:2110.10754, 2021.
10.Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of Artificial Intelligence Research, 13:227–303, 2000.
11.Marc Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, and Safia Kedad-Sidhoum. Reinforcement learning for variable selection in a branch and bound algorithm. In CPAIOR, 2020.
12.Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
13.Alex S Fukunaga. A branch-and-bound algorithm for hard multiple knapsack problems. Annals of Operations Research, 184(1):97–119, 2011.
14.Gerald Gamrath and Christoph Schubert. Measuring the impact of branching rules for mixed-integer programming. In Operations Research Proceedings 2017, pages 165–170. Springer, 2018.
15.Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, Gregor Hendel, Christopher Hojny, Thorsten Koch, Pierre Le Bodic, Stephen J. Maher, Frederic Matter, Matthias Miltenberger, Erik Mühmer, Benjamin Müller, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Christine Tawfik, Stefan Vigerske, Fabian Wegscheider, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin, 3 2020.
16.Gerald Gamrath, Timo Berthold, and Domenico Salvagnin. An exploratory computational analysis of dual degeneracy in mixed-integer programming. EURO Journal on Computational Optimization, 8(3):241–261, 2020.
17.Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. In Advances in Neural Information Processing Systems, pages 15580–15592, 2019.
18.Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. MIPLIB 2017. Mathematical Programming Computation, pages 1–48, 2021.
19.Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. In Advances in Neural Information Processing Systems, volume 33, 2020.
20.Christoph Hansknecht, Imke Joormann, and Sebastian Stiller. Cuts, primal heuristics, and learning to branch for the time-dependent traveling salesman problem. arXiv preprint arXiv:1805.01415, 2018.
21.He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Advances in Neural Information Processing systems, pages 3293–3301, 2014.
22.Elias B Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In AAAI, 2022.
23.Elias Boutros Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
24.Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pages 66–76, 2000.
25.Andrea Lodi and Giulia Zarpellon. On learning and branching: a survey. Top, 25(2):207–236, 2017.
26.Alejandro Marcos Alvarez, Louis Wehenkel, and Quentin Louveaux. Online learning for strong branching approximation in branch-and-bound. Technical report, Universite de Liege, 2016.
27.Marvin Minsky. Steps toward artificial intelligence. Proceedings of the IRE, 49(1):8–30, 1961.
28.Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015.
29.Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks. arXiv preprint arXiv:2012.13349, 2020.
30.Vangelis Th Paschos. Applications of combinatorial optimization, volume 3. John Wiley & Sons, 2014.
31.Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
32.Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. In Workshop on Learning Meets Combinatorial Algorithms, NeurIPS 2020, 11 2020.
33.Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving learning to branch via reinforcement learning. In Learning Meets Combinatorial Algorithms at NeurIPS 2020, 2020.
34.Richard S Sutton, David A McAllester, Satinder P Singh, Yishay Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems, volume 99, pages 1057–1063. Citeseer, 1999.
35.Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229–256, 1992.
36.Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-bound search trees to learn branching policies. In AAAI, pages 3931–3939, 2021.

Citation

MLA

Scavuzzo, L., et al. “Learning to Branch with Tree MDPs”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 18514–26, https://proceedings.neurips.cc/paper_files/paper/2022/file/756d74cd58592849c904421e3b2ec7a4-Paper-Conference.pdf.

APA

Scavuzzo, L., Chen, F., Chetelat, D., Gasse, M., Lodi, A., Yorke-Smith, N., & Aardal, K. (2022). Learning to Branch with Tree MDPs. Advances in Neural Information Processing Systems, 35, 18514–18526. https://proceedings.neurips.cc/paper_files/paper/2022/file/756d74cd58592849c904421e3b2ec7a4-Paper-Conference.pdf

Chicago

Scavuzzo, L., F. Chen, D. Chetelat, et al. 2022. “Learning to Branch with Tree MDPs”. Advances in Neural Information Processing Systems 35: 18514–26. https://proceedings.neurips.cc/paper_files/paper/2022/file/756d74cd58592849c904421e3b2ec7a4-Paper-Conference.pdf.

Harvard

Scavuzzo, L. et al. (2022) “Learning to Branch with Tree MDPs”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 18514–18526. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/756d74cd58592849c904421e3b2ec7a4-Paper-Conference.pdf.

Vancouver

1. Scavuzzo L, Chen F, Chetelat D, Gasse M, Lodi A, Yorke-Smith N, Aardal K (2022) Learning to Branch with Tree MDPs. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 18514–18526

BibTeX

@inproceedings{scavuzzo2022learning,
  title = {Learning to Branch with Tree MDPs},
  author = {Scavuzzo, Lara and Chen, Feng and Chetelat, Didier and Gasse, Maxime and Lodi, Andrea and Yorke-Smith, Neil and Aardal, Karen},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {18514-18526},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/756d74cd58592849c904421e3b2ec7a4-Paper-Conference.pdf}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Learning to Branch with Tree MDPs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Tree Markov Decision Processes

Knowl 2 — Tree Policy Gradient Theorem

Knowl 3 — Branch-and-Bound Formulation as a Tree MDP

Knowl 4 — Conditions for Tree Markovian Transitions in Branch-and-Bound

Knowl 5 — Tree REINFORCE Training Loop for Learning to Branch

Knowl 6 — Experimental Setup for Reinforcement Learning Branching Rules

Knowl 7 — Branching Performance Across Synthetic MILP Benchmarks

Knowl 8 — Advantage of RL Branching over Strong Branching on Problems with Weak Relaxations

Knowl 9 — Convergence and Sample Efficiency of Tree MDPs

Knowl 10 — Environment Mismatch and Exploration Bottlenecks in RL for Branching

References

Citation

BibTeX

Source Code

Access the Paper