A Markov Decision Process for Variable Selection in Branch & Bound
Authors: Paul STRANG
Zacharie ALES
Côme Bissuel
Olivier Juan
Safia Kedad-Sidhoum
Emmanuel Rachelson
Venue: NeurIPS 2025 poster ()
Keywords: Mixed-integer linear programming
Branch and bound
Reinforcement learning
Markov decision process
Primary area: optimization
TL;DR: We enhance the potential for reinforcement learning applications in mixed-integer linear programming by modeling variable selection in Branch and Bound as a Markov decision process.

Abstract: Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms to the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP, a principled vanilla MDP formulation for variable selection in B&B, allowing to leverage a broad range of RL algorithms for the purpose of learning optimal B&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-art RL agents on four standard MILP benchmarks.

A Markov Decision Process for Variable Selection in Branch & Bound
Paul Strang EDF R&D. France CNAM Paris, France stuangeead fr
Zacharie Ales ENSTA IP Paris, France CNAM Paris, France zacharie. ales@ensta. fr
Côme Bissuel EDF R&D, France come bissuel@edf
Olivier Juan EDF R&D, France olivier, olivier.juan@ede fr
Safia Kedad-Sidhoum
CNAM Paris, France
safia. kedad..iddooommmenn.
Emmanuel Rachelson ISAE-SUPAERO, France
Abstract
Linear Programming (MILP) is powerful framework used to ad- dress a wide range of NP-hard combinatorial optimization problems, often solved by Branch and bound (B&B). A key factor influencing the performance of B&B solvers is the variable selection heuristic governing branching decisions. Recent contributions have sought to adapt reinforcement learning (RL) algorithms the B&B setting to learn optimal branching policies, through Markov Decision Processes (MDP) inspired formulations, and ad hoc convergence theorems and algorithms. In this work, we introduce BBMDP. a principled vanilla MDP formu- lation for variable selection in B&B, allowing leverage broad range of RL algorithms for the purpose of learning optimal B&B heuristics. Computational experiments validate our model empirically, as our branching agent outperforms prior state-of-the-ann RL agents on four standard MILP benchmarks.
Introduction
Mixed-Integer Linear Programming (MILP) is subfield of combinatorial optimization (CO), a discipline that aims at finding solutions to optimization problems with large but finite sets of feasible solutions. Specifically, mixed-integer linear programming addresses CO problems that are NP-hard, meaning that no polynomial-time resolution algorithm has yet been discovered to solve them. Mixed-integer linear programs used solve efficiently vast range of high-dimensiooal combinatorial problems, spanning from operations research [Hillier and Lieberman, 2013) to the fields of deep learning (Tjeng al. 2019]. finance MMansini al. 2015). computational biology Gusffeld 2019). and fundamental physics Barahona 1982]. MILPs Ps are traditionally solved using Branch and bound (B&B) [Land and Doig 1960), algorithm which methodically explores the space of solutions by dividing the original problem into smaller sub-problems, while ensuring the optimality of the final returned solution. Intensively developed since the 1980s [Bixby] 2012). MILP solvers based on the B&B algorithm are high-performing tools. In particular, they rely on complex heuristies fine-tuned by experts on large heterogeneous benchmarks [Gleixner et al., 2021] Hence, in the context of real-world applications, in which similar instances with slightly varying inputs are solved on regular basis, there huge incentive to reduce B&B total solving time by
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

learning efficient tailor-made heuristics. The branching heuristic, or variable selection heuristic, which determines how to iteratively partition the space of solutions. has been found to be critical to B&B computational performance [Achterberg and Wunderling 2013]. Over the last decade, many contributions have sought to harness the predictive power of machine learning (MI.) to learn netter-performing B&B heuristics [Bengio et al., 2021 Scavuzzo et al. 2024]. By using imitation learning (IL) to replicate the behaviour of a greedy branching expert at lower computational cost, Gasse et al. [2019] established landmark result as they first managed to outperform solver relying on human-expert heuristics. Building on the works of Gasse et al.] [2019] and He et al. (2014), who proposed Markov decision process (MDP) formulation for node selection in B&B, several contributions succeeded in learning efficient branching strategies by reinforcement (Etheve et al.
2020 Scavuzzo et al. 2022 Parsonson et al.) [002]. without surpassing the performance achieved by the II. approach. Yet, the performance of II. heuristics are caped by that the suboptimal branching experts they learn from, the performance of RI. branching strategies are, in theory, only bounded by the maximum score achievable. We note that in order to cope with dire credit assignment problems (Pignatelli et al. (2033) induced by the sparse reward model described in He et al. (2014),
prior research efforts have shifted away from the traditional Markov decision process framework, finding it impractical for learning efficient branching strategies. Instead, [Etheve al. 20220)
Scavuzzo et al. [0022] and Parsonson et al.) [2022] have adopted unconventional IDP-inspired
formulations to model variable selection in B&B.
In this work. we show that, despite improving the em- pirical performance of RI. algorithms, these alternative formulations introduce approximations which undermine the asymptotic performance of RL. branching agents in the general case. In order to address this issue, we introduce branch and bound Markov decision processes (BBMDP), a principled vanilla MDP formulation for variable selection in B&B, which preserves convergence properties brought by previous contributions without sacrificing optimality. Our new formulation allows to define proper Bellman optimality operator, which, turn, enables unlock the full potential of state-of of-the-art approximate dynamic pro- gramming algorithms (Hessel et al.] 2007 Dabney al.] 2018. Farebrohrrr et al., 2024] for the purpose of learning optimal B&B branching strategies. We evaluate our method on four classic MILP benchmarks, achieving state-of-the art performance and dominating previous RL agents while narrowing the gap with the IL approach of Gasse et al. [2019] as shown in Figure
Noraalzed performance
10a
995
137
10a
100
82
random
DON- DON-
Retro
Figure 1: Normalized scores in log scale of IL, RL and random agents across the Ecole benchmark Prouvost et al. [2020].
2 Problem statement
2.1 Mixed-integer linear programming
We consider linear programs (MILPs), defined as:
min c Tx x P: I S S u
Ax < b; x IEZI X RZ
with n the number of variables, the number of linear constraints, 1, IR" the lower and upper bound vectors, E RR the constraint matrix, b E TT the right-hand side vector, c E T the objective function, and I the indices of integer variables. Throughout this document, interested in repeated MILPs of fixed dimension P. = (A,, by, 0,,44 4, uy u))ee sampled according to an unknown distribution po: : + mmxa x 1.m x 1. R. R..
In order to solve MILPs efficiently, the B&B algorithm iteratively builds a binary tree (V, E) where each node corresponds to MILP, starting from the root node to E V representing the original problem Po. The incumbent solution J E L x = denotes the best feasible solution found at current iteration, associated value GUB = e a called the global upper bound on the optimal value. The overall state of the optimization process is thus captured by the triplet (V, D,E, Z), we

---

Fo
8.75
4L
122
$2
die - 62.5 < cla
minimme:: -13rg Aog
21 2,
2e 28
Pg S
subjoct 500 1 22,
8xy + 2xy
0.5 29
32
11,32 2
Open
Curren
Clooed
Fathomed
37.
infrasible
Figure 2: Solving MILP by B&B using variable selection policy л and node selection policy p. Each node U; represents a MILP derived from the original problem, each edge represents the bound adjustment applied to derive child nodes from their parent. Throughout the solving process, U1 is pruned by integrity, Uy is pruned by bound, and va by infeasibility.
note S the set of all such triplets Throughout the optimization process, B&B nodes are explored sequentially. We note C' the set of visited or closed nodes, and the set of unvisited or open nodes, such that V/ C U O. Originally, O {to} and C 0. At each iteration, the node selection policy p: S - O selects the next node to explore. Since p necessarily defines a total order on nodes o, E O can arrange indices such that 01 = p(s) denotes U, the node currently explored at step t.
Figure 2 iillustrates how B&B operates on an example. At each iteration, let LiP E R be the optimal solution to the linear relaxation of Pt. the problem associated with u. If P; admits solution, o is marked as visited and the branch is pruned by infeasibility. If aiir E IR. exists, and GUB < c -ip-- no integer solution in the subsequent branch can improve GUB, thus in is marked as closed and the branch is pruned by bound. If oi,P p is not dominated by I and x is feasible (all integer variables in Tt E R" have integer values), new incumbent solution ā -7 has been found. Hence GUB is updated and 2 is marked as visited while the branch is pruned by integrity. Else, 27.P admits fractional values for some integer variables. The branching heuristic т S + I selects variable ry with fractional value &. to partition the solution space. As a result, two child nodes (v_, 14), with associated MILPs P_ P. U {aa [ and P_ P. U {a,, [ }. are added to the current node
P Their linear relaxation is solved, before they are added the set of open nodes O and o, is marked as visited.
This process is repeated until O 0 and F is returned. The dynamics of the B&B algorithm between two branching decisions can be described by the function Kip : S x I S, such that s' = (p π (s)). By design. B&B does not terminate before finding optimal solution and proving its optimality. Consequently, optimizing the performance of B&B on a distribution of MILP instances is equivalent to minimizing the expected solving time of the algorithm. As Etheve [022 evidenced, the variable selection strategy æ is by far the most critical B&B heuristic terms of computational performance. In practice, the total number of nodes of the B&B tree is used as an alternative metric evaluate the performance of branching heuristics π, as it is a hardware-indeeendeer proxy for computational efficiency. Under these circumstances, given fixed node selection strategy p. the optimal branching strategy nt associated with a distribution po of MILP instances can be defined as:
arg min E P-po (r.)
with BB (T.n) the size of the B&B tree after solving P to optimality following strategies (I, p).
2.2 Reinforcement learning
We consider the setting of discrete-time, deterministic MDPs [Puterman 2014 defined by the tuple A, T, Po. R). At each time step f. the agent observes 8, E S the current state of the environment, before executing action a; A, and receiving reward r R(s,, The Markov transition function T : S x A + S models the dynamics of the environment. In particular, it satisfies the Markov property: conditionally to 8, and at, S1+1 is independent of past visited states and actions. Given a trajectory starting in state 80 sampled according to the initial distribution Po. the total gain is defined for all t > 0 as G, EPm.. "R(ss, ay),, with 7 E [0, 1]. The
'To account for early resolution steps where no incumbent solution has yet been found, we define a special value for ã, whose GUB = oc. For the sake of simplicity, we make this implicit the remainder of the paper. Lg denotes the value of 2s in zi... We use the symbol denote the refinement of the bound on in Pt.
3

---

objective of an RL agent is to maximize the expected gain of the trajectories yielded by its action
selection policy т S + A. This equivalent to finding the policy maximizing value functions V (sx) = ((g~)(()) [Gr] and Q* 0+) = R(xt; at) + <VV*(8++1)
(8++1). The optimal Q-value function Q" indicates the highest achievable cumulated gain in the MDP. satisfies the Bellman optimality
equation ((s, a) R(s, a) + y ma Q(s', a'), noting s' Tss, a) for (s. a) E S x A. The optimal policy is retrieved by acting greedily according to the learned Q-value function: x (s) = arg A (s)a).
2.3 Related work
Following the seminal work by Gasse et al. [2019], few contributions have proposed to build more complex neural network architectures based on transformers [Lin al. [022] and recurrence mechanisms (Seyfi et al., 2023] to improve the performance of IL branching agents, with moderate success. In parallel, theoretical and computational analysis [Bestuzheva et al. 2021 Sun et al. 2022] have shown that neural networks trained by imitation could not rival the tree size performance achieved by strong branching (SB), the branching expert used in Gasse et al. [2019). In fact, low tree sizes associated with SB turn out be primarily due the formulation improvements resulting from the massive number of LPs solved in SB, not to the intrinsic quality of the branching decisions themselves.
Since branching decisions are made sequentially, reinforcement learning appears as a natural candidate to learn good branching policies. [Etheve et al. 2020) and Scavuzzo et al. [0022] proposed the model of TreeMDP, in which state 8; = [Pr, Ti.,,; 2.,) consists in the MILP associated with node v; along with the solution of its linear relaxation and the incumbent solution at e, The actions available at s; are the set of fractional variables in P Given (s,, a;) the tree Markov transition function produces two child node states (5, s that can be visited in any order. Crucially, when the B&B tree is explored in seeth-hirst-eearch (DFS), TreeMDP trajectories can be divided in independent subtrees, allowing to learn policies minimizing the size of each subtree independently. This helps mitigate credit assignment issues that arise owing to the length of episode trajectories. Subsequently, PPrrsonsonn Subsssquentyyy|Paroooonn et al. [2022) found the DFS node selection policy to be highly detrimental to the computational performance of RL branching strategies. Assuming that RI. branching agents trained following advanced node selection strategies would perform better despite the lack of theoretical guarantee, they proposed to learn from retrospective trajectories, diving trajectories built from original TreeMDP episodes. In fact, Parsonson al. (2022) found retrospective trajectories alleviate the partial observability induced by the "disordered" exploration of the tree and outperform prior RL agents.
A large body of work has proposed to learn, either by imitation or reinforcement, better-performing B&B heuristics outside of variable selection [Nair et al., [2021] Paulus et al., [022). RL contributions
in primal search [Sonnerat et al.) 2022. Wu and Lisser 2023] node selection He et al. 2014 Etheve 202T] and cut selection [Tang et 20200 (Son et al. 22020] Wang et al.) 2023 have all relied on the TreeMDP framework to train their agents, simply adapting the action set to the task hand. Finally, machine learning applications in combinatorial optimization are not limited to B&B. For example, in the context of routing scheduling problems where exact resolution rapidly becomes prohibitive, agents are trained to learn direct search heuristics [Kool et al., 2019 Grinsztajn et al.) 2022 Chalumeau et al. 2023) yielding high-quality feasible solutions.
3 Branch and bound Markov decision process
By using the current B&B node as the observable state, prior attempts to learn optimal branching strategies have relied on the TreeMDP formalism to train RL agents. However, TreeMDPs are not MDPs, as they do not define a Markov process on the state random variable (for instance, a transition yields two states and is hence not a stochastic process on the state variables). As result, this forces Etheve et al. 2020) and Scavuzzo et al. [2022] to redefine Bellman updates and derive hoc convergence theorems for TD(0), value iteration, and policy gradient algorithms. In order to leverage broader theoretical results from the reinforcement learning literature, we propose a description of variable selection in B&B as a proper Markov decision process.

---

3.1 Definition
The problem of finding an optimal branching strategy according to Eq. can be described as a regular deterministic Markov decision process. To this end, we introduce Branch and bound Markov decision processes (BBMDP), taking 7 = since episodes horizons are bounded by the (finite)
largest possible number of nodes:
State-action space. S is the set of all B&B trees 8 = &1, Note that this includes intermediate B&B trees, whose incumbent solutions H, are yet to be proven optimal. A is the set of all integer variables indices I.
Transition function. The Markov transition function is defined as T Kip with Kip the branching operation described in Section 2.1 Note that if the variable associated with a is not fractional in LLP. then 8t-1 = T(s Q2) = St as relaxing a variable that is not fractional has no impact on the LP relaxation. Importantly, all states for which O = 0 are terminal states.
Starting states. Initial states are single node trees, where the root node is associated to a MILP Po drawn according to the distribution Po defined in Section 7 (hence the use of po for both the initial problem Po and the MDP's initial state so).
Reward model. We define R(s, a) = 2 for all transitions until episode termination. Since each transition adds two B&B nodes, the overall value of a trajectory is the opposite of the number of nodes added to the B&B tree from the root node, which aligns with the definition of Eq. ①
Unlike in TreMMDP, the current state is defined as the state of the entire B&B tree, rather than merely the current B&B node. The transition function returns a B&B tree whose open nodes are sorted according the node selection policy p. thus reflecting the true dynamics of the B&B algorithm, instead of couple of pseudo-states associated with the child nodes the last node expansion. Note that the definition above sets BBMDPs among the specific class of MDPs called stochastic shortest path problems [Puterman] 2014).
3.2 Misconceptions when learning to explore B&B trees
Like in TreeMDP, episode trajectories can be decomposed in independent subtree trajectories, to facilitate RL agents training. Consider a deterministic branching policy ग, and let us we rewrite V and Q' to exhibit the tree structure. Given an open node o; E Or, we note T(o:)) the subtree rooted in 0g, and define (st, o;) the function that returns the opposite of the size of the subtree rooted in
og, when branching according to policy ι starting from state st until episode termination. Then V can be expressed as:
V*( = Σ (st. O.E0.
(2)
In plain words, the total number of nodes that will be added to the B&B tree past 8, is the sum of the sizes of all the subtrees T(o,) rooted in the open nodes of st. Because the full B&B tree is a complex object to manipulate, it is tempting to discard the tree structure in 8 and define V-value functions merely as functions of (o,, ), rather than functions of (&t, oz). where To, E R the incumbent solution when oN is processed by the B&B algorithm, at time step The rationale for such value functions that the size of the subtree rooted in o; E Or, for given incumbent solution To.. should be the same, regardless of the parents of o,, its position in the tree, or the branching decisions taken in subtrees I (o,) for j * i. turns out, this last statement does not always hold, quite counter-intuitively Let write тi the time steps at which the nodes 0, E O2 are selected by the node selection strategy م Now, consider for instance a node selection procedure p that performs breadth-firs search through the tree. The number of nodes in T(o;) will depend strongly on whether an improved incumbent solution To, was found in the subtrees explored between s and Sr,, and, in turn, on the branching decisions taken in these subtrees. This example highlights the major importance of the node selection strategy when one wishes to define subtree sizes based solely (o,, Fo.).
Consider now two open nodes o and of in Or- Conversely to the previous example, if one can guarantee that the subtree rooted in 0j will be solved to optimality before o; is considered for expansion in the B&B process, then the number of nodes in T(o:) will not be affected by the
Following our indexation of or E Oc. have = <... Ti < TI0d
5

---

(a) 1-step BBMDP Bellman equation:
(b) 1-step TrecMDP Bellman equation:
1n (01, (oz) = + V (0i, Fof + V (02, Fogg)
(T((.) -2 V (*(s) (*,))
(c) k--stp BBMDP Bellman equation:
k-step TreMMDP Bellman equation:
V/ (01, = 2h
k++ 1 (o (5))
V (50) = 2 2 2 Σ
Figure 3: When minimizing 1-step temporal difference, TreeMDP and BBMDP yield equivalent 3a 3b However, over k-step trajectories, the two methods diverge as shown in 3c 3d
results, see
branching decisions taken at any node under oj. In fact, oj is solved optimality, To, will either not change if no feasible solution in T(o;) improves GUB, or either be the best feasible solution of the MILP associated with oj, which does not depend on the series of actions taken in T(o,). In other words, to make sure that the size of (o:) does only depend on the branching decisions taken in T.,,), all nodes 03 E O, must have been either fully explored or strictly unexplored at т, Applying this argument recursively induces that the only node selection strategy which enables predicting a subtree size only based on (o,, To; is a depth-first search (DFS) exploration of the B&B tree. Therefore, we consider p = DFS and write V (o,, Fo,) the opposite of the size of T(o;) in this context. We can now derive a refined Bellman update to train branching agents in BBMDP
Proposition 3.1. In
the Bellman equation V*)(s (s) R(s, (s)) (s') yields:
(" = - V (o' Roo.) + V" (0' Rot))
(3)
with 01 = p(s)), ((T(ss and ol2 is the sibling of of in the B&B tree.
Proof. Eq. (3) follows directly from injecting Eq. (2) in the Bellman equation, and observing that most terms in the sums simplify as V (0;, To,) =V*(o' (0'_1::: for 2 2.
Keeping the same notation convention for 01, of and ozz, we define (0 (o,, = -2 V (" (T Toi). Analogous to V the Q function returns the opposite of the size of the subtree rooted in o E O; when branching on action T(o;) is fathomed. Note that if vTT and Q are not strictly value functions, they naturally emerge when applying Bellman equations to BBMDP value functions under = DFS. We stress that, in depth-first search BBMDPs, it is not necessary to learn Q' derive x² since acting according to a policy minimizing the size of the subtree rooted in the current B&B node is equivalent to acting according a global optimal policy:
at o, and following policy π until
(s) arg max (" a) arg max (01 To,, aeAA
a
3.3 Approximate dynamic programming
The previous properties enable learning T- by training neural network to approximate Q* using traditional temporal difference (TD) algorithms. Notably, Q* is easier learn than Q" as relies solely on quantities observable at time t, whereas the previous decomposition of Q* depends on all To; for o, E Or, which are known at time t. Moreover, Q" trains on much shorter trajectories than Q", which helps mitigate credit assignement issues F
'On average. the length of subtree trajectories is logarithmically shorter than the length of BBMDP episodes.

---

Consider a transition (s, r, s'). Following Eq. 3 the Bellman optimality equation yields sequence Qn functions via dynamic programming updates the form:
Q0t1 Zor: a) 22 max (n : max Qn Tog,
(5)
One can also consider s-step Bellman operator (k 1), generalizing Eq. (5) Let æ be policy, and g(k) the state reached after first application of from and k subsequent applications of Provided the subtree rooted in has not been fathomed within these & time steps, s(k) has k +
new open nodes which we label 0,
(k). Then, the Bellman update becomes:
R++
Qn11 a) = 2k + Σ max Qn(o agg E'EA
(6)
This Bellman update can be approximated using neural network qo. whose weights are trained to
minimize the k-step temporal difference loss L()) [o) To Q (o ..).)) {)) where
Qn+1 is bootstrapped by the previous qo. Following the work Farebroohh al. [2024] on training
value functions via classification, we also introduce HL-Gauss cross- entropy loss adapted to the
B&B setting (()) ge (01. ão, a) log Phist (Qn+1 (01. a)) where Phvie the function that
encodes values in categorical histogram distributions, see Appendix B for complete description and theoretical motivation.
3.4 BBMDP Tre
As it evacuates the core MDP notions of temporality and sequentiality, TreeMDP fails to describe variable selection in B&B accurately in the general case. This is illustrated in Figure 3 and further detailed in Appendix A although the TreeMDP model is a valid approximation of BBMDP when training an RL agent to minimize temporal difference on one-step trajectories, it produces inconsis- tent learning schemes when evaluating temporal difference across multi-steps trajectories. In fact, repeatedly applying the tree Bellman operator from Etheve 202T yields B&B trees that cannot, in general, be produced by DFS, as shown in Figure (d).
Hence, BBMDP leverages the results first established by Etheve al.) [020) and Scavuzzo al. 2022] in DFS, minimizing the whole B&B tree size is achieved when any subtree is of minimal size (Eq.
all while preserving MDP properties. Crucially, BBMDP allows harness RL algorithms that are not compatible with the TreeMDP framework, such as k-step return temporal difference, TD(A), any RI. algorithms using MCTS policy improvement operator [Grill et al.. 2020). as illustrated in Appendix A In the same fashion, BBMDP can be applied to augment the pool of RL algorithms available for learning improved simply by adapting the action set and the reward model to the task at hand. Complete exploration and comparison of such algorithms is beyond the scope of this paper and left for future work, as our primary objective here is to study the conditions under which B&B search can be cast as an MDP, and provide the community with a solid basis for principled algorithms.
selection and primal search heuristics,
Experiments
We now compare branching agent against prior IL and RL approaches. For our experiments, use the open-source solver SCIP 8.0.3 [Bestuzheva et al. 2021] as backend MILP solver, along with the Ecole library (Prouvost et al. 2020 both for instance generation and environment simulation. To foster reproducibility, our implementation and pretrained models are made publicly available at httpggggthtioooobooaaaaaaaaaaeae
4.1 Experimental setup
Benchmarks. We consider the usual standard MILP benchmarks for learning branching strategies: set covering, combinatorial auctions, maximum independent set and multiple knapsack problems. We train and test on instances same dimensions as Scavuzzoo et al. [2022] and Parsonson al. [2022), see Appendix F As to SCIP configuration, as in previous work, we set the time limit to one hour, disable restart, and deactivate cut generation beyond root node. All the other parameters are left at their default value.
7

---

Table I: Performance comparison of branching agents four standard MILP benchmarks. For each method, we report total number of B&B nodes, presolve time and total solving time outside of presolve. Lower is better, red indicates best agent overall, blue indicates best among RL agents. Presolve is common to all methods. Following prior works, we report geometrical mean over 100 test instances unseen during training and over 100 higher-dimensional transfer instances. Norm. Score denotes the aggregate average performance obtained by each agent across the four MILP benchmarks, normalized by the score DQN-BRI DDMDBBDDP.
Test instances
Set Covering Time
Comb. Node
Auction Time
Max. Ind. Set
Mult. Node
Knapsack Time
Norm. Score
Method
Node
Node
Time
Node
Time
Presolve
4.74
0.90
1.78
0.20
Random
3289
5.94
1111
2.16
386.8
2.01
733.5
0.55
995
374
SB
35.8
12.93
28.2
6.21
24.9
45.87
161.7
0.69
36
2358
SCIP
62.0
2.27
20.2
1.77
19.5
2.44
289.5
0.53
51
253
IL 133.8
0.90
83.6
0.65
40.1
0.36
272.0
0.69
82
95
IL-DFS
136.4
0.74
95.5
0.56
69.4
0.44
472.8
1.07
114
129
PG-MMP
649.4
2.32
168.0
0.94
153.6
0.92
436.9
1.57
233
206
DQN-MMD
175.8
0.83
203.3
1.11
168.0
1.00
266.4
0.73
151
136
DON-Retro
183.0
1.14
103.2
0.78
223.0
1.81
250.3
0.67
137
160
DQN-BBMDP
152.3
0.77
97.9
0.62
103.2
0.69
236.6
0.66
100
100
Transfer instances
Set Covering
Comb. Node
Auction Time
Max. Ind. Set
Mult. Knapsack
Norm. Score
Method
Node
Time
Node
Time
Node
Time
Node
Time
Presolve
12.3
2.67
5.16
0.46
Random
271632
842
317235
749
215879
2102
93452
70.6
5555
2737
SB
672.1
398
389.6
255
169.9
2172
1709
12.5
9
1425
SCIP
3309
48.4
1376
14.77
3368
90.0
30620
22.1
62
90
2610
23.1
1309
1882.0
38.6
9747
43.5
39
54
IL-DFS
3103
22.5
1802
10.2
3501
51.9
43224
131
75
PG-MMDP
44649
221
6001
30.7
3133
39.5
35614
123
298
223
DQN-MMDP
8632
71.3
20553
116
45634
477
22631
65.1
439
445
DQN-Rent Retro
6100
59.4
2908
18.4
119478
1863
27077
79.5
494
662
DON-BBMDP
5651
46.4
2273
11.8
7168
81.3
37098
109
100
100
Baselines. We compare our DQN-BBMDP agent against DON- (DQN-IMDP) (Etheve al. 2020]. COANFOORCETTreMMDD (PG-LMDP) [Scavuzzo al.) 2022 and the current state-of-the the
art DQN-Retro Parsonson et al. 2022] agents. We also compare against the reference IL expert from Gasse et al. [2019] as well LL-DFS, which is the same expert, only evaluated following a depthh-frst search node selection policy. More details on these baselines can be found in Appendix [ Finally, report the performance of reliability pseudo cost branching (SCIP), the default branching heuristic used SCIP, strong branching (SB) [Applegate et al., 1995), the greedy expert from which the IL agent learns from, and random branching (Random), which randomly selects a fractional variable.
Network architecture. Following prior work, we use the bipartite graph representation introduced by Gasse et al. [2019) augmented by the features proposed in Parsonson et al.) (2022) to represent B&B nodes. Additionally, we use the graph convolutional architecture of Gasse et al. 2019 to
parameterize our Q-value network; see Appendix E for a more detailed description.
Training & evaluation. Models are trained on instances of each benchmark separately, and evaluated on test instances and transfer instances. Validation curves can be found in Appendix H For evaluation, we report the node and time performance over 100 test instances unseen during training, well as on 100 transfer instances of higher dimensions (see Table Appendix FF. At evaluation, performance scores are averaged over seeds. Importantly, when comparing a machine learning (IL or RL) branching strategy with a standard SCIP heuristic, time performance is the only relevant criterion. In fact, when implementing one its own branching rules, SCIP triggers series of techniques strengthening the current MILP formulation. If these techniques effectively reduce the number of
8

---

Table 2:
Ablation impact of BBMDP, HL-Gauss loss and DFS. We remove component the time, and evaluate corresponding versions on 100 set covering test instances after training for 200k gradient steps described in section 4.1
stsp return
DQN DQN-BBMDP
w.o. DFS
W.O. HL--Gauss
W.o. BBMDP
k:
158.9
156.2 2%)
175.8(+ 172.3 (+8%)
158.9(+-0%)
175.8( 10%) 178.9 +13%)
152.3(-4%)
150.1 (-5%)
162.1 (+2%)
nodes to visit, they incur computational overhead which ultimately increases SCIP overall solving time. This renders node comparisons between ML and non-ML branching strategies negligible relative to solving time evaluations, observed by Gamrath and Schubert 2018). Scavuzzo et al. [022].
4.2 Results
Computational results obtained the four benchmarks are presented in Table [ On test instances, DQN-BBMDP consistently obtains best performance among RL agents. When compared against prior state-of-the-art DQN-Retro, DQN-BBMDP achieves an aggregate average 27% reduction of total number of node and 38% reduction of solving time outside presolve across the four Ecole benchmarks, reported in Figure ! performance comparable to DQN-iMDP. Remarkably, all RL agents outperform the SCIP solver on of benchmarks in terms of solving time.
Contrary to Parsonsoon al. [2022], we find DQN-Retro to yield
On transfer instances, DON-BBMDP also dominates among RL agents, although it is outperformed by PG-tMDP maximum independent set instances and by DQN-Retro multiple knapsack instances. The aggregate performance gap between DQN-BBMDP and other RL baselines is notably wider on transfer instances, which aligns with the advantages of using principled MDP formulation over Tr. In fact, DQN-BBMDP is the first RL agent to demonstrate robust generalization capabilities higher dimensional instances, outperforming SCIP
of benchmarks.
Additional performance metrics are provided in Appendix ! A notable metric is the number of wins, i.e. the number of test instances that one algorithm solves faster than any other baseline. DQN-BBMDP outperforms even the IL. approaches both in average solving time and total number of wins, the set covering, combinatorial auction and multiple knapsack test instances.
4.3 Ablation study
We perform an ablation study on set covering test instances to separate the performance gain associated with BBMDP and the HL-Gauss classification loss. Since BBMDP and TreeMDP are strictly equivalent when minimizing one-step temporal difference, we evaluate the performance gap between one-step and k-step TD learning for both DQN-BBMD and DON-TreeMDD.
As shown in Table 2 we find that the bulk of the performance gain is brought by the use of a cross- entropy loss. Nonetheless, observe that the use of multi-step TD loss improves the performance of DQN-BBMDP, but degrades the performance of DQN-TreeMDP. This supports our initial claim that, the general case, despite improving the empirical properties of RL algorithms, TreeMDP introduces approximations which hinder the asymptotic performance achievable by RL agents. Following Parsonson et al. [2022), we also evaluate the cost of opting for depth-first search instead of best estimate search, SCIP's s default node selection policy, when learning branching strategies. Contrary to their work, we find DFS not to be restrictive in practice terms of performance. We further investigate theses discrepancies in Appendix D
5
Conclusion and perspectives
Guiding combinatorial optimization algorithms with reinforcement learning has proven challenging. including beyond mixed-integer linear programming [Berto et al. 2023). Not only are RL agents consistently outperformed by human-expert CO heuristics or II. agents trained to mimic these experts, but their application has also been limited so far to fairly easy problem instances. This begs for thorough study of these problems' properties, for well-posed formulations and principled

---

methods. In this work, we showed the theoretical and practical limits of the concept of TreeMDP for learning optimal branching strategies in MILP, highlighting which context TreeMDDs were valid formulation. Introducing BBMDP, we proposed rigorous description of variable selection in B&B, unlocking the use of vanilla dynamic programming methods. turn, the resulting DON-BBMDP method outperformed prior RI-inspired agents on the Ecole benchmark.
Nonetheless, there remains significant room for improvement for RL approaches on both test and transfer instances, suggesting that the generalization capacity of RL agents still lags behind that of IL. We believe this be mainly due to out of distribution effects, since transfer instances are intrinsically more complex than training instances, and Q-networks are lead to evaluate B&B nodes with subtree sizes far exceeding those encountered during training. In contrast, IL networks learn predict the strong branching action via behavioral cloning, making them robust to such out-of-distribttion scaling effects. Yet, we believe that building on a principled MDP formulation of variable selection B&B is a stepping stone to achieve substantial acceleration of solving time for nigher-dimensional MILPs in the future, also opening avenues to tackle distribution shift and domain adaptation.
References
Tobias Achterberg and Roland Wunderling. Mixed integer programming: Analyzing 12 years of progress. In Facets of combinatorial optimization: Festschrift for martin grötschel, pages 449-481. Springer, 2013.
David Applegate, Robert Bixby, Vašek Chvátal, and William Cook. Finding cuts in the TSP (A preliminary report), volume 95. Citeseer 1995.
Egon Balas and Andrew Ho. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: computational study. Combinatorial Optimization, pages 37-60, 1980.
Francisco Barahona. On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15(10)33241, 1982.
Marc Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforcement learning. In International conference on machine learning, pages 449-458 PMLR, 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial op-
timization: A methodological tour d'horizon. European Journal of Operational Research, doi: 10. 2020..00.....0......... 006666 URL httpp::/www.sciieceediiee www.:eecceeeeett.ccooeeeeeeeeeee htt.ai/aeeaaatteeeee.////////.o.
290(2):405-421, April 2021. ISSN 0377-2217.
htttps://ww...
David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker. Decision diagrams for optimization, volume 1. Springer, 2016.
Federico Berto, Chuanbo Hua, Junyoung Park, Minsu Kim, Hyeonah Kim, Jiwoo Son, Haeyeon Kim, Joungho Kim, and Jinkyoo Park. RI4CO:: an Extensive Reinforcement Learning for Com- binatorial Optimization Benchmark, June 2023. http:///: org/abs//////oo 2306 17100 arXiv:2306.I 100000 [es].
Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graezyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Thorsten Koch, Marco Lübbecke, Stephen J. Maher, Frederic Matter, Erik Mühmer, Ben- jamin Müller, Marc E. Pfetsch, Daniel Rehfeldt, Steffan Schlein, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Boro Sofranac, Mark Turner, Stefan Vigerske, Fabian Wegscheider, Philipp Wellner, Dieter Weninger, and Jakob Witzig. The SCIP Optimization Suite 8.0. Technical Report, Optimization Online, December 2021. URL http: http:://ww.ggtimmiiii. wwwp:wwwpiiizzaiiioom www.oon.n.nnnne.....eeee org/DB_ HTML/2021/12/8772 html
ine.
Robert E. Bixby. A brief history of linear and mixed-integer programming computation. Documenta Mathematica, 10721107- 2012.
Felix Chalumeau, Shikha Surana, Clément Bonnet, Nathan Grinsztajn, Arnu Pretorius, Alexandre Laterre, and Tom Barrett. Combinatorial optimization with policy adaptation using latent space search. Advances in Neural Information Processing Systems, 36:7947-7959, 2023.
10

---

Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference on machine learning, pages 1096-1105. PMLR, 2018.
Mare Etheve. Solving repeated optimization problems by Machine Learnnng phdthesis, HESAM Université, December 2021. URL httpss::/tteeees..bbttt hall hct...seeeeeeetaa0007777777117
Mare Etheve, Zacharie Ales, Côme Bissuel, Olivier Juan, and Safia Kedad-Sidhoum. Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm. In Emmanuel Hebrard and Nysret Musliu, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Lecture Notes in Computer Science, pages 176-18 776,185, Cham, 2020. Springer International Publishing. ISBN 378-3-030-58942-44
doi: 10. 10.1007/978-3-00 3-030-58942--000
Jesse Farebrother, Jordi Orbay. Quan Vuong, Adrien Ali Taīga, Yevgen Chebotar, Ted Xiao, Alex Irpan, Sergey Levine, Pablo Samuel Castro, Aleksandra Faust, Aviral Kumar, and Rishabh Agarwal. Stop Regressing: Training Value Functions via Classification for Scalable Deep RL, March 2024. URL http: wwwpxiv.orrg/b////000000 03950 arXiv:2403.0333 [cs, stat].
Alex S Fukunaga. A branch-and-bound algorithm for hard multiple knapsack problems. Annals of Operations Research, 184(1):97-119, 2011.
Gerald Gamrath and Christoph Schubert. Measuring the impact of branching rules for mixed- integer programming. In Operations Research Proceedings 2017: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Freie Universiät Berlin, Germany, September 6-8, 2017, pages 165-170. Springer, 2018.
Maxime Gasse, Didier Chetelat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact Combinato- rial Optimization with Graph Convolutional Neural Networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL httppp:::ppocceeeeiiiiist html
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, and Jeff Linderoth. MIPLIB 2017: data- driven compilation of the 6th mixed-integer programming library. Mathematical Programming Computation, 13(3):443-490, 2021. Publisher: Springer.
Jean-Bastien Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, loannis Antonoglou, and Rémi Munos. Monte- Tree Search Regularized Policy Optimization, July 2020. URL http://arxiv.orgg wwwppb///g/....11...p. 12509 arXiv:2007.122 12509 [cs, stat].
Nathan Grinsztajn, Daniel Blanco, and Thomas D. Barrett. Population- Based Reinforcement Learning for Combinatorial Optimization, October 2022. /ttp:///://aaxixi..o aasggg//////aa/ /bab////0100 03475, arXiv:2210.03475 [cs].
Dan Gusfield. Integer linear programming in computational and systems biology: an entry-level text and course. Cambridge University Press, 2019.
He He, Hal Daume III. and Jason M Eisner. Learning to Search in Branch and Bound Algorithms. In Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014. URL https::/papers. nips ctcpapp.cc/ppppap http:/aapp////////e/ 155FB44811B000776644000000101110
Awstract. html
Mattco Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski. Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining Improvements in Deep Reinforcement Learning, October 2017. URL hlllatpp//arrav..or//abb/////// 02298 arXiv:1710.02298 [es].
Frederick S Hillier and Gerald Lieberman. Introduction to operations research. McGraw-Hill, 2015.
Ehsan Imani and Martha White. Improving Regression Performance with Distributional Losses In Proceedings of the 35th International Conference on Machine Learning, pages 2157-2166. PMLR, July 2018 URL 2640-3498.
.ww.ggg.m....................... mlr, wwwpss/e0/eeeeeeeeepeepep / imani 18a html ISSN:

---

Wouter Kool, Herke van Hoof, and Max Welling. Attention. Learn to Solve Routing Problems!, February 2019. http:ppp//aax.v.oorr//////0000
wrg/abs/180/ 08475 arXiv:1803.08475 [es, stat].
AH Land and AG Doig. An automatic method of solving discrete programming problems. Econo- metrica, 28(3):497-553)) 1960.
Kevin Leyton- Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combina- torial auction al algorithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pages 66-76, 2000.
Jiacheng Lin, Jialin Zhu, Huangang Wang, and Tao Zhang. Learning branch with Tree-aware Branching Transformers. Knowledge-Based Systems, 252:109455, September 2022. ISSN 0950-7051. doi: 10110166.kkoosss2222.044444 URL https: / /www. wcwenceireeeerrc.... com/ occ/oo////rr1222//////6666621220
Renata Mansini, Wodzimierz Ogryczak, M Grazia Speranza, and EURO: Operational Research Societies. Linear and mixed integer programming for portfolio optimization, volume 21. Springer, 2015.
The Association of European
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving Mixed Integer Programs Using Neural Networks, July 2021.
URL http:htt:::/rree //tp:vv/axvvvv///o
13349 arXiv:2012.13349 [cs, math].
Christopher W. F. Parsonson, Alexandre Laterre, and Thomas D. Barrett. Reinforcement Learning for Biranch-and-Bound Optimisation using Retrospective Trajectories, December 2022. URL
http://araxvv.org/bbb///200 14345 arXiv:2205.144: 14345 [cs].
Max B. Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to
Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning. Proceedings of the 39th International Conference Machine Learning, pages 17584-1700 17600. PMLR, June 2022. URL
httpps://proceedings mlr. presss/162/paauluee
html
ISSN: 2640-3498.
Eduardo Pignatelli, Johan Ferret, Matthieu Geist, Thomas Mesnard, Hado van Hasselt, and Laura Toni. A survey of temporal credit assignment in deep reinforcement learning. arXiv preprint arXiv:2312.00102. 2023.
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, November 2020. http:/ttp:/arrxxv.ooo a011:///...///a///11..... 06069 arXiv:2011 1.6069 [es, math].
Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Lara Scavuzzo, Feng Yang Chen, Didier Chételat, Maxime Gasse, Andrea Lodi, Neil Yorke-Smith, and Karen Aardal. Learning to branch with Tree MDPs, October 2022. URL http://arxix: org/abs/2205 11107 arXiv:2205.11 107 [cs, math].
Lara Scavuzzo, Karen Aardal, Andrea Lodi, and Neil Yorke-Smith. Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming, February 2024. /Rtp::t:://arxt //axxiv
orrgabsa 2aabs/402.. 2402.055011 arXiv:2402.05501 [cs, math].
Tom Schaul. Prioritized experience replay, arXiv preprint arXiv:1511.05952. 2015.
Mchdi Scyfi, Amin Bamitalebi Zirui Zhou, and Yong Zhang. Exact Combinato- rial Optimization with Temporo-Attention Graph Neural Networks, November 2023. URL
htttp://arxiv.org/// 2at../..1...11113333 arXiv:231 NVv22311.13845 1.13843 [cs].
David Silver, Thomas Hubert, Julian Schrittwisser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap. Karen Simonyan, and Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science, 362(6419): 140-1144, December 2018. ISSN 0036- 8075, 1095-9203. doi: 10. 1116/science..ar64444 URL, /ttpt:tt////ttt h//::://www www.:sscieccccceeeeeeeee 1126/ /022//cciece..o aar6404 a
12

---

Jialin Song, Ravi Lanka, Yisong Yue, and Bistra Dilkina. A General Large Neighborhood Search Framework for Solving Integer Linear Programs, December 2020. URL http::/arrxii org/
0bs/2004.00427 arXiv:2004.00422 [cs, math, stat].
Nicolas Sonnerat, Pengming Wang. Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning
Large Neighborhood Search Algorithm for Mixed Integer Programs, May 2022. URL http
//aaxiv.org//////. ab/gg/7 10201 arXiv:2107.1020 [cs, math].
Haoran Sun, Wenbo Chen, Hui Li, and Le Song. Improving Learning Branch via Reinforcement (oto:/ooddddddd------
Learning. July 2022. URL https: //tperevi///peeviiee
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement Learning for Integer Programming: Learning to Cut. In Proceedings of the 37th International Conference on Machine Learning,
pages 9367-9376. PMLR, November 2020. URL htlp:tts/////ccedinnngg mww.g.ss.m......... www.mp....e/.11///////
tang20a. html ISSN: 2640-3498.
Vincent Tjeng, Kai Y Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Zhihai Wang, Xijun Li, Jie Wang. Yufei Kuang, Mingxuan Yuan. Jia Zeng, Yongdong Zhang, and Feng Wu. Learning Cut Selection for Mixed-Integer Linear Programming via Hierarchical Sequence Model. February 2023. URL http:ttt:://oeeeeeeieee www.:eeeoooommmddoooooooaooa00
Dawen Wu and Abdel Lisser. A deep learning approach for solving linear programming problems. Neurocomputting, 520:15 24, February 2023. ISSN 09252312, doi: hww.:000//..nucmmm222222.... 1.053. URL
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims made in the abstract and introduction are supported by the theoreti- cal and experimental results presented in sections 3 and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Moreover, section 4.3 as Justification: The main limitations are adressed in section D
[nd 5
well as appendix alsso discuss the limitations associated with the use of DFS in BBMDP.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
13

---

The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex: system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Proposition 3.1 clearly states the conditions for its validity, and its proof is provided.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: Comprehensive experimental details and references are provided in section and appendices G to allow for straightforward experiment reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data provided or not.
14

---

If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g.. with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: In order to enhance reproducibility, we share our implementations of the different RI baselines with the community, as well as pretrained network weights.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips ptaips.cc/public/guiico http://guuidee/oeeSubbiiin itw.oeeeubmmssioooollllllee
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
15

---

Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: All experimental details are provided in section while comprchensive list of hyperparameters is provided in appendix G
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Standard deviation for our experimental results are provided in appendix |
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma eтror bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All hardware ressource information are provided in appendix H
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
16

---

The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We have conducted research in confirmity with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e-g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML..
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All authors of assets duly cited in this work.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsspppppssttteeee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods this research? Note that if the L.M used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
19

---

A BBMDP vs TreeMDP
Side-by-side comparison
TreMMDP offers intuitive and computationaly efficient framework for training RL agents to learn enhanced variable selection strategies in branch and bound. However, by discarding core MDP concepts such as temporality and sequentiality, it fails to accommodate the diversity of RL algorithms. For example, defining the k-step return temporal difference target in TreeMDP is challenging. Since branching on action a, state 8; produces two child next states 8 and ST. applying recursively
Σラ= 2 + Eド V (s(). The corresponding TreeMDP trajectory depicted in Figure 3 (d) for A 3. More generally, is important to note that such trajectories cannot be obtained when solving a MILP using B&B with depth-first search node selection policy, since the subtree rooted in 8; must be fully fathomed before the node s can be considered for expansion. Therefore, the TreeMDP k-step return TD target defined above stems from approximations in the B&B dynamics, which undermines the best performance achievable by k-step tMDP-DQN, demonstrated in the ablation study in Section 4.3 Table further highlights the key differences between BBMDP and Tre.MDP.
the tree Bellman operator from Etheve [2021] to V yields (s;
Table 3: Side by side comparison of BBMDP and TreMMDP frameworks, complementing Figure
BBMDP
TrecMDP
MDP
Yes
State 8
= (Ve, Fc)
8, = ir.,,
Action
de E I
0, E I
Reward r
-2
-1
Next state s
8141 (V411, Ec41,
8T
s-st next state (8)
844k = (Mas,, Ec4k, T144)
sl.......
B(V*) V
(o(o) V (4)) (d2,)))
= - (=(s))= Ej= 2' + (*)
(x())t
(V(²)= V
( -2k Σnh (o( (.))
Learning to branch with MCTS
MCTS-based RL algorithms have achieved remarkable performance in combinatorial settings, partic- ularly in board games Silver al. 22018. Interstingly, by providing rigorous MDP formulation for variable selection in B&B, BBMDP enables the adapation of MCTS-based learning algorithms to the B&B framework, overcoming the incompatibilities that persisted within TreeMDP. In fact, when searching for the next node to expand, MCTS traverses the tree following a UCT exploration criterion:
N(S.A ( 1+ c1 log( EBE M(s,b),
a arg max
AEA ((s as)
C2
where (ss, a) corresponds to the number of visits of the node (s, a), and C1, C2 are search hyper- parameters. This formulation balances exploration and exploitation, guiding the search toward promising states while ensuring sufficient exploration of the tree. However in TreeMDP, such an exploration criteria leads to inconsistencies, as the exploration between node 8; and s is balanced based on their estimated value. Since both s; and s originate from the same branching decision as, differentiating between them for expansion is irrelevant. In B&B, branching on a; implies that s and 8, are both necessarily added to the B&B tree. Consequently, in TreeMDP, MCTS could guide the search towards a suboptimal action a; based on the assumption that produces a state s, of small subtree size, while failing to account for the potentially enormous subtree size of s,
20

---

This fundamental inconsistency hinders the effective application of MCTS within the TrecMDP framework.
B HL.-Gauss Loss
As they investigated the uneven success met by complex neural network architectures such as Transformers in supervised versus reinforcement learning. Farebrother learoin, et al. [022] found that training agents using a cross-entropy classification objective significantly improved the performance and scalability of value-based RI methods. However, replacing mean squared error regression with cross- entropy classification requires methods to transform scalars into distributions and distributions into scalars. Farebrother et al. [2024] found the Histogram Gaussian loss (HL-Gauss) [Imani and White 2018]. which exploits the ordinal structure of the regression task by distributing probability mass multiple neighboring histogram bins, to be reliable solution across multiple RL benchmarks. Concretely, in Gauss, the support of the value function 2, C R is divided in my bins of equal width forming a partition of Ze. Bins are centered at
Z, for 1 S m, use (Smaz - / m/m, to denote their width. Given scalar z E 2,, we define the random variable Y= ~N(n 2, o² and note respectively dy, and Øy, its associate probability density and cumulative distribution function. can then be encoded into a histogram distribution on 2, using the function Phist IR + [0, 1m Explicitly, Phist computes the aggregated mass of øy, on each bin:
si+ ( J
(hiie(2) (pi(z))ssism) with pi(z)
(y) (Si ") Dy (G: -
Conversely, histogram distributions (p:)ısism, such the ones outputted by agents' value networks can be converted to scalar simply by computing the expectation: 2 > Pi Çt.
BBMDP is challenging setting to adapt HL-Gauss, the support for value functions spans over several order of magnitude. In practice, we observe that for train instances of the Ecole benchmark, Z, 1-0 -2]. Since value functions predict the number of node of binary trees built with B&B, it seems natural to choose bins centered at Ç = -2' to partition Z,.. In order to preserve bins of equal size, consider distributions on the support (b(22,) with (=2) (-g)(=2) for = E 2,, such that (2,,) is efficiently partitioned by bins centered at G = for S S m,- Thus, in BBMDP histograms distributions and can be converted back to Z, through 2 = >i Pi (Gs) with a) (2) = -2..
given by Phist (2) (p; o (z)) for E 2..
mm
C Baselines
Imitation learning We trained and tested II agents using the official Ecole re-implementation of Gasse et [2019] shared at /t/ttps://gitthbb http:///wwaaaee/ee///rrrraaaeeee
DQN-TreeMDP Since there is no publicly available implementation of Etheve et al. [2020), we re-implemented DQN-TreeMDP and trained it on the four Ecole benchmarks, using when applicable the same network architectures and training parameters as DQN-BBMDP and DQN-Retro. We share implementation and trained network weights to the community.
PG-MMDP We used the official implementation of Scavuzzo et al. 2022 to evaluate PG-TreeMDP. For each benchmark, we used the (MDP+DFS network weights shared wttph:tt///// ttttpa://githin tiggghhu...... com/ lascavana/r12branchh
DON-Retro As Parsonson et al. 2002 only trained on set covering instances, we took inspira- tion from the official implementation shared at httpps://g: htt///ttttuuu... thub. wttpa..co//wwwwareeeeeeeeoeeeeee woom///cfppassosoo/retrerr branching to train and evaluate DON-Retro agents on the four Ecole benchmarks. Importantly, we trained and tested DQN-RE Ret-Retro following SCIP's default node selection strategy, see Appendix for more details. We share our re-implementation and trained network weights with the community.
21

---

Importantly, on the multiple knapsack benchmark, given the high computational cost associated with opting for depth-first search node selection policy, all baselines excepted IL-DFS are evaluated following SCIP default node selection policy.
D BBMDP vs Retro branching
In their work. Parsonson et al. 2022 proposed to train RL agents on retrospective trajectories built
from TreeMDP episodes, in order to leverage the state-of-the art node selection policies implemented in MILP solvers. When reproducing their work, we found several discrepancies with the results they stated. First, the performance gap between DQN-Retro and DON-TreeMDP [Etheve et al.) 2020] turned out to be much narrower than expected. On test set covering instances, the only benchmark on which the agents are compared in Parsonson et 2022]. we even found DDN to perform better. Second, Parsonson et al. [2022] found that adopting a fest-first-search (BeFS) node selection strategy evaluation time greatly improved the performance of DQN-TreeMDP on test set covering instances, indicating that abandoning DFS during training could be beneficial. However, in our experiments, we observed 20% performance drop when replacing DFS by BeFS at evaluation time. After thorough examination of both Parsonson et al. [2022] 's article and implementation, SMMSTSDDR
their article) was quite distant from the branching agent originally described in [Etheve et al. 2020 In fact, in Parsonson
we found that the baseline labeled as DON-TreeMDP
ct al. [022]. the Etheve et al. [2020] branching agent not trained on TreeMDP trajectories, but on retrospective trajectories built from TreeMDD episodes, using DFS construction heuristic. Therefore, Parsonson et al. 2022] could not conclude on the superiority of retro branching over TreeMDP, nor could they assess the limitations of DFS-based RL agents. In contrast, our contribution provides compelling evidence that, while DFS is generally expected to hinder the training performance of RL agents due to its reputation as suboptimal node selection policy, the theoretical guarantees brought by DFS in BBMDP enable to surpass prior state-of- tfeth--rrt non-DFS agents. We believe this because optimizing the node selection policy has less influence tree size performance compared to optimizing the variable selection policy, as evidenced by Etheve 2021
E
Neural network
State representation Following the works Gasse al. 2019]. MILPs are best represented by bipartite graphs 9 (Vg. Cg, Eg) where Vig denotes the set of variable nodes, Cg denotes the set of constraint nodes, and Eg denotes the set of edges linking variable and constraints nodes. Nodes ug E Vg and cg Cg connected if the variable associated with eg appears in the constraint associated with cg. Given MILP P, defined as in Section 2.1 its associate bipartite representation G + nodes. We use bipartite graphs encode the information contained in (o,, To ). as defined in section 3.2 In our experiments, IL and PG-tMDP agents use the list of features of Gasse al. [2099] to represent variable nodes, constraint nodes and edges, while BBMDP DON-TreeMDD and DQN- agents also make use of the additional features
has [G] = Dg + |Cgl
introduced by Parsonson et al. 2022
Network architecture All RL agents utilize the graph convolutional network architecture described in Scavuzzo et al. [2022] and Parsonson et al.] (2022). In DQN-BBMDP, the architecture differs slightly, with the final layer outputting distribution vectors Im instead of scalar values in IR.
F Instance dataset
Instance datasets used for training and evaluation are decribed in Table 4 We trained and tested on instances of same dimensions as Scavuzzo et al. (2022) and Parsonson et al. 2022]. As a reminder, the size of action set A is equal to the number integer variables P. Consequently, action set sizes in the Ecole benchmark range from 30 to 480 for train test instances and from 50 to 980 for transfer instances.
22

---

Table 4: Instance size for each benchmark. Performance is evaluated on instances that match
the size of the training instances, as well as on larger instances, to further assess the generalization capacity of our agents. Last two columns indicate the approximate number of integer variables after presolve, both for train / test and transfer instances.
Parameter value
Int. variables
Benchmark
Generation method
Parameters
Train / Test
Transfer
Train Test
Transfer
Combinatorial auction
Items Bids
100
200
Leyton-Brown et al.
2000
500
1000
100
200
Items
500
1000
Set covering
Balas and Ho
1980
Sets
1000
1000
100
130
Maximum independent set
Bergman al
2016
Nodes
500
1000
480
980
Multiple knapsack
Items Knapsacks
100
100
Fukunaga 2011
12
30
50
G Training pipeline
DQN Implementation In Algorithm pipeline. Our DQN implementation includes several Rainbow-DQN features [Hessel et al. 2017 double DQN (Van Hasselt al., [016]) n-step learning and prioritized experience replay (PER)
provide description of DQN-BBMDP training
Schaul 2015). Moreover, as DON-BBMDP learns distributions representing Q-values, it integrates
elements of Bellemare al. 2017
Algorithm DQN-BBMDP
for t O....V 1 do
Draw randomly an instance Po-
Solve P by acting following a combined e-greedy and Boltzman exploration according to qe
Collect transitions along the generated tree (8i, di, Σ5= Pitjr 8i+k) and store them into
replay buffer Breplay-
Update 6e using the loss described in Sec 3.3 on transition batches drawn from Breplay-
end for
Exploration We train agents following Boltzmann and e-greedy exploration combined. Con- cretely, agents select actions uniformly from A with probability while following a Boltzmann exploration strategy with temperature for the remaining probability 1 1-c The decay rates for and are listed in Table
we defined R(s, a) 2 for transition, so that the overall value of trajectory matched the size of the B&B tree. In practice, all negative constant reward model yield cquivalent optimal policies BBMDP, therefore, we chose to implement R(s, a) = -1 for all RL baselines in order to allow clearer comparison between BBMDP and TrecMDP agents.
Reward model Section 3.1
Training parameters 3 the list of hyperparameters used train DQN agents on the Ecole benchmarks. To allow fair comparisons, when applicable, we keep SCIP parameters, training parameters and network architectures fixed for DQN-agents.
H
Validation curves
All experiments were conducted on an NVIDIA DGX A100 system equipped with 8x A100 40GB GPUs, 2x AMD EPYC 7742 64-core CPUs (128 threads total), and I TB of DDR4 RAM. We present validation curves for DQN-BBMDP, DQN-TreeMDP and DQN-Retro in Figure For each benchmark we trained for 200k gradient steps, which took approximately days for combinatorial auction instances, days for set covering instances, 5 days for multiple knapsack instances and 7
23

---

Table Training parameters for all DQN branching agents, For DQN-Retro, we take y 0.99 as in Parsonson et al. 2022].
Module
Training parameter
Valuc
Batch size
128
Optimizer
Adam
k-step return
Q-learning
Learning rate
10-5
Discount factor Y
1.0
Agent steps per network update Soft target network update Tree
10
10
Replay buffer
Buffer minimum size [Breplaylintt Buffer maximum capacity |Breptoylmox
x 10
100 x 10
PER a PER Benst
0.6
0.4
Prioritized experience replay
PER final
1.0
Bout - y learner steps
100 x 10 10
Minimum experience priority
Start exploration probability Cinst
1.0
Minimum exploration probability Emin
10-2
Exploration
e-decay
10-4
Start temperature Tinit
1.0
Minimum temperature Timén
10 10-3 3
r-decay
10
Zoii
HL-Gauss (only for DQN-BBMDP)
16
18
days for maximum independent set instances. As shown in Figure 4 interrupted before final convergence 3 out of benchmarks, hinting that performance could likely be improved by training for more steps.
DQN-BBMDP training was
I Additional computational results
In this section, we include further computational results on instances of the Ecole benchmark.
Table provides additional performance metrics to compare the different baselines across test and transfer benchmarks. For each benchmark, we report the number of wins and the average rank of each baseline across 100 evaluation instances. The number of wins is defined as the number of instances where baseline solves MILP problem faster than any other baseline. When multiple baselines fail to solve an instance to optimality within the time limit, their performance is ranked based on final dual gap.
Finally, Table recapitulate the computational results presented in Table 1 and provides for each baseline the per-henchmark standard deviation over five seeds, well as the fraction of test instances solved to optimality within the time limit.
24

---

Table 6: Additional performance metries for each baseline on train / test and transfer instance benchmarks, see Appendix F for instance details. For each benchmark, we report the number of wins, and the average rank of each baseline across the 100 evaluation instances. We also report for each baseline the fraction of test instances solved to optimality within time limit. The number of wins defined as the number of instances where baseline solves MILP problem faster than all other baselines. When multiple baselines fail to solve an instance to optimality within time limit, their performance ranked based on final dual gap.
Train Test
Transfer Wins
Method
Solved
Wins
Rank
Solved
Rank
SCIP
100/100
8/100
5.7
100/100
10/100
II.
100/100
1/00
3.8
100/100
29/100
1.8
IL-DFS
100/100
35/100
2.1
100/100
58/100
1.7
PG-MMPP
100/100
0/100
6.6
78/100
0/100
DQN-IMDP
100/100
11/100
2.9
96/100
0/100
5.0
DON-Retro
100/100
1 1/100
4.9
98/100
0/100
5.1
DQN-BBMDP
100/100
44/100
1.9
100/100
3/100
4.2
Set covering
Train / Test
Transfer
Method
Solved
Wins
Rank
Solved
Wins
Rank
SCIP
100/100
14/100 1/100
4.1
100/100 1000
14/100
3.51
II. 100/100
16/100
3.5
100/10 100
47/100
1.7
IL-DFS
100/100
31/100
2.6
100/ 100
20/ 1001
2.5
PG-MMDP
100/100
0/100
5.7
100/100
0/100
5.8
DQN-IMDP
100/100
0/100
6.2
100/100
0/100
6.5
DON-Retro
100/100
10/100
100/100
1/100
4.6
DQN-BBMDP
100/100
34/100
2.3
100/100
18/100
2.9
Combinatorial Auction
Train / Test
Transfer
Method
Solved
Wins
Rank
Solved
Wins
Rank
SCIP
100/100
9/100
5.7
100/100
7/100
4.5
II.
100/100
72 72/100 /100
1.6
100/100
57 57/100
1.7
IL-DFS
100/100
10/100
2.4
100/100
0/100
3.2
PG-MMDP
100/100
0/100
4.9
100/100
36/100
1.8
DQN-MMDP
100/100
1/100
4.8
85/100
0/100
6.1
DetrRetro
100/100
6/100
5.4
22/100
0/100
6.7
DQN-BBMDP
100/100
2/100
3.3
95/100
0/100
4.2
Maximum Independent Set
Train / Test
Transfer
Method
Solved
Wins
Rank
Solved
Wins
Rank
SCIP
100/100
88/100
1.4
100/100
60/100
1.9
IL
100/100
1/100
4.5
100/100
6/100
IL-DFS
100/100
1/100
5.8
98/100
0/100
6.0
PG-IMDP
100/100
0/100
6.0
98/100
5/100
DQN-IMDP
100/100
1/100
3.5
99/100
14/100
3.5
DQN-Rette
100/100
3/100
3.5
98/100
9/100
3.8
100/100
6/100
3.3
100/100
6/100
4.3
Multiple Knapsack
25

---

Table 7: Computational performance comparison four MILP benchmarks. Following prior works,
we report geometrical mean over 100 instances, averaged over seeds, as well as per-benchmark standard deviations.
Train / Test Time
Transfer
Method
Nodes
Solved
Nodes
Time
Solved
Random
3289 = 4.2%
5.9 + 4.3%
100/100
270365 + 9.5%
811 7.9%
60/100
SB
35.8 + 0.0%
12.93 + 0.0%
100/100
672.1 + 0.0%
398 + 0.2%
82/100
SCIP
62.0 + 0.0%
2.27 + 0.0%
100/100
3309 + 0.0%
48.4 = 0.1%
100/100
II.
133.8 + 1.0%
0.90 4.8%
100/100
2610 + 0. 0.7%
23.1 = 1.5%
100/100
IL-DES
136.4 + 1.8%
0.74 + 5.3%
100/100
3103 + 2.0%
22.5 + 3.1%
100/100
PG-IMDP
649.4 + 0.7%
2.32 + 2.4%
100/100
44649 + 3.7%
221 + 4.1%
78/ 100
DQN-MMDP
175.8 + 1.1%
0.83 + 4.5%
100/100
8632 + 4.9%
71.3 = 5.8%
96/100
DQN-Retro
183.0 + 1.2%
1.14 4.1%
100/100
6100 4.2%
59.4 4.2%
98/100
DQN-BBMDP
152.3 + 0.6%
0.77 5.6%
100/100
5651 + 2.2%
46.4 + 3.3% 100/100
Set covering
Train / Test Time
Transfer
Method
Nodes
Solved
Nodes
Time
Solved
Random
1111 + 4.3%
2.16 1 6.6%
100/100 100/100
354650 6.7%
814 7.1%
64/100
SB
28.2 + 0.0%
6.21 + 0.1%
100/100
389.6 + 0.0%
255 1 0.2%
88/100
SCIP
20.2 = 0.0%
1.77 + 0.1%
100/100
1376 = 0.0%
14.77 = 0.1%
100/100
IL
83.6 1 0.8%
0.65 1 7.3%
100/100
1309 1 1.6%
9.4 1: 2%
100/100
IL-DFF
95.5 0.9%
0.56 1 7.1%
100/100
1802 1 2.0%
10.2 1.8%
100/100
PG-MDP
168.0 + 2.8%
0.94 + 6.0%
100/100
6001 + 2.7%
30.7 = 2.4%
100/100
DQN-IMDP
203.3 + 4.2%
1.11 + 4.0%
100/100
20553 3.8%
116 + 3.9%
100/100
DQN-Retro
103.2 1.2%
0.78 + 7.5%
100/100
2908 + 1.7%
18.4 2.7%
100/100
BDN-BBMDP
97.9 1.2%
0.62 = 8.5%
100/100 1000
2273 - 1.9%
11.8 2.0%
100/100
Combinatorial auction
Train Test Time
Transfer
Method
Nodes
Solved
Nodes
Time
Solved
Random
386.8 + 5.4%
2.01 + 4.8%
100/100
215879 + 6. 6.7%
2102 + 6.2%
25/100
SB
24.9 + 0.0%
45.87 + 0.4%
100/100
169.9 + 0.2%
2172 + 0.9%
15/100
SCIP
19.5 + 0.0%
2.44 + 0.4%
100/100
3368 0.0%
90.0 = 0.2%
100/100
IL
40.1 1 3.45%
0.36 3.1%
100/100
1882 + 4.0%
38.6 + 3 3.2%
100/100
IL-DES
69.4 6.5%
0.44 4.8%
100/100
3501 2.7%
51.9 2.6%
100/100
PG-MMDP
153.6 +: 5.0%
0.92 2.6%
100/100
3133 1 4.6%
39.5 1 3.8%
100/100
DQN-IMDP
168.0 1 5.6%
1.00 3.4%
100/100
45634 7.4%
477 5.1%
85/100
DQN-Reen Retro
223.0 + 4.1%
1.81 3.6%
100/100
119478 + 6.1%
1863 + 4.8%
22/100
DQN-BBMDD
103.2 + 9.3%
0.62 6.8%
100/100
7168 + 5.3%
81.3 = 4.2% 95/100
Maximum independent set
Train Test Time
Transfer Time
Method
Nodes
Solved
Nodes
Solved
Random
733.5 1 13.0%
0.55 1. 6.9%
100/100
93452 1 14.3%
70.6 1: 9.2%
99/100
SB
161.7 + 0.0%
0.69 0.1%
100/100
1709 1 0.5%
12.5 1 0.9%
100/100
SCIP
289.5 + 0.0%
0.53 0.2%
100/100
30260
0.0%
22.14 1 0.2%
100/100
IL
272.0 +: 12.9%
0.69 8.5%
100/100
9747 + 7.5%
46.5 + 6.6%
100/100
IL-DES
472.8 13.0%
1.07 9.0%
100/100
43224 9.0%
131 8.6%
98/100
PG-MDP
136.9 + 21.2%
1.57 + 16.9%
100/100
35614 + 14.3%
123 + 15.4%
98/100
DON-IMDP
266.4 + 7.2%
0.73 4.6%
100/100
22631 + 8.6%
65.1 5.5%
99/100
DON-Retro
250.3 + 9.5%
0..7 5.0%
100/100
27077 + 8.8%
79.5 + 6.2%
98/100
DQN-BBMDD
236.6 6 1 6.4%
0.66 + 2.7%
100/100
37098 + 7.0%
109 = 4.9%
100/100
Multiple knapsack
26

---

Covering
Combinatorial Auction
DON ootie DON autre
10"
Total number of nodess
Total number of nodes
20
10a-
2039
46
d0
sb
1d0
126
140
160
160
200
25
50
75
100
125
150
175
200
Training (1c3)
Training (1e3)
Maximum Independent Set
DON-31MEP
Multiple Knapsack
Dok Antro
Das
Total number of nodes
103-
Total of
M
25
50
75
160
125
150
175
200
Training step (1e3)
25
50
200
Training step (1e3)
Figure 4: Validation curves for DQN-BBMID. DON-Retro and DQN-IMDP agents, in log scale. Throughout training, agents are evaluated on 20 validation instances after each batch of 100 training instances solved. Note that on the multiple knapsack benchmark, none of the agents reach conver- gence.
27


Reviews:
[{"review_id": "3eAnZ6w3df", "reviewer": "Reviewer_1t91", "summary": "The paper proposes BBMDP, a principled formulation of learning better branching policies in branch & bound (B&B). The main analytical and algorithmic contribution involves a) identifying an issue with prior RL-based approaches to learning to search in B&B and b) reformulating the optimization problem as a proper stochastic shortest path problem. Specifically, the approach seeks to learn a branching policy to find the shortest sequence of B&B trees (representing partial solutions during search) that lead to a solution. Doing so permits leveraging techniques from Q-function learning (i.e., Bellman equations). Experiments are conducted on standard MILP benchmarks. Results indicate that BBMDP performs strongly compared to prior work on RL-based solutions (e.g., TreeMDP) on both same-size test instances and larger-size transfer instances. However, BBMDP is unable to clearly outperform a strong baseline (IL).", "questions": "1. What's the formal definition of $\\bar{V}$ (Line 193)? Same question for \"opposite\".\n\n2. Would popular PG algorithms (PPO, GRPO) make a difference here? How challenging would it be to include them in the experiments?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- The paper studies an interesting and important problem. B&B algorithms are widely used for combinatorial optimization and any improvements here is likely to be of significant interest and have a large impact.\n\n- The paper is well written. The problem formulation is clearly described. The description of prior work is very good.\n\n- The proposed approach is intuitively clear and mathematically rigorous. The optimization problem is well defined and the reformulation to stochastic shortest paths makes sense to me. The paper motivates its approach well by contrasting with prior work. As a result, it's easy to identify the main contributions, which are mostly analytical and algorithmic.\n\n- The experiments are carefully constructed on four common MILP benchmarks. Although BBMDP does not beat the IL baseline, it is able to outperform other RL agents, which is a nice result. The experiments and appendix include a lot of detail and the included code aids reproducibility.\n\n- Overall, I think the paper represents a solid contribution to the literature on learning search control knowledge for B&B algorithms.\n\n**Weaknesses**\n\n- I wasn't able to find any major issues with the paper. A minor point is that the definitions of a couple of important concepts needs to be formally defined (See Q1). Overall, I think this is a nice contribution to the literature on principled RL approaches to improve B&B algrorithms for MILPs.\n\n- (Not a weakness, more of an observation) Given the strength of the IL baseline and the importance of the HL-Gauss CE loss, it seems like learning a policy directly might be better / easier. However, PG-tMDP results suggests that might not be the case. Results seem mixed, at best. I was hoping the paper would explore this aspect in more detail and if / how popular policy gradient algorithms (PPO, GRPO, etc.) might fit in here. Including a discussion or empirical exploration of this aspect would be nice to have (but likely out of scope).", "was_revised": true, "final_justification": "After reading the other reviews, I continue to recommend acceptance of the paper, maintaining my current score.", "rebuttal": ""}, {"review_id": "zhRQ7si9ib", "reviewer": "Reviewer_euoY", "summary": "This paper introduces a novel branch and bound Markov decision process (BBMDP) framework for combinatorial optimization in Mixed-Integer Linear Programming (MILP).  \nThe authors formulate the process by modeling the traversal of B&B subtrees temporally, rather than structurally, and derive a corresponding Bellman equation that facilitates the use of reinforcement learning (RL) techniques.  \nThey evaluate BBMDP on benchmark problems and demonstrate that it outperforms existing RL-based approaches, achieving reductions in both computation time and the number of B&B nodes explored.", "questions": "4. How are child nodes generated during the B&B process?\n\n5. Is the value of each state updated after every iteration? If so, does the framework allow for previously visited nodes to be revisited in future steps?\n\n6. The network architecture is described only briefly in the experimental setup (line 293), with little discussion of its flexibility. If the architecture can be chosen freely, it raises an important question: to what extent does the choice of architecture affect performance? This aspect remains unexplored in the paper.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strength**:\n* Enables the use of RL frameworks within B&B solvers.\n* Models the B&B process as a temporal decision-making problem, allowing for the incorporation of time-dependent strategies (e.g., node selection with early stop).\n* BBMDP demonstrates strong empirical performance, outperforming other RL-based approaches in benchmark tests.\n\n\n**Weakness**:\n1. The presentation of the work is hard to follow when a nomenclature is not present. Since there are symbols with both B&B and RL their defitions are hard to find from the paragraph, making it difficult for readers to keep track of the notations.\n\n2. The overall structure of the paper could be improved for better readability. For example,\n  * it would be helpful to make a summary on table 5 which compares BBMDP and TreeMDP in Appendix H. Absense of this summary leads to the confusing regarding the key novelty of BBMDP. \n  * the ordering of sections in the appendix feels extremely arbitrary, making it difficult to locate relevant details. \n  * some concepts in the appendix are mentioned only once in main text without clarification. This makes readers puzzled. An example is the inclusion of HL cross-entropy in line 251, where the motivation of introducing this concept is placed into the appendix, not the main context.\n  * the rationale behind several design choices is not well explained. An example is the reward function being set to –2 for all transitions. It seems the authors try to minimize the size of the B&B tree via this settings, but this initiative is not clearly stated in the paragraph.\n  * a figure showing the workflow of BBMDP, similar as Figure 2, would greatly help readers' understanding.\n  * the benchmarks lack a summary of problem difficulty levels, making it hard to assess the significance of the reported performance gains.\n\n3. A missing element throughout the manuscript is a clear explanation of why and how choices were made on using temporal models. \n  * What is the major initiative for authors to use such a temporal sequence model instead of structural model? \n  * While the authors argue that temporal modeling allows for MDP to be applied, this shift also introduces new challenges. Specifically in BBMDP, branching decisions are no longer structurally constrained to child nodes but all future nodes in the domain, which increases the complexity of selecting the optimal next node. This potentially leads to higher variance in trajectories and longer training times, intuitively. However, the authors have not discussed the impact of this added complexity such as how the training is performed.", "was_revised": true, "final_justification": "I can rate the submission with score of 4.\n\nAfter my major concerns are partially addressed by original submission and other reviewers, I can see the paper has made clear contribution to RL in B&B domain, which is significant and with high impact to the field (score of 5).  \nHowever, the clarity of the paper is insufficient to me (-1): \n* many concepts are arbitarily placed into the main text without justification\n* the reason on the choice of policy network is unexplained (ignore authors' rebuttal)\n\nTherefore, I will rate 4 for this submission.", "rebuttal": ""}, {"review_id": "PoZSCX0JIU", "reviewer": "Reviewer_P4AA", "summary": "The paper revisits reinforcement learning for branching in MILP solving. The paper proposes a new MDP formulation. This differs from the previous sota, TreeMDP, in that it is a standard MDP. This has theoretical advantages and potentially practical advantages. An experimental study on standard benchmark instances shows improved performance compared to previous RL approaches, and narrows the gap to the sota supervised learning approach for branching.", "questions": "Can you consider the \"real world\" production scheduling instances from:\nWang, J., Wang, Z., Li, X., Kuang, Y., Shi, Z., Zhu, F., Yuan, M., Zeng, J., Zhang, Y., Wu, F., 2024a. Learning to cut via hierarchical sequence/set model for efficient mixed-integer programming. IEEE Transactions on Pattern Analysis and Machine Intelligence 46, 9697–9713. doi:10.1109/TPAMI.2024.3432716.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Attempts to use RL for variable selection in MILP branch-and-bound solving has not yet reached their potential.  The paper well situates that in principle RL can surpass supervised learning, namely imitation learning from strong branching.  A difficulty has been formulating a MDP for the RL task that has the markov property.  Etheve et al in 2020 made an not entirely satisfactory effort, which was formalised by Scavuzzo et al in 2022 as the TreeMDP, accompanied by a careful empirical study.  This lead to the sota RL approach of Parsonson et al also in 2022.  A strength of the present submission is to compare its approach with all these earlier approaches.\n\nThe main contribution of the paper is a MDP formulation as a standard MDP, i.e. not with the tree property.  This is an important step.  The paper has some nice technical examples and counter-examples, and overall provides illumination into the branching-via-RL task.\n\nFurther, the empirical study follows Scavuzzo et al and is done well.  The authors (re-)implement Etheve et al and Parsonson et al, and compare on four standard instance classes.  Both test and transfer instances are presented, together with an ablation study.  The results compare against strong branching, SCIP 8's default branching (although there is now SCIP 9), IL and IL with DFS.  The proposed approach is better in general than previous RL approaches and comes closer than them to IL and/or SCIP.\n\nThe paper has clear exposition, and the appendices are helpful.  There is sufficient information to reproduce the work.\n\nThis paper will be interesting for the MILP community.  It will have interest for a subset of the ML community.  There is not new RL theory here.  Altogether this gives this reviewer a Significance score and an Originality score of fair.  Explicitly, that is not a criticism of the technical quality.  In sum, a valuable contribution to the interface of learning and optimisation in the context of MILP.", "was_revised": true, "final_justification": "The authors are thanked for providing a response to reviewers, which was read and does not lead to a change in rating.", "rebuttal": ""}, {"review_id": "M8JfZJcHr3", "reviewer": "Reviewer_Qj2v", "summary": "This paper addresses the problem of learning branching policies for solving Mixed-Integer Linear Programs (MILPs) using reinforcement learning. The authors first identify a key theoretical limitation in prior work, arguing that it is not a true Markov Decision Process and is incompatible with standard multi-step RL algorithms. The paper’s main contribution is the introduction of a new, principled formulation called the Branch and Bound Markov Decision Process (BBMDP). This formalization as a standard MDP allows the authors to leverage a broader range of well-established RL techniques, such as k-step temporal difference learning. Finally, the authors present computational experiments demonstrating that an agent trained with their BBMDP formulation outperforms previous state-of-the-art RL agents on several standard MILP benchmarks.", "questions": "Please see the Weaknesses part for my main questions. Besides, there are several minor questions:\n1.\tWhat is the computational and memory overhead of maintaining the full B&B tree state in BBMDP compared to TreeMDP’s simpler node-based representation, particularly for large problem instances?\n2.\tHow does the k-step TD performance of BBMDP compare to TreeMDP across a more comprehensive range of k values (e.g., k=2, 4, 5)?\n3.\tHow sensitive is the performance gain from HL-Gauss loss to its hyperparameters across different problem types, and were these values tuned specifically for the benchmarks used?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nA Principled Formulation. The paper’s primary strength is the introduction of the “Branch & Bound Markov Decision Process” (BBMDP). This is a significant contribution, advancing the field from “MDP-inspired” but technically flawed frameworks (e.g., TreeMDP) to a principled, standard MDP formulation that is theoretically sound.\nInsightful Analysis. The paper provides a clear and insightful diagnosis of a core issue with prior approaches in Section 3.2, “Misconceptions in Learning to Explore the B&B Tree.” This sharp analysis of how the global incumbent breaks subproblem independence is a valuable contribution in itself and provides strong motivation for the proposed framework.\nComprehensive Performance Validation. The experimental results in Section 4 provide strong validation for the proposed framework. The DQN-BBMDP agent consistently outperforms the prior state-of-the-art RL agent (notably DQN-Retro) across all four standard benchmarks, on both in-distribution test instances and larger transfer instances, as shown in Table 1.\nWeaknesses\nThe main weakness of this paper is the insufficient experimental evidence for some of the claims made in its theoretical section:\n1.\tAblation study may not be fully comprehensive. By removing only one component at a time, it does not explore potential interaction effects. It is therefore difficult to ascertain whether the benefits of the different components are purely additive or if they have synergistic relationships that are not captured by the current experimental design.\n2.\tA significant weakness of this work is its strict reliance on a Depth-First Search (DFS) node selection strategy. This becomes problematic as the ablation study appears to show that performance can be slightly better without the DFS constraint, despite it being theoretically necessary for the Markov property. This apparent contradiction is not sufficiently addressed in the main text and warrants a more detailed discussion to reconcile the theoretical foundation with the empirical evidence.\n3.\tThis paper argues that the BBMDP framework enables the application of a wide range of standard RL algorithms. However, this central claim is not fully substantiated by the experiments, which are limited to a single, well-tuned DQN agent. The paper would be more convincing if it demonstrated the framework’s efficacy with other classes of RL algorithms (e.g., policy gradient methods) to validate this claim of generality.", "was_revised": false, "final_justification": "", "rebuttal": ""}]

Author rebuttal:

Meta-review: The paper introduces B&B-MDPs (or BBMDPs), a Markov Decision Process formulation for variable selection in branch & bound strategies for MILPs. In particular, it addresses key shortcomings of prior RL-based approaches, such as TreeMDP, by leveraging a temporal MDP reformulation of the selection problem and applying a reinforcement learning algorithm to solve it. The authors also provide empirical results on four standard MILP benchmarks, showing that BBMDP  outperforms previous RL approaches and narrow the gap to existing imitation learning baselines.

The review team was generally positive towards the paper, with four reviewers ultimately supporting acceptance. The initial reports highlighted that the idea is novel and well motivated. The paper is also nicely written, with a convincing empirical validation showing comparable or better performance than existing RL agents for variable selection (including the highly cited TreeMDP). There were a few concerns about the clarity of exposition, completeness of the ablation study, and the reliance on depth-first search (DFS) as a simplifying assumption, given modern MILP solvers leverage variations of strong branching and other sophisticated techniques. 

The rebuttal period, however, revealed some procedural challenges. Authors submitted their rebuttal late, and reviewers were instructed to disregard it. Despite this issue, most reviewers found their concerns adequately addressed by the original submission, the other reports, and the subsequent discussion, and agreed that these limitations do not undermine the significance of the contribution. Specifically, Reviewer Qj2v emphasized that the ablation study clarified the benefits of the BBMDP formulation, while Reviewer euoY, despite initial reservations about clarity and structure, raised their score after recognizing the framework’s significance. Reviewer P4AA praised the careful positioning of the work within the literature and the robustness of the empirical comparisons, and Reviewer 1t91 found the paper to be a solid and rigorous contribution with clear impact on learning to search in MILPs. 

Overall, the consensus is that the paper represents a valuable step forward at the intersection of optimization and reinforcement learning, and merits acceptance at NeurIPS. The review team was particularly engaged and excited about this paper.
Decision: Accept (poster)