Learning to Branch with Tree MDPs
Authors: Lara Scavuzzo
Feng Yang Chen
Didier Chételat
Maxime Gasse
Andrea Lodi
Neil Yorke-Smith
Karen Aardal
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning
mixed integer programming
markov decision process

Abstract: State-of-the-art Mixed Integer Linear Programming (MILP) solvers combine systematic tree search with a plethora of hard-coded heuristics, such as branching rules. While approaches to learn branching strategies have received increasing attention and have shown very promising results, most of the literature focuses on learning fast approximations of the \emph{strong branching} rule. Instead, we propose to learn branching rules from scratch with Reinforcement Learning (RL). We revisit the work of Etheve et al. (2020) and propose a generalization of Markov Decisions Processes (MDP), which we call \emph{tree MDP}, that provides a more suitable formulation of the branching problem. We derive a policy gradient theorem for tree MDPs that exhibits a better credit assignment compared to its temporal counterpart. We demonstrate through computational experiments that this new framework is suitable to tackle the learning-to-branch problem in MILP, and improves the learning convergence.

Learning to Branch with Tree MDPs
Lara Scavuzzo
Feng Yang Chen Polytechnique Montréal feng-yange cwen@pollytt..comm
Delft University of Technology
1.v. scaruzzonontarraeuuualltt...... .nl
Didier Chételat
Maxime Gasse
Polytechnique Montréal
Mila, Polytechnique Montréal
didier. chettelat@pollymtl.ccom
maxime gasse@polymtl...mmmmmmmmm
Andrea Lodi Jacobs Technion-Conen Institute Cornell Tech and Technion IIT andrea. lodi modi@corneel.. edu
Neil Yorke-Smith
Delft University of Technology
n. yorke- smi tmithhrueelft.tr
Karen Aardal Delft University of Technology
k. aardar @ttreaft..dll......m
Abstract
State-of-the of 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, instead propose learn branching rules from scratch via Reinforcement Learning (RL). We revisit the work of Etheve et al. [[I] and propose tree Markov Decision Processes, or tree MDPs, a generalization of temporal MDPs that provides more suitable framework for learning to branch. We derive a tree policy gradient thcorem, which exhibits a better credit assignment compared to its temporal counterpart. We demonstrate through computational ex- periments that tree MDPs improve the learning convergence, and offer promising framework for tackling the learning-to to- co-branch problem in MILPs.
1
Introduction
Mixed Integer Linear Programs (MILPs) offer powerful tool for modeling combinatorial opti- mization problems, and are used many real-world applications (30). The method of choice for solving MILPs to global optimality is the divide-and-conquer strategy. A critical component the algorithm is the branching rule, which is used recursively partition the MILP search space using space search tree. While there is little understanding of optimal branching decisions in general settings [25). the choice of the branching rule has a decisive impact solving performance in practice [3] In modern solvers, state-of-the teff-hh-and art performance is obtained using hard-coded branching rules that rely on heuristics designed by domain experts perform well representative set of test instances [18]
(B&B) algorithm, which follows
In recent years, increasing attention has been given to approaches that use Machine Learning (MI.)
to obtain good branching rules and improve upon expert-crafted heuristics [ Such statistical
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

d
h
B&B
Tree MDP episode
Temporal MDP episodes
temporal MDP episode. White nodes denote states, green nodes denote actions. In the tree MDP framework, the branching decision for splitting node f is credited two rewards, (Fh, r;). In the temporal MDP framework, the same branching decision is credited with additional rewards which depend on the temporal order in which B&B nodes processed, (Th: Te re), (Tho Tas ggg
Figure 1: B&B process
MDP episode
Tby Ta: re). or (rgz Tt).
approach is particularly well-suited in situations where similar problems are solved repeatedly, which is a common industrial scenario. In such cases, generic and agnostic branching rule might be suboptimal. Due to the sequential nature of branching, natural paradigm formulate the learning problem is Reinforcement Learning (RL), which allows to directly search for the optimal branching rule with respect to a metric of interest, such as average solving time, or final B&B tree size.
Etheve et 11 show that, when using depth- first-search (DFS) as the tree exploration (a.k.a. node selection) policy in B&B, minimizing each subtree size equivalent minimizing the global tree size. Using this result, they propose an efficient value-based RL procedure for learning to branch. In this paper build upon the work of Etheve al. [ and we propose generalization of the Markov Decision Process (MDP) paradigm that we call free MDP (illustrated in Figure I formally discussed in Section This general formulation captures the key insight of their approach, but opens the door for more general B&B settings, RL algorithms and reward functions.
In particular, show that DFS is just way enforce the "tree Markov" property, and propose an alternative, more practical solution that simply relies on providing the optimal objective limit to the solver during training. Our contribution is three-fold:
1. We introduce the concepts of a tree MDP and of the tree Markov property, and derive policy gradient theorem for tree MDPs.
2. We propose alternative way to enforce the tree Markov property in learning to branch by imposing an optimal objective limit, which less computationally demanding than DFS !.I.
3. We show that adopting the tree MDP paradigm improves both the convergence speed of RL and the quality the resulting branching rules, compared the regular MDP paradigm.
The remainder of this paper is organized as follows. We formally introduce MILPs, B&B and MDPs in Section 2 In Section we motivate the need for moving beyond imitation learning learning to branch, and discuss the challenges it raises. In Section we introduce the concepts of tree MDPs and the tree Markov property, we derive policy gradient theorem for tree MDPs, and we present convenient solution to enforce the tree Markov property in B&B without DFS [I]. In Section 5 we conduct, for the first time, a thorough computational evaluation of RL for learning branching rules, on five synthetic MILP benchmarks with two difficulty levels. Finally, we discuss the significance of our results and future directions 6
2 Background
In this section, we describe the Branch-and Bound (B&B) algorithm, and we show how the branching problem naturally formulates as a (temporal) Markov Decision Process.

---

2.1 The B&B algorithm
Consider a Mixed Integer Linear Program instance as an optimization problem of the form
min {ct x Ar S b, I < RER
I, E Z vi E 2},
(1)
where E IR" is the objective coefficient vector, A E m is the constraint matrix, b E RM is I, u E IX" are the lower and upper bound vectors, respectively, and
the constraint night-hand-side I S 2,.,,... n is the subset of variables constrained to take integer values. Relaxing the integrality constraints, x; E Z E I. yields a Linear Program (LP) that can be solved efficiently in practice, for example by using the Simplex algorithm. Solving such relaxation yields an LP solution 2*, and provides a lower bound c" 2" to the original problem (1). If by chance s* satisfies the integrality constraints, 27 Z Vi I. then it is also optimal solution to (Tp. If, on the contrary. there is at least one variable 2,, i E I such that 27 is not an integer, then one can split the feasible region into two sub-problems, by imposing
2, [
or
Iz 11
This partitioning step is known as branching. In its most basic form, the vanilla B&B algorithm recursively applies branching, thereby building search space tree where each node has an associated local sub-MILP, with a local LP solution and associated local lower bound If the local LP solution satisfies the MILP integrality constraints, then it is termed a feasible solution, and it also provides an upper bound to [ At any given time of the B&B process, a Global Lower Bound (GLB) to the original MILP be obtained by taking the lowest of local lower bounds of the leaf nodes of the tree. Similarly. a Global Upper Bound (GUB) can be obtained by taking the lowest of the upper bounds so far The B&B process terminates when more B&B leaf node be partitioned with (2). i.e., all leaf nodes satisfy one of these conditions: the local I.P has no solution (infeasible); the local lower bound is above the GUB (pruned); or the local LP solution satisfies the MILP integrality constraints (integer feasible). At termination, we have GLB = GUB, and the original MILP is solved.
The branching problem, a.k.a. variable selection problem, is the task of choosing, at every B&B iteration, the variable v; that will be used to generate a partition of the form (2). While there is no universal metric measure the quality of a branching rule, common performance measure is the final size of the B&B tree (the smaller the better) [1]
2.2 Temporal MDPs
In the following, upper-case letters in italics denote random variables (e.g. S, A), while their lower- case counterparts denote their value (e.g. 8, a) and their calligraphic counterparts their domain (e.g., $ E S.a A). We consider episodic Markov Decision Processes (MDPs) of the form M (S. A. Paut: Permu::" r), with states E S, actions a AA. initial state distribution (5)). state transition distribution Prone (8 (8, (z), and reward function r S R. For simplicity, we assume finite episodes of length T, that is, T = (s0, ., 8T), |T| T Together with control mechanism represented by a stochastic policy I (acls))) the MDP defines probability distribution over trajectories, namely
|r|-1
Pa (T) = Pimit
II
π (a Prons 18t, Oz).
t=o
The MDP control problem is to find a policy that maximizes the expected cumulative reward, π² E arg max, V*, with
Irl Σ
E TrupT
r(())
key property of MDPs is the temporal Markov property Se+1 IL Se. St, Ar, Vt, which guarantees that the future only depends upon the current state and action. One consequence of this property is
'The local lower bound is oo if the LP is infeasible.
TThe local upper bound oo if the LP infeasible, or its solution is not MILP feasible. 'Equivalently, we can assume all trajectories will reach an absorbing. zero-reward state Smult in a finite number of steps, that is, Poonr (St-1)tt1 Smili, as) 8e,m (St+1) ). r ((sui)) O, and 31' s.t. pr (ST Smitt) = 1, VT.
3

---

the temporal policy gradient theorem [4]
which forms the basis of policy gradient methods
17|
V
V
E ToPa
v log (()l)))
Σ r(sp)
(4)
t=0
1=t+1
2.3 The branching temporal MDP
Let us now consider the problem of learning a branching policy in a B&B solver. As noted by 17 branching decisions are made sequentially, thus the problem can naturally be regarded as temporal MDP. In this form, the states consist of the entire state of the B&B process (that is, the solver) at time f. which includes the whole tree structure, all sub-MILPs and LP solutions, and all upper and lower bounds. The actions Oe are the branching decisions, and the reward is chosen so that the return matches an objective function of interest (e.g., the final B&B tree size).
While appealing by its simplicity, we argue that this formulation is not practical for two reasons. First, even in the simplest textbook implementation of B&B, the MDP states are complex objects of growing size, which are impractical to handle. Second, episode length in branching can grow extremely large, in the worst case exponentially with the size of the problem. This exacerbates the so-called credit assignment problem, i.c., the problem of determining which actions should be given credit for certain outcome (see Section 3..2 for more detailed discussion). In Section [ we will we will show how the tree MDP formulation addresses both those challenges.
3 Approaches to learning to branch
Approaches that frame branching as a learning problem have gained significant attention recently. In this section, we review some common trends in the field and identify some key challenges.
3.1 Learning to branch with imitation learning
In recent years, it has been demonstrated that efficient branching rules can be obtained by learning fast approximations of strong branching, globally effective but computationally expensive rule
19 36, 29]. This approach can be framed as imitation learning, a well-known method for learning in MDPs when an expert is available. While this approach can lead to improvements over ofate-of-the-arr branching rules on various benchmarks, it also has several drawbacks.
23
26 20
17
First, strong branching implementations are known to trigger side effects (such as early detection of an infeasible child) that do not map well within the branching MDP framework [14). This means that branching decisions collected from the strong branching expert might not line up with the environment of the learning agent, which might result performance gap between the learning agent and the expert, even if the agent manages to successfully reproduce the expert decisions.
Second, other than these side-effects, strong branching relies dual bound improvements to make branching decisions. This can be ineffective in problems where the IP relaxation is not very informative or suffers from dual degeneracy, as pointed out in Gamrath et al. [16]. As extreme case, Dey et al. 9 provide an example where a more nodes than the tree obtained with a problem-specific rule.
based B&B tree can have exponentially
Finally, regardless of the expert quality, obtaining strong branching samples can become prohibitively expensive for large instances. This means that non-trivial engineering solutions and scaling strategies are needed to allow training on larger problems, such as heavy computational parallelization [2]].
3.2 Learning to branch with reinforcement learning
The reasons listed above suggest the need for an alternative approach to finding good branching policy; an approach that does not rely on the strong branching rule. One could perform imitation learning on another expert, but no other plausible imitation target known, and the same performance ceiling issue would remain. A natural alternative is reinforcement learning, approach that aims to find an optimal policy in Markov Decision Process, with respect to any desired objective function. But despite the theoretical appeal of RL for learning to branch, it also comes with its own challenges.

---

First, common evaluation metrics in B&B, such as solving time or final tree size, are inconvenient for RL. Both require run episodes completion, that is, to solve MILP instances optimality. which leads to very long episodes even for moderately hard instances. Second, in contrast to many RL tasks studied in the literature, in B&B the worse the policy is, the longer are the episodes. These two factors combined give rise to the following problems:
1. Collecting training data is computationally expensive. In particular, training from scratch from a randomly initialized policy can be prohibitive for large MILPs.
2. Due to the length the episodes, training signals are partieularly sparse. This exacerbates the so-called credit assignment problem (27]. i.e., the problem of determining which actions should be given credit for a certain outcome.
Two works have tried to tackle the branching problem with RL so far. Sun et al. approach based evolution strategies, variant of RL, combined with a novelty bonus based on discrepancies in B&B trees. They show improvements over an imitation learning approach Gasse et al. [17 on instances derived from common backbone graph, but fail to improve more heterogeneous ones. These results emphasize the difficulty of a direct application of RI. on hard instance sets.
3 propose an
In parallel, Etheve et al. [1] recently made a contribution that directly addresses the credit assignment problem. They show that, when depth-first-seae
(DFS) is used as the node selection strategy, minimization of the total B&B tree size can be achieved by taking decisions that minimize subtree size at each node. Based on this result, they propose a Q-learning-tyee learned Q-function approximates the local subtree size. They report improvements over state-of- the-art branching rule on collections of small, fixed-size instances. However, they only evaluate the learned policy with DFS node selection, which matches their training setting, but is not realistic B&B setting. In Section 4 we will show that the method proposed by Etheve et al. [[]] can be interpreted as specific instantiation of more general free MDP framework, which effectively simplifies the credit assignment problem in learning to branch (point above). Furthermore, we propose an alternative condition to the one of Etheve et al. [11] ensure tree MDP setting, which results in shorter episodes, hence reducing the cost of data collection (point I above).
algorithm (28) where the
4 Branching as a tree MDP
We now detail our tree MDP framework, and show how the branching problem can be cast a tree MDP control problem, under some conditions. Proofs as well as side-by-side comparison of temporal and tree MDPs are deferred the Supplementary Material.
4.1 Tree MDPs
We define tree MDPs as augmented Markov Decision Processes tM (S. A. Piir Pis Pate r, I). with states s E S, actions E A, initial state distribution (mnr(so), respectively left and right child transition distributions P |si, az) and ( 18; az reward function r S - IR and leaf indicator 1: S {0, 1.. The central concept behind tree MDPs is that each non-leaf state 8; (i.e., such that I(s,) = 0), together with an action a; produces two new states $,-- (its left child) and s (its right child). As result, the tree MDP generative process results in episodes that follow a tree structure (see Figure D. where leaf states (i.e., such that I(s;) = 1) are the leaf nodes of the tree, below which no action can be taken and no children state will be created. For simplicity, just like in we assume the tree-like trajectories have some finite size that we denote T |r|-
Section 2.2
A tree MDP episode T consists of binary tree with nodes N =
and leaf nodes L= {ili E 1(s)))) = 1). which embeds state s; at every node E A and an action a, at every non-leaf node E A \, L. For convenience, in the following we will the nodes that are respectively parent, left child and right child of a node if any, as well as de and nd; to denote respectively the set of all descendants and -on-eescesdsnts of node in the tree. Together
pa,, ch; and chat to denote
In the case of branching, these transitions are deterministic.
TTee concept can easily be extended non- binabinary trees.
5

---

with control mechanism ( st), tree MDP defines a probability distribution over trajectories,
Pr (T) = Pimie (#o)
(aas(8))Po (Sch, 18s, O. Pas (Sos) (s)...). TENIC
II
As in temporal MDPs, the tree MDP control problem is find a policy that maximizes the expected cumulative reward, as defined by 3 Due to their specific generative process, a key characteristic of tree MDPs is the tree Markov property : TL Snd; [. A,, Vi. which guarantees, similarly to the temporal Markov property, that each subtree only depends upon the immediate state and action. This again simplifies the credit assignment problem in RL and results in an efficient tree policy gradient formulation.
Proposition 4.1. For any tree MDP tM, the policy gradient can be expressed as
V.V==
E TrupT
Σ
V log ((clss)
r(ss))
(5)
LiENVe
jEd.
4.2 The branching tree MDP
We now show how and under which conditions the vanilla B&B algorithm can be formulated as tree MDP. We consider episodes T that follow exactly the B&B tree structure. Each node in the tree embeds a state = (MILP;, GUB:), where MILP; is the local sub-MILP of the node, and GUB; is the global upper bound at the time the node is processed Each non-leaf node also embeds an action a, (j, 4,)) where is the index of the branching variable chosen by B&B, and x; is the value used to branch (2j S |aj] V zj 2 [2]] 1). Note that such states and actions, embedded in the B&B tree, carry enough information to unroll a vanilla B&B algorithm, as described in Section [2. We now need make two additional assumptions in order formulate branching as tree MDP.
4.2.1 B&B tree transitions
First, and this is our main requirement, B&B state transitions must decompose into Pet. and Per Assumption 4.2. For every non-leaf node i, the global upper bounds GUB ct, and GUB di (reached by B&B when the left and right child is processed, respectively) can be derived solely from the current state and action, (st, a.).
Proposition 4.3. A vanilla B&B algorithm that satisfies Assumption 4.2 forms tree MDP
Assumption 4.2 is not always satisfied, the following counterexample shows.
Counter example. Consider the root problem MILP, min z s.t. x 0.6, Z. with upper bound GUB, = oc. The root LP solution is f 0.6, and the two sub-problems MILP ch, and MILP oh! follow from the (only) branching decision x < 0 x 2 1. Now, the two global upper bound GUB dt; and GUB ck! depend on whether the feasible solution
has been found in the past, which in turn depends on the node processing order. Going left first (-) will yield (GUB ,GBB ont)) = (oo, oc),
while going right first (+) will yield (GUB di; GUB dx ) (l)
We now provide two conditions under which Assumption 4.2 is true.
Proposition 4.4. In Optimal Objective Limit B&B (Objl im B&B), that is, when the optimal solution value of the MILP is known at the start of the algorithm (GUB, GUB"), ), Assumption 4.2 holds.
Proposition 4.5. In Septh-First-eaade B&B (DFS B&B), that is, when nodes are processed depth- first and left-first by the algorithm, Assumption 4.2 holds.
Propositions/ 4.4 and 4.5 provide two viable options for turning vanilla B&B into a tree MDP, where Per and Pas are deterministic functions. The first variant, ObjLim, requires MILP instances used for training to be solved to optimality once, in order to collect their optimal objective value. The second variant, DFS, corresponds to the setting in [.. In this variant there is no need to pre-solve training instances to optimality, however it is expected that the collected episodes might be longer than with a standard node selection rule, which might result in slower training.
'Recall that in B&B, the GUB corresponds to the value of the best feasible solution found so far, oc when no solution has been found yet.

---

4.2.2 B&B tree reward
Last, for branching to formulate as control problem in a tree MDP, the objective must be compatible. Assumption 4.6. The branching objective can be decomposed over the nodes of the B&B tree, with a state-based reward function S R.
Interestingly, natural objective for branching is the final B&B tree size, which expresses naturally as r(s;) = -1. Thus, it trivially compatible with Assumption 4.6 We will consider this reward in our experiments. Another common objective is the total solving time, which can also be expressed as state-based reward r + R under mild assumptions. Indeed, it suffices to considers that solving LP relaxations and making branching decisions at each node are the main contributing factors in the total running time, while other algorithmic components have negligible cost. In vanilla B&B, both these components only depend the local state s, (MILP;, GUB,) of each node.
4.3 Efficiency of tree MDP
Tree MDPs, when applicable, provide a convenient alternative to temporal MDPs for tackling the branching problem. First, the tree Markov property implies that branching policies in tree branching MDPs will not benefit from any information other than the local state 8; = (MILP,, GUB,) to make optimal decisions, similarly to how control policies in temporal MDP can ignore past states and rely only on the immediate state 8t- Second, the credit assignment problem in the branching tree MDP is more efficient than in the equivalent temporal MDP. This is showcased in Figure [ and stems from the fact that in a tree MDP all the descendants of node i are necessarily processed after that node temporally. As consequence, the rewards credited to an action in the tree policy gradient (5). Lij,, r(sz), ). are necessarily a subset of the rewards credited to the same action in the temporal policy gradient (4). Ee't r(ser) Thus, it can be expected intuitively that learning branching policies within the tree MDP framework will be easier, and more sample-efficient than learning within the temporal MDP framework. We will validate this hypothesis experimentally in Section
4.4 Theoretical limitations
Our proposed B&B variants, ObjL.i and DFS, allow for a nice formulation of the branching problem as tree MDP, which we argue is key unlocking a more practical and sample-efficient learning of branching policies. However, usually the end goal is to learn branching policy that performs well in realistic B&B settings, and the fact that a branching policy performs well in of those variants does not guarantee that it will perform well in the vanilla setting also. This discrepancy between the training environment and the evaluation environment is recurring problem in RL, and is more generally referred to as the transfer learning problem. While there exist solutions to mitigate this problem, in this paper we leave the question aside and simply assume that the transfer problem is negligible. We thus directly report the performance obtained from each training setting in the realistic evaluation setting, default B&B solver.
4.5 Connections with hierarchical RL
The tree MDP formulation has connections with hierarchical RL (HRL), a paradigm that aims at decomposing the learning task into set of simpler tasks that can be solved recursively, independently of the parent task. The most related HRL approach is perhaps MAXQ [00. which decomposes the value function of an MDP recursively using finite set of smaller constituent MDPs, each with its own action set and reward function. For example, delivering a package from a point A to a point B decomposes into: moving to A, picking up package, moving to B, dropping package. While both tree MDP and MAXQ exploit a recursive tree decomposition in order to simplify the credit assignment problem, the two frameworks also differ on several points. First, in MAXQ the hierarchical sub-task structure must be known a priori for each new task, and results in a fixed, limited tree depth, while in tree MDPs the decomposition holds by construction and can result in virtually infinite depths. Second, in MAXQ each sub-task results in different MDP, while in tree MDPs all sub-tasks are the same. Lastly, in MAXQ the recursive decomposition must follow a temporal abstraction, where each episode is processed according to a depth-first traversal of the tree. In tree MDPs the decomposition not tied to the temporal processing order of the episode, except for the requirement that a parent must be processed before its children. Thus, any tree traversal order is allowed (see Figure II.
7

---

Algorithm REINFORCE training loop
1: Input: training set of MILP instances and their pre-computed optimal solution D, maximum number of epochs K, time limit Ç, entropy bonus X, learning rate a, sample rate B.
2: Initialize policy with random parameters 8.
3: for epoch from 1 to K do
4: if' clapsed time > Ç then break
5: Sample 10 MILP instances from D
6: for each sampled instance do
7: Collect one episode by running B&B to optimality
8: Extract randomly 3 x |r| state, action, return tuples (s, G) from (with G the local
subtree size for tree MDPs, and the remaining episode size for MDPs 9: end for
n f number of collected tuples, L 5- for each collected tuple (s, a, G) do
11:
12:
+ _ log To (a) (a]s) policy gradient cost
13:
L L- A H Ta (-1s)) # entropy bonus
end for
15: 0 4- V
end for
17: return T
Experiments
We now compare the performance of four machine learning approaches: the imitation learning method of Gasse et al. [17), and three different RL methods. We also compare against SCIP's default rule (for description of this rule we refer to the Supplementary Material A.4p. Code for reproducing all experiments is available online
5.1 Setup
Similarly to Gasse al. [17), we train and evaluate each method on five NP-hard problem benchmarks, which consist of synthetic combinatorial auctions, set covering, maximum independent set, capacitated facility location and multiple knapsack instances. For each benchmark we generate training set of 10,000 instances, along with a small set of 20 validation instances for tracking the RL performance during training. For the final evaluation, of 40 instances, the same size as the training ones, and also a transfer set of 40 instances, larger and more challenging than the training ones. More information about benchmarks and instance sizes can be found in the Supplementary Material A.5
Benchmarks
further generate a test set
Training We use the Graph Neural Network (GNN) from Gasse et al. 17 to learn branching policies, with the same features and architecture. This state representation has been shown provide an efficient encoding of the local MILP together with some global features. Notice that this makes the MDP formulation into POMDP, given that do not encode the complete search tree (see Section 2.3). We compare four training methods: imitation learning from strong branching (II.); RL using temporal policy gradients (MDP); RL using tree policy gradients with DFS node selection strategy (LMDP+DFS), which enforces the tree Markov property due to Proposition 4.5) and RL using tree policy gradients with the optimal objective value set an objective limit (IMDP+ObjLim)) which corresponds to Propositions 4.4 Other than that, we use default solver parameters, except for restarts and cutting planes after the root node which are deactivated. We use plain REINFORCE (35] with entropy bonus as our RL algorithm. for simplicity. Our training procedure is summarized in Algorithm [ We a maximum of 15,000 epochs and a time limit of six days for training. Our implementation uses Py Torch 31 together with PyTorch Geometric [12], and Ecole [32] for interfacing to the solver SCIP [5 All experiments are run on compute nodes equipped with a GPU.
httpp::/githuu: httpps/s/ggttab...oo/aaaaaaaaaaa www/lassavaaa/rllll...
"Notice that for tree MDPs the computation of the return for each node can be computed efficiently with bottom-up traversal that runs in (n))

---

Theee size (geametric: mean))
Tree size (geormetric mean)
Training samples
Training samples
Training samples
in
(a) Combinatorial Auctions
(h) Set Covering
(c) Maximum Independent Set
Training curves for REINFORCE with temporal policy gradients (MDP), tree policy gradients with objective limit (IMDP+ObjLim) and DFS node selection (IMDP+DFS). We report the final B&B tree size on the validation set (geometric mean over 20 instances x 5 seeds, the lower the better), versus the number of processed training samples on the x-axis. Solid lines show the moving average. Training curves for the remaining benchmarks can be found in the Supplementary Material (A.3).
Figure 2:
Evaluation For each branching rule evaluated, we solve every validation, test or transfer instance times with a different random seed. We use default solver parameters, except for restarts and cutting planes after the root node which are deactivated (same as during training), and a time limit of I hour for each solving run. For tMDP+DFS and tMDP+ObjLimg the specific settings used during training (DFS node selection and optimal objective limit, respectively) are not used any more, thus providing a realistic evaluation setting. We report the geometric mcan of the final B&B tree size as our metric of interest, as is common practice in the MILP literature 33. We pair this with the average per-instance standard deviation (in percentage). We only consider solving runs that finished successfully for all methods, as in 17 Extended results including solving times are provided the Supplementary
Material A.3
5.2 Results
Figure showcases the convergence of our three RL paradigms MDP, LMDP+ObjLim and LMDP+DFS during training, in terms of the final B&B tree size the validation set (the lower the better). In order to better highlight the sample efficiency of each method, we report on the x-axis the cumulative number of collected training samples, which correlates with the length of the episodes collected during training. This provides a tree MDP paradigm clearly improves the convergence speed these three benchmarks, with clear domination of tMDP+ObjLim on one benchmark (Set Covering). Training curves for the remaining benchmarks are available in the Supplementary Material (A.3).
proxy for training time. As can be seen, the
Table reports the final performance of the branching rules obtained with cach method, on both held-out test set (same instance difficulty training) and a transfer set (larger, more difficult instances than training). Despite a mismatch between the training and evaluation environments, which is required enforce the tree Markov property, the tree MDP paradigm consistently produces equal or better branching rules than the temporal MDP paradigm on all benchmarks.
On one benchmark, Multiple Knapsack, the branching rules learned by RL outperform both SCIP's default branching rule and the strong branching imitation (II.) approach. The likely reason that the MILP formulation of Multiple Knapsack provides very poor linear relaxation, which often results in no dual bound improvement after branching. This means that strong branching scores are in most cases not discriminative, which is problematic for rules that heavily rely on this criterion (see Section 3.T), such as SCIP's default or a policy that imitates strong branching. This situation makes a strong case for the potential of RL-based methods, which can adapt and devise alternative branching strategies.
On the remaining 4 benchmarks, however, RL methods perform worse than SCIP default or IL, despite being based on the same GNN architecture. This illustrates the difficulty of learning to branch via RI, even small-scale problems, and the remaining room for improvement. Additional evaluation criteria (solving times and number of time limits) are available in the Supplementary Material A.3

---

Table 1: Solving performance of the different branching rules in terms of the final B&B tree size (lower is better). We evaluate each method on test set with instances the same size as training, and a transfer set with larger instances. We report the geometric mean and standard deviation over 40 instances, solved 5 times with different random seeds, and we bold the best of the RI. methods.
Model
Comb. Auct.
Set Cover
Mnx.Ind.Set
Facility Loc.
Mult. Knap.
SCIP default
7.3.1.9%
10.7.:24%
19.3.152%
203.611639
267.8 228.0:195%
IL
52.2:1 13%
51.8.1: 10%
35.91136%
247.5.1.9%
RL (MDP)
86.7#:165
19%0
91.8+:66%
393. 393.2 4::%%
143.4=76%
RL (IMDP+DFS)
86.1-:17%
190.8:120% %
89.8:1:519 %
460.4:1466
133,8:1:70 %
RL (IMDP+ObjiLim
87.0:t 18%
193.5-:23%%
85.4:1.53%
325.4
142.4: 78%
Test
Model
Comb. Auct.
Set Cover
Inx.Ind.Set
Facility Loc.
Mult. Knap.
SCIP default
733.9
61,4+19%
2867. 1 335%
344.3==57%
592.3=
IL
805.1.19%
145.0:16%
1774.8
407.8:1.7%
1066. 1666.11110 101
RL (MDP)
1006.311889
853.3++27%
76%
679.4=:52%
518.4=79%
RL (LMDF+DFS)
1804.6+11%% %
816.8+255% %
2970.0==666
609.1=477%
495.1
RL (IMDP+Objl..mm
1841.9--1899 18%
826.4-1-26%
2763.6 74%
496.0
425.3-1 64%
Transfer
Conclusions and Future Directions
This paper adds to a growing body of literature on using ML to assist decision-making in several key components of the B&B algorithm (see e.g. 5 221). ) We contribute to the study RL as tool for learning to branch in MILP solvers. We present tree MDP, variant of Markov Decision Processes, and show that under some conditions, the B&B branching process the approach of Etheve et al. [1] can be naturally cast as Q-learning for tree MDPs, and we propose an alternative, more computationally appealing way to enforce the tree Markov property in B&B, using optimal objective limits. Finally, we evaluate for the first time a variety of RL-based branching rules a comprehensive computational study, and we show that tree MDPs improve the convergence speed of RL for branching, as well as the overall performance of the learnt branching rules.
Merk-vaaovi.n. We show that
These contributions bring closer learning efficient branching rules from scratch using RI, which could ultimately outperform existing branching heuristics built upon decades of expert knowledge and experiment. However, despite the convergence speed-up that our method provides, training without expert knowledge remains very computationally heavy and in general still results in worse performance than its supervised learning counterpart, which reveals a significant gap that must be closed. As future work, we would like to explore ideas to keep improving sample efficiency, and generalization across instance size. This necessary for RL to scale to larger, non-homogeneous benchmarks, such as MIPLIB [18] which at the moment remain out-of-reach for RL.
Finally, although our concern in this paper is focused improving variable selection for MILP, our tree MILPP construction could be useful in other applications. Branch-and-bound is type of divide-anddconquer algorithm, and we expect that, in general, this framework can be applied to any problem where one seeks to control such algorithms more efficiently. Examples would include controlling the order in which rover explores rooms in a building, or selecting the pivots quicksort algorithm.
Acknowledgements
The authors thanks the anonymous reviewers for their suggestions. The work of Karen Aardal, Lara Scavuzzo and Neil Yorke-Smith was partially supported by TAILOR. a project funded by EU Horizon 2020 research and innovation programme under grant number 952215, and by The Netherlands Organisation for Scientific Research (NWO), grant OCENW.GROOT.20001 work of Feng Yang Chen, Didier Chételat, Maxime Gasse and Andrea Lodi was supported by the Canada Excellence Research Chairs program (CERC).
The
10

---

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 Integration of Construint Progrumming, 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 Oplimization, 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' d'horizon. European Journal of Operational Research, 2020.
[6] David Bergman, Andre Cire, Jil 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 heuristies branch-and-bound. arXiv preprint arXiv:2103. 100204940 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):20-2277, 1991.
[9] Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. A theoretical and computa- tional analysis of full strong-branching. arXiv preprint N0. 2021.
[10] Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of Artificial Intelligence Research, 13:227-303, 2000.
[11] Mare Etheve, Zacharie Alès, Côme Bissuel, Olivier Juan, and Safia Kedad-Sidhoum. Re- inforcement 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 20/7, pages 165-170. Springer, 2018.
[15] Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Fifler, 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, Mare 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, 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):441-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 Neural Information Processing Systems, pages 15580-15592, 2019.

---

[18] Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarek, 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-drives framework for guiding combinatorial solvers. In AAAI, 2022.
[23] Elias Boutros Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learn- ing 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: 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-bourd Technical report, Universite de Liege, 2016.
[27] Marvin Minsky. Steps toward artificial intelligence. Proceedings of the IRE, 49(1)88-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' 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. Gamett, 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 NewrIPS 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. Citescer, 1999.
12

---

[35] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine Learning. 8(3):229-255)
1992.
[36] Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and- search trees to learn branching policies. In AAAI, pages 3931-3939, 2021.
13


Reviews:
[{"review_id": "xHA6V2nlw_", "reviewer": "Reviewer_NiZ2", "summary": "The main contribution of this paper is a new type of augmented MDP formulation called a “tree MDP”, which is motivated by the “learning to branch” problem in mixed-integer linear programming (MILP). The intuition is to convert the default MDP formulation, which we can think of to be defined over subtrees, into a simpler formulation that is defined over nodes instead. The authors then show computational experiments on a set of benchmarks, showing that the new MDP formulation is more amenable for RL.", "questions": "Questions:\n[Side-by-side comparison] It would be nice to have a side-by-side comparison between the temporal MDP formulation and the tree-MDP formulation, where the states, actions, reward, and definition of episode are compared.\n[Requirement of optimal solutions] In Section 3.2, it is mentioned that one of the drawbacks of the standard approach is that “...require to run episodes to completion, that is, to solve MILP instances to optimality, which leads to very long episodes even for moderately hard instances.” However, based on my understanding, the ObjLim version also requires this so it would be nice to properly contextualize some of this (e.g., “with a certain assumption, we can get rid of this requirement”). For the side-by-side comparison mentioned in the point above, it would also be good to mention which assumptions are needed.\n[Deterministic MDP formulation] As I was reading through Section 4.1, I was a little thrown off by what is meant by p_ch^- and p_ch^+ since I expected them to be deterministic. It is later specified that the MDP is indeed deterministic (line 215). I wonder if it would be clearer to define a tree MDP only for the deterministic case, rather than in full generality. Is there any point that we need a stochastic tree MDP?\n[Other applications of tree MDP] Related to the above, can the authors point to other applications where a tree MDP might be useful? If so, this would be a good reason to present the general setup of a tree MDP.\n[Exponentially sized episodes and more difficult policy gradient computation] The paper emphasizes that the states and rewards for a tree MDP are localized to the specific nodes. It would be good to also emphasize that the trade-off here is that each episode is now a tree and therefore can blow up in size -- this trade-off now makes the policy gradient computation more difficult, since it requires a sum over all nodes. If I misdiagnosed the drawback, please correct me, but my concern here is that a cursory read might suggest to a reader that all aspects are simplified compared to before.\n[Temporal RL algorithms] In a policy gradient setting, I can see that a tree MDP can be used because the entire episode is run and then (s, a, G) are extracted. Could tree MDPs be used with algorithms like Q-learning that make stronger use of the temporal MDP setup? It is not clear to me that they could because in order to compute an immediate reward, one would need to wait for both child states to be evaluated. Some clarity / discussion on this would be nice!\n[Capitalized states and actions] In line page 5, line 182, the states and actions are capitalized -- is this a typo or does it have some significance?\n[Figure 1] In Figure 1, the dotted lines are not explained (although I realized that they mean the node was pruned). It would be good to clarify. \n[GNN] What exactly is the state fed to the policy for each of the different algorithms? I was confused by the statement that “same features and architecture” for the GNN are used, but I thought that the states for the MDP / tree MDP approaches are quite different.\n[Computational results] What does 1804.6 +/- 17% mean? Is the 17% defined to be 1804.6 +/ 0.17*1804.6? Why do we use geometric mean here? Would the results be different if sample mean were used?", "limitations": "They have to some extent, but I have also asked for a few more points in the Questions section above.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I found the tree MDP idea used in the paper to be novel, creative, and directly targets the motivating problem without extraneous features and believe that this is a valuable contribution to the literature on applying RL to MILP.\n\nWeaknesses: The ideas in the paper took me some time to properly digest. I believe (nearly) all of the information needed for the reader to digest is there, but think that the paper could make this process easier on the reader. Please see the questions below for specific queries.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cUaQnx2UQ9_", "reviewer": "Reviewer_hf9x", "summary": "The paper proposes a tree MDP formulation for learning to branch in MILP branch-and-bound algorithms. A policy gradient algorithm for solving MILP tree MDPs is proposed. Conditions for the correctness of the algorithm are derived. The paper compares the tree MDP formulation with the vanilla RL formulation as well as a strong baseline (default SCIP) on 5 benchmark problem sets. The main empirical result shows that the tree MDP formulation outperforms the vanilla RL formulation but does not outperform SCIP in 4 out of 5 problems. Similar results are observed for the transfer learning experiments.\n\n--------\n\nUPDATE: I thank the authors for their detailed responses. After reading the other reviews and the responses, I'm a bit more positively inclined towards the paper although the computational performance remains a bit of an issue for me. I've upgraded my score to a Weak Accept.", "questions": "1. How novel is the tree MDP formulation?\n  - What, if any, relationship, does tMDP have to a recursively-optimal hierarchical RL algorithm like MAXQ [Dietterich99])?\n\n2. Does the tree MDP formulation have other applications besides B&B trees for MILPs?\n\n3. Why does tMDP outperform SCIP default on Multiple Knapsack? Is it possible to characterize how the branching rule learned in tMDP is overcoming the poor relaxation (assuming that's the root cause)? Can the presence / absence of the poor relaxation be verified experimentally?", "limitations": "There is a discussion on the limitations and social impact in the checklist (but not the main paper). The authors could consider moving it to the main paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n  + There appear to be a number of novel algorithmic contributions (tree MDP, using tree MDPs to encode B&B trees for MILPs, policy gradient algorithm for tree MDPs).\n  + The proposed approach seems well-motivated, intuitively clear with correctness guarantees for ObjLim and and DFS (although I didn't check these carefully). Combined with the novelty, this makes the paper interesting in itself.\n  + The paper is tackling a problem of significant practical importance (B&B, MILPs) and improvements here would have a large impact.\n  + The paper is clearly written and the proposed ideas and experiments are easy to follow.\n\nWeaknesses\n  - The empirical results don't show improved performance over the baseline in 4 out of 5 cases. In the case where it does well (Multiple Knapsack), there is no deeper analysis. Overall, the experimental section provides limited insight into the empirical characteristics of tMDP compared to SCIP.\n  - It's unclear if the tree MDP formulation can be used in other applications. The paper does not place the tree MDP formulation into the broader (and large) body of work on MDPs. As a result, it becomes difficult to assess the impact of the algorithmic contributions. (This is reflected in my score for presentation and contribution.)\n  - The baseline (SCIP branching rule) is not described and the description strong branching is very brief. Coupled with the above, it becomes difficult to place the proposed ideas into the existing body of knowledge.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RxZ1XxU8yw3", "reviewer": "Reviewer_Je2V", "summary": "This paper proposes a new Tree MDP theory and formalizes the branching problem as a Tree MDP problem.\nUnder this new formulation, the resulting algorithm benefits sample efficiency and credit assignment.", "questions": "\nQuestions:\nMy major concern is how could the method be generalized to the test environment? In other words, does there exists an optimal policy that can map the MIP problem into an action?\n\nAlthough the authors have discussed the limitations in Section 4.4, I think this is the fundamental point about the method, as it is the key to the soundness of the method. I think the paper should discuss more on that.\n\nSome related questions are as follows:\n\n1. What's the architecture of policy \\pi_\\theta in your implementation? \n2. In line 190, the state is embedded as MILP_i, GUB_i. How to embed a MILP_i? This is a critical problem for generalizing the policy for testing.\n\nSome points are not clear to me:\n\n1. It is not clear to me why a state (MILP_i, GUB_i) can carry enough information to unroll a vanilla B&B algorithm.\n2. For a B&B tree in Figure 1, if h is the current state, then it expands from h. After several iterations, is that possible that the policy will still expand d or c or g? ", "limitations": " ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nThis paper proposes a novel Tree MDP theory, which is well fitted for the branching problem.\nThe new tree MDP formulation has an obvious advantage over the existing MDP formulation.\n\nHowever, the paper has some basic theoretical flaws.\n\nMy major concern is how could the method be generalized to the test environment? In other words, does there exists an optimal policy that can map the MIP problem into an action?\n\nAssumption 4.2 is strong to me. The paper has offered two conditions in Proposition 4.4 and 4.5.  \n\nHowever, in P 4.4, if the optimal value is provided, the problem is reduced to another easier problem with equality constraint (is this true?).\nIn P 4.5, the algorithms can be limited to a very limited scope. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept