<figure><img src="image_1.png" /></figure>

HAL
open science

# Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, Emmanuel Rachelson

► To cite this version:

Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan, Safia Kedad-Sidhoum, et al. Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization. AAAI 2026, Jan 2026, Singapour, Singapore. hal-05488800

HAL Id: hal-05488800

https://hal.science/hal-05488800v1

Submitted on 2 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Planning in Branch-and-Bound: Model-Based Reinforcement Learning for Exact Combinatorial Optimization

Paul Strang¹, ³, Zacharie Alès², Côme Bissuel¹, Olivier Juan¹,
Safia Kedad-Sidhoum³, Emmanuel Rachelson⁴

¹EDF R&D, France
{paul.strang, come.bissuel, olivier.juan}@edf.fr

²ENSTA Paris, Institut Polytechnique de Paris, France

zacharie.ales@ensta.fr

³CNAM Paris, CEDRIC, France

safia.kedad_sidhoum@cnam.fr

⁴ISAE-SUPAERO, France

emmanuel.rachelson@isae-supaero.fr

## Abstract

Mixed-Integer Linear Programming (MILP) lies at the core of many real-world combinatorial optimization (CO) problems, traditionally solved by branch-and-bound (B&B). A key driver influencing B&B solvers efficiency is the variable selection heuristic that guides branching decisions. Looking to move beyond static, hand-crafted heuristics, recent work has explored adapting traditional reinforcement learning (RL) algorithms to the B&B setting, aiming to learn branching strategies tailored to specific MILP distributions. In parallel, RL agents have achieved remarkable success in board games, a very specific type of combinatorial problems, by leveraging environment simulators to plan via Monte Carlo Tree Search (MCTS). Building on these developments, we introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages a learned internal model of the B&B dynamics to discover improved branching strategies. Computational experiments empirically validate our approach, with our MBRL branching agent outperforming previous state-of-the-art RL methods across four standard MILP benchmarks.

## 1 Introduction

Mixed-Integer Linear Programming (MILP) plays a central role in combinatorial optimization (CO), a discipline concerned with finding optimal solutions over typically large but finite sets. Specifically, MILPs offer a general modeling framework for NP-hard problems, and have become indispensable in tackling complex decision-making tasks across fields as diverse as operations research (Hillier and Lieberman 2015), quantitative finance (Mansini et al. 2015) and computational biology (Gusfield 2019). Modern MILP solvers are built upon the branch-and-bound (B&B) paradigm (Land and Doig 1960), which systematically explores the solution space by recursively partitioning the original problem into smaller subproblems, while maintaining provable optimality guarantees. Since the 1980s, considerable research and engineering effort has gone into refining these solvers, resulting in highly optimized systems driven by expert-designed heuristics tuned over large benchmarks.

(Bixby 2012; Gleixner et al. 2021). Nevertheless, in operational settings where structurally similar problems are solved repeatedly, adapting solver heuristics to the distribution of encountered MILPs can lead to substantial gains in efficiency, beyond what static, hand-crafted heuristics can offer. Recent research has thus turned to machine learning (ML) to design efficient, data-driven B&B heuristics tailored to specific instance distributions (Scavuzzo et al. 2024). The variable selection heuristic, or branching heuristic, plays a particularly critical role in B&B overall computational efficiency (Achterberg and Wunderling 2013), as it governs the selection of variables along which the search space is recursively split. A key milestone was achieved by Gasse et al. (2019), who first managed to outperform human-expert branching heuristics by learning to replicate the behaviour of a greedy branching expert at lower computational cost. While subsequent works succeeded in learning efficient branching strategies by reinforcement (Etheve et al. 2020; Scavuzzo et al. 2022), none have yet matched the performance achieved by imitation learning (IL) approaches. This trend extends beyond MILPs to combinatorial optimization problems at large, as reinforcement learning (RL) baselines consistently underperform both handcrafted heuristics and IL methods trained to replicate expert strategies across various CO benchmarks (Berto et al. 2023). Yet, if the performance of IL heuristics are capped by that of the experts they learn from, the performance of RL agents are, in theory, only bounded by the maximum score achievable. One of the main challenge lies in the high dimensionality and combinatorial complexity of CO problems, which exacerbates exploration and credit assignment issues in sequential decision making. While supervised learning can partially mitigate these issues by scaling up neural architectures and exploiting abundant labeled data, such approaches are impractical in RL due to sample inefficiency and unstable learning dynamics (Liu et al. 2023).

Despite these challenges, RL has achieved notable success in a specific subset of combinatorial problems, board games, reaching superhuman performance by leveraging environment simulators to perform model-based planning. Specifically, the integration of learned policy and value functions
<figure><img src="image_3.png" /><figcaption>Figure 1: Aggregate normalized solving time performance obtained on test instances by SCIP (Bestuzheva et al. 2021), IL, RL and random baselines across the Ecole benchmark (Prouvost et al. 2020), in log scale. These baselines are formally introduced in Section 5.</figcaption></figure>

with look-ahead search via Monte Carlo Tree Search (MCTS) was found to steer action selection towards high-value states, effectively mitigating exploration and credit assignment issues in sparse-reward environment settings. Inspired by the work of Schrittwieser et al. (2020), we seek to extend the applicability of MCTS-based RL algorithms from board games to exact combinatorial optimization. To that end, we introduce Plan-and-Branch-and-Bound (PlanB&B), a model-based reinforcement learning (MBRL) agent that leverages an internal model of the B&B dynamics to learn improved variable selection strategies. To the best of our knowledge, this is the first MBRL agent specifically designed to solve CO problems. As shown in Figure 1, our agent achieves state-of-the-art performance on test sets across four standards MILP benchmarks (Prouvost et al. 2020), surpassing prior IL and RL baselines. These results suggest that the branching dynamics in B&B can be approximated with sufficient fidelity to enable policy improvement through planning over a learned model, opening the door to broader applications of MBRL to mixed-integer linear programming.

## 2 Problem statement

**Mixed-integer linear programming.** We consider mixed-integer linear programs (MILPs), defined as:

$$P: \begin{cases} \min c^{\top} x \\ l \le x \le u \\ Ax \le b; \quad x \in \mathbb{Z}^{|\mathcal{I}|} \times \mathbb{R}^{n-|\mathcal{I}|} \end{cases}$$

with $n$ the number of variables, $m$ the number of linear constraints, $l, u \in \mathbb{R}^n$ the lower and upper bound vectors, $A \in \mathbb{R}^{m \times n}$ the constraint matrix, $b \in \mathbb{R}^m$ the right-hand side vector, $c \in \mathbb{R}^n$ the objective function, and $\mathcal{I}$ the indices of integer variables. In this work, we are interested in repeated MILPs of fixed dimension $\{P_i = (A_i, b_i, c_i, l_i, u_i)\}_{i \in \mathcal{D}}$ sampled according to an unknown distribution $p_0$.

In order to solve MILPs efficiently, the B&B algorithm iteratively builds a binary tree $(V, E)$ where each node corresponds to a MILP, starting from the root node $v_0 \in V$ representing the original problem $P_0$. The incumbent solution $\bar{x} \in \mathbb{Z}^{|\mathcal{I}|} \times \mathbb{R}^{n-|\mathcal{I}|}$ denotes the best feasible solution

found at current iteration, its associated value $GUB = c^{\top}\bar{x}$ is called the global upper bound on the optimal value. The overall state of the optimization process is thus captured by the triplet $s = (V, E, \bar{x})$, we 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 $O$ the set of unvisited or open nodes, such that $V = C \cup O$. Figure 2 illustrates how B&B operates on an example. Initially, $GUB = \infty$, $O = \{v_0\}$, and $C = \emptyset$. At each iteration $t \ge 0$, the node selection policy $\rho: S \to O$ selects the next node to explore. Let $x_{LP}^* \in \mathbb{R}^n$ be the optimal solution to the linear program (LP) relaxation of $P_t$, the MILP associated with the current node $v_t$:

* If the relaxation of $P_t$ admits no solution, $v_t$ is marked as closed and the branch is pruned by infeasibility. If $x_{LP}^* \in \mathbb{R}^n$ exists, and $GUB < c^{\top}x_{LP}^*$, no integer solution in $P_t$ can improve $GUB$, thus $v_t$ is marked as closed and the branch is pruned by bound. If $x_{LP}^*$ is not dominated by $\bar{x}$ and $x_{LP}^*$ is feasible, a new incumbent solution $\bar{x} = x_{LP}^*$ has been found. Hence, $GUB$ is updated and $v_t$ is marked as closed while the branch is pruned by integrity.

* Else, $v_t$ is called branchable, as $x_{LP}^*$ admits fractional values for some integer variables. The branching heuristic $\pi: S \to \mathcal{I}$ selects a variable $x_b$ with fractional value $\hat{x}_b$, to partition the solution space. As a result, two child nodes with associated MILPs $P_- = P_t \cup \{x_b \le \lfloor \hat{x}_b \rfloor\}$ and $P_+ = P_t \cup \{x_b \ge \lfloor \hat{x}_b \rfloor\}$, are added to the set of open nodes $\mathcal{O}$ in place of $v_t$.<fnref n="1" />

This process is repeated until $\mathcal{O} = \emptyset$ and $\bar{x}$ is returned. The dynamics governing the B&B algorithm between two branching decisions can be described by the function $\kappa_\rho: S \times \mathcal{I} \to S$, such that $s' = \kappa_\rho(s, \pi(s))$. By design, B&B does not terminate before finding an 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 (2021) evidenced, the variable selection strategy $\pi$ is by far the most critical B&B heuristic in terms of computational performance. In practice, the total number of nodes of the B&B tree is used as an alternative metric to evaluate the performance of branching heuristics $\pi$, as it is a hardware-independent proxy for computational efficiency. Under these circumstances, given a fixed node selection strategy $\rho$, the optimal branching strategy $\pi^*$ associated with a distribution $p_0$ of MILP instances can be defined as:

$$\pi^* = \arg \min_{\pi} \mathbb{E}_{P \sim p_0} (|BB_{(\pi, \rho)}(P)|) \quad (1)$$

with $|BB_{(\pi, \rho)}(P)|$ the size of the B&B tree after solving $P$ to optimality following strategies $(\pi, \rho)$.

**Markov decision process formulation.** The problem of finding an optimal branching strategy according to Eq. (1) can be described as a discrete-time deterministic Markov decision process (MDP) $(S, A, \mathcal{T}, p_0, \mathcal{R})$. State space $S$ is the set of all B&B trees as defined previously, action space

<footnote n="1">¹$\hat{x}_b$ denotes the value of $x_b$ in $x_{LP}^*$. We use the symbol $\cup$ to denote the refinement of the bound on $x_b$ in $P_t$.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 2: Solving a MILP by B&B using variable selection policy $\pi$ and node selection policy $\rho$. Each node $v_i$ represents a MILP derived from the original problem, each edge represents the bound adjustment applied to derive child nodes from their parent. At each step, nodes $o_i \in O$ are re-indexed according to $\rho$.</figcaption></figure>

A is the set of all integer variables indices $\mathcal{I}$. Initial states are single node trees, where the root node is associated to a MILP $P_0$ drawn according to the distribution $p_0$. The Markov transition function is defined as $\mathcal{T} = \kappa_\rho$. Importantly, all states for which $O = \emptyset$ are terminal states. The reward model is defined as $\mathcal{R}(s, a) = -1$ for all transitions until episode termination. In this setting, the Bellman state-value function writes $V^\pi(s) = -\mathbb{E}_{a' \sim \pi(s')}[\sum_{t' \ge 0} \gamma^{t'}]$ for $s \in S$. Since episodes horizons are bounded by the (finite) largest possible number of nodes, we take a discount factor $\gamma = 1$. Indeed, under this formulation, the optimal policy $\pi^*$ defined in Eq. (1) also maximizes the state-value function $V^\pi(s)$ for all $s \in S$. Crucially, Etheve et al. (2020) and Scavuzzo et al. (2022) have shown that when the B&B tree is expanded following a depth-first-search (DFS) node selection policy, minimizing the total B&B tree size is achieved when any subtree is of minimal size. This allows the decomposition of B&B episodes into independent subtree trajectories, which helps mitigate credit assignment issues arising from the length of B&B episodes. Moreover, under $\rho = DFS$, $V^\pi$ can be decomposed as the sum of the negative size $\bar{V}^\pi$ of the subtrees rooted in the open nodes of $s \in S$:

$$V^\pi(s) = \sum_{o \in O} \bar{V}^\pi(o, \bar{x}_o), \qquad (2)$$

with $\bar{x}_o \in \mathbb{R}^n$ the incumbent solution when $o$ is selected for expansion. Conveniently, this decomposition enables to derive $V^\pi$ by training graph convolutional neural networks to approximate $\bar{V}^\pi$, using the MILP bipartite graph representation introduced by Gasse et al. (2019) as observation function for B&B nodes. Thus, as in previous works, we take $\rho = DFS$ in the remaining of the paper.

**MuZero.** Model-based reinforcement learning approaches exploit reversible access to the MDP to design policy improvement operators via planning (Silver et al. 2018; Hansen, Su, and Wang 2023). Monte Carlo Tree Search (MCTS) is among the most widely used planning algorithms in MBRL. Given access to an environment model ($\mathcal{T}$, $\mathcal{R}$), MCTS leverages value and policy estimates to select actions leading to promising states, while balancing an exploration-exploitation criterion. In order to extend the applicability of MCTS-based RL algorithms to broader control tasks where efficient simulators are not available, Schrittwieser et al. (2020) introduced MuZero, building upon the previous AlphaZero framework

(Silver et al. 2018). Concretely, MuZero learns a model consisting of three interconnected networks. First, the representation network $h$ maps raw state observations $s_t$ to a latent state $\hat{s}_t = h(s_t)$. This internal state can then be passed to the prediction network $f$ to obtain state policy and value estimates ($\hat{p}_t, \hat{v}_t$). Alternatively, latent states can be passed along with an action $a_t$ to the dynamics network $g$, to produce predictions for both the true reward $r_t$ and the internal representation $h(s_{t+1})$ of the next visited state when taking action $a_t$ at $s_t$: $g(\hat{s}_t, a_t) = (\hat{r}_t, \hat{s}_{t+1})$. At each decision step, MuZero integrates $h$, $f$ and $g$ to perform MCTS, thereby generating improved policy targets $\pi_t$ from which actions are sampled. During training, the model is unrolled for $K$ hypothetical steps and its predictions are aligned with sequences sampled from real trajectories collected by MCTS actors. By enforcing consistency between the predictions observed along simulated rollouts and those observed on real trajectories, MuZero constrains its model to capture only the information most relevant for accurately estimating future states' policy and value. This approach was shown to significantly reduce the burden of MDP dynamics approximation, unlocking the use of MBRL in visually complex domains where model-free RL methods had previously dominated. Subsequent work introduced several enhancements to the MuZero framework, including a temporal consistency loss for the dynamics network (Ye et al. 2021) and the use of Gumbel search for improved search efficiency in MCTS (Danihelka et al. 2022), which proved particularly useful in environments with large action space.

### 3 Planning in Branch-and-Bound

In the context of B&B, taking a step in the environment involves solving the two linear programs associated with the nodes generated by the branching decision. Unfortunately, this procedure is very expensive to simulate, and remains difficult to approximate accurately (Qian, Chételat, and Morris 2023). In order to overcome these limitations, we introduce Plan-and-branch-and-bound (PlanB&B), a model-based reinforcement learning agent adapting the MuZero framework to the B&B setting. Crucially, our learned model is not explicitly trained to solve linear programs. Instead, it learns the dynamics of an abstract, value-equivalent MDP that retains only the aspects of B&B essential for enabling policy improvement via MCTS.
**Model.** Let $s_t = (V_t, E_t, \bar{x}_t) \in S$ be a B&B tree where $V_t = O_t \cup C_t$, and let $o = \rho(s_t) \in O_t$ be the node currently selected for expansion. MuZero is originally designed to operate on full state observations $s_t$ as input to its internal model. In contrast, prior RL and IL branching agents have been designed to rely solely on information from the current B&B node, represented by the pair $(o, \bar{x}_t)$, and encoded using the MILP bipartite graph representation function from Gasse et al. (2019). While, under DFS, this local information is sufficient to recover the optimal policy at state $s_t$, it is generally insufficient to infer the subsequent state $s_{t+1}$. In fact, whenever taking action $a_t$ at $s_t$ leads to fathoming the subtree under $o$, the next visited node will be a leaf node that can not be deduced directly from the triplet $(o, \bar{x}_t, a_t)$. To address this, our model learns to predict recursively, along subtree trajectories, the internal representations $(\hat{o}_l, \hat{o}_r)$ associated with the left and right child nodes $(o_l, o_r)$ generated by the agent's branching decisions.<fnref n="2" /> Doing so, PlanB&B enables simulating imagined subtree trajectories while relying exclusively on the information available at the current node. The representation network $h$ first maps the pair $(o, \bar{x}_t)$ to an internal representation $\hat{o}$ which serves as the root node for the imagined tree $\hat{T} = (\hat{O}, \hat{C})$. Initially, $\hat{O} = \{\hat{o}\}$ and $\hat{C} = \emptyset$. The current imagined node $\hat{o}$ can then be passed to the dynamics network $g$ along with any action in $A$ to generate $(\hat{o}_l, \hat{o}_r)$. Since $r_t = -1$ is constant, $g$ is not tasked with predicting the future reward. However, note that if either of the real child nodes is pruned, either by bound, integrity or infeasibility, its associated subtree value is null, and, consequently, its node internal representation should not be considered for expansion by the model. To distinguish nodes leading to branching decisions from nodes destined to be pruned, we task the prediction network $f$ with estimating future nodes' branchability $b \in \{0, 1\}$, in addition to policy and subtree value estimates<fnref n="3" />. Based on the predicted branchability values, PlanB&B updates the sets $(\hat{O}, \hat{C})$ by discarding unbranchable nodes and designates the next visited node as the node in $\hat{O}$ with the greatest depth. If $\hat{O} = \emptyset$, the imagined subtree has been fully explored, and all subsequent recursive calls to $g$ will, by convention, receive a null reward. The overall interaction between the networks $h, f$, and $g$ during the simulation of $k$-step subtree trajectories is illustrated in Figure 3. In-depth model description as well as network architectures for $h, f$ and $g$ are presented in Appendix B.

**Data generation.** Since $\rho = DFS$, learning a policy minimizing the local subtree size is equivalent to learning a globally optimal policy. Therefore, we can use the model introduced in the previous paragraph to derive improved branching policy targets $\pi_t$ through planning. Due to the large action space size typically encountered in MILP environments, we implement Gumbel search (Danihelka et al. 2022), a variant of MCTS presented in Appendix C. Throughout the search,

<figure><img src="image_5.png" /><figcaption>Figure 3: Planning in B&B over a learned model. The combined use of $h, f$, and $g$ allows simulating subtree rollouts starting from the current B&B node. Here, $\hat{T}^3 = (\hat{O}^3, \hat{C}^3)$ with $\hat{O}^3 = \{\hat{o}_l^3, \hat{o}_r^3, \hat{o}_r^1\}$ and $\hat{C}^3 = \{\hat{o}_r^2\}$. To simplify notations, we write $z_j^i$ in place of $z_{\hat{o}_j}$ for $z \in \{p, \bar{v}, b\}$.</figcaption></figure>

the policy prior $\hat{p}_t^k$ associated with the imagined tree $\hat{T}^k$ is given by the policy prediction of the branchable node in $\hat{O}^k$ with the greatest depth. Similarly, following Eq. (2), the estimate state value $\hat{v}_t^k$ is obtained by summing the subtree value predictions $\bar{v}_{\hat{o}}$ of all open nodes in the imagined tree: $\hat{v}_t^k = \sum_{\hat{o} \in \hat{O}^k} \bar{v}_{\hat{o}}$. Thus, by combining networks $h, f$ and $g$ to simulate subtree rollouts, Gumbel search yields an improved target policy $\pi_t$ from which the selected action $a_t$ is sampled. Repeating this process generates B&B episodes that are stored in memory and subsequently used for training.

**Learning.** The agent is trained over $K$-step subtree trajectories $(s_t, a_t, \dots, s_{t+K})$ sampled from memory. As in MuZero, the model is unrolled from $s_t$ over $K$ steps to generate imagined trajectories $(\hat{T}^0, \dots, \hat{T}^K)$. As illustrated in Figure 3, for each step $k = 0, \dots, K$, the model recursively predicts $\hat{p}_t^k$ and $\hat{v}_t^k$ to approximate the Gumbel search policy $\pi_{t+k}$ and $n$-step return $z_{t+k} = -n + \hat{v}_t^{k+n}$ prediction targets. Moreover, the predicted branchability scores of imagined nodes are trained to match the true branchability labels of real nodes. To support this, we introduce a new self-supervised loss term $\mathcal{L}_T$, which enforces structural consistency between real and imagined subtrees, as well as hierarchical consistency between consecutive B&B node observations. The overall loss minimization objective can thus be summarized as:

$$ \mathcal{L}_t(\theta) = \sum_{k=0}^{K} \mathcal{L}_p(\pi_{t+k}, \hat{p}_t^k) + \mathcal{L}_v(z_{t+k}, \hat{v}_t^k) + \mathcal{L}_T(s_{t+K}, \hat{T}_K) $$

with $\theta$ the global parameter for $f, g, h$. Losses $\mathcal{L}_p, \mathcal{L}_v$ and $\mathcal{L}_T$ are presented in Appendix E.

## 4 Related work

Following the work of Gasse et al. (2019), several studies have explored adopting more expressive neural architectures,

<footnote n="2">²Following our convention, in DFS, $o_l$ designates the node selected immediately next for expansion, while $o_r$ designates the node selected once the subtree rooted in $o_l$ has been fathomed.</footnote>

<footnote n="3">³By construction, $\kappa_\rho$ ensures that the current node at $s_t$ is always branchable.</footnote>
from transformer-based models (Lin et al. 2022) to recurrent designs (Seyfi et al. 2023), for the purpose of learning to branch. However, these architectural extensions have yielded only limited gains. In parallel, theoretical and empirical analyses (Dey et al. 2021) have shown that the small trees produced by strong branching (SB), the branching expert used in Gasse et al. (2019), arise mainly from the extensive formulation tightening induced by solving large numbers of LPs, rather than from the intrinsic quality of its branching decisions.

Such findings cast doubt on the long-term effectiveness of purely imitation-based approaches. Since branching decisions unfold sequentially, reinforcement learning provides a principled alternative framework for learning to branch. Building on the works of Etheve et al. (2020) and Scavuzzo et al. (2022), Parsonson et al. (2022) explored training RL branching agents on B&B trees expanded following solvers' default node selection policies, rather than DFS. To address the partial observability induced by moving away from DFS, they trained their agent on retrospective trajectories, tree-diving trajectories extracted from original B&B episodes.

More generally, a substantial line of research (Nair et al. 2021; Paulus et al. 2022) has explored augmenting B&B heuristics with machine learning algorithms beyond variable selection. Building on the MDP formulation first proposed by He, Daume III, and Eisner (2014), recent RL contributions to primal search (Sonnerat et al. 2022; Wu and Lisser 2023), node selection (Etheve 2021; Zhang et al. 2025), and cut selection (Tang, Agrawal, and Faenza 2020; Wang et al. 2023) have primarily focused on deploying traditional model-free RL algorithms within the B&B framework, adapting the action space to suit the specific heuristic being targeted.

Finally, machine learning methods have been applied beyond the scope of exact combinatorial optimization. In large routing and scheduling problems, where exact resolution quickly becomes intractable, recent works have trained neural agents to act as direct-search heuristics, capable of producing strong feasible solutions (Kool, van Hoof, and Welling 2019; Chalumeau et al. 2023). Drawing inspiration from model-based planning, Pirnay and Grimm (2024) proposed a self-improvement operator that refines learning agents' policies by generating alternative trajectories via stochastic beam search, and treating improved trajectories as targets for imitation learning. Applied to routing problems, their approach matched the performance of imitation learning agents trained on expert demonstrations, highlighting the potential of planning-based methods as a data-efficient alternative to expert supervision in combinatorial optimization.

# 5 Experimental study

We now assess the efficiency of our model-based branching agent, as we aim to answer the following questions:

**Q1** Can PlanB&B learn an efficient policy network to guide MILP solving? In particular, how does it compare against solver heuristics, as well as prior RL and IL approaches?

**Q2** When provided with additional search budget, can our agent further improve the quality of its decisions by leveraging its internal model of B&B?

**Q3** To what extent does the branching behavior of PlanB&B align with that of the expert strong branching (SB) strategy?

**Q4** Is the use of a DFS node selection policy inherently detrimental to the performance of branching agents?

**Benchmarks.** We consider four standard MILP benchmarks: set covering (SC), combinatorial auctions (CA), maximum independent set (MIS) and multiple knapsack (MK) problems. In our experiments, SCIP 8.0.3 (Bestuzheva et al. 2021) is used as backend MILP solver, along with the Ecole library (Prouvost et al. 2020) for instance generation, see Appendix A for further benchmark details.

**Baselines.** We compare our PlanB&B agent against prior RL agents, namely DQN-tMDP (Etheve et al. 2020), PG-tMDP (Scavuzzo et al. 2022) and DQN-Retro (Parsonson et al. 2022). We also compare against the IL expert from Gasse et al. (2019), evaluated under both SCIP's default node selection policy (IL*), and DFS (IL-DFS). More details on these baselines can be found in Appendix G. Finally, we report the performance of reliability pseudo cost branching (SCIP), the default branching heuristic used in 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. SCIP configuration is common to all baselines. As in prior works, 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.

**Training & evaluation.** The overall PlanB&B training pipeline is provided in Appendix F. Branching agents are trained on instances of each benchmark separately. For evaluation, we report performance in terms of both node count and solving time on 100 test instances unseen during training, as well as on 100 transfer instances of higher dimensions. Evaluation metrics are averaged over 5 random seeds. Importantly, when comparing ML-based branching strategies to standard SCIP heuristics such as RPB or SB, solving time remains the only reliable performance indicator. This is because invoking a custom branching rule in SCIP triggers auxiliary routines, such as conflict analysis and bound tightening, that strengthen the MILP formulation while incurring computational overhead.

**Baselines comparison (Q1)** Computational results obtained on the four benchmarks are presented in Table 1. Standard deviations, additional performance metrics as well as targeted ablations are provided in Appendix I. Unlike conventional MBRL settings, PlanB&B operates under strict time and computational constraints. Crucially, every second spent on planning directly increases the overall solving time, thereby impacting final performance. Therefore, to allow systematic comparison, the results reported for PlanB&B in Table 1 reflect the performance of its policy network alone, without any computational budget allocated to MCTS simulations at evaluation time. On aggregate test instances, compared to prior RL baselines, PlanB&B's policy network achieves 2× reductions both in tree size and solving time. This performance gap broadens further to 3×
<table><thead><tr><th rowspan="2">Method</th><th colspan="2">Set Covering</th><th colspan="2">Comb. Auction</th><th colspan="2">Max. Ind. Set</th><th colspan="2">Mult. Knapsack</th><th colspan="4">Norm. Score ± Conf. Interval</th></tr><tr><th>Node</th><th>Time</th><th>Node</th><th>Time</th><th>Node</th><th>Time</th><th>Node</th><th>Time</th><th>Node</th><th>CI</th><th>Time</th><th>CI</th></tr></thead><tbody><tr><td>Presolve</td><td>—</td><td>4.74</td><td>—</td><td>0.90</td><td>—</td><td>1.78</td><td>—</td><td>0.20</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>Random</td><td>3289</td><td>5.94</td><td>1111</td><td>2.16</td><td>386.8</td><td>2.01</td><td>733.5</td><td>0.55</td><td>1068</td><td>±113</td><td>454</td><td>±51</td></tr><tr><td>SB</td><td>35.8</td><td>12.93</td><td>28.2</td><td>6.21</td><td>24.9</td><td>45.87</td><td>161.7</td><td>0.69</td><td>46</td><td>±0</td><td>4279</td><td>±57</td></tr><tr><td>SCIP</td><td>62.0</td><td>2.27</td><td>20.2</td><td>1.77</td><td>19.5</td><td>2.44</td><td>289.5</td><td>0.53</td><td>58</td><td>±0</td><td>363</td><td>±3</td></tr><tr><td>IL<sup>*</sup></td><td><span style="color:red;">133.8</span></td><td>0.90</td><td><span style="color:red;">83.6</span></td><td>0.65</td><td><span style="color:red;">40.1</span></td><td>0.36</td><td>272.0</td><td>0.69</td><td><span style="color:red;">96</span></td><td><span style="color:red;">±17</span></td><td>116</td><td>±15</td></tr><tr><td>IL-DFS</td><td>136.4</td><td><span style="color:red;">0.74</span></td><td>92.1</td><td>0.56</td><td>68.5</td><td>0.44</td><td>411.5</td><td>1.07</td><td>130</td><td>±26</td><td>131</td><td>±20</td></tr><tr><td>PG-tMDP</td><td>649.4</td><td>2.32</td><td>168.0</td><td>0.94</td><td>153.6</td><td>0.92</td><td>436.9</td><td>1.57</td><td>272</td><td>±46</td><td>254</td><td>±50</td></tr><tr><td>DQN-tMDP</td><td><span style="color:blue;">175.8</span></td><td><span style="color:blue;">0.83</span></td><td>203.3</td><td>1.11</td><td>168.0</td><td>1.00</td><td>266.4</td><td>0.73</td><td>207</td><td>±25</td><td>188</td><td>±16</td></tr><tr><td>DQN-Retro</td><td>183.0</td><td>1.14</td><td>103.2</td><td>0.78</td><td>223.0</td><td>1.81</td><td>250.3</td><td>0.67</td><td>208</td><td>±23</td><td>241</td><td>±25</td></tr><tr><td>PlanB&B</td><td>186.2</td><td>0.87</td><td><span style="color:blue;">84.7</span></td><td><span style="color:blue;">0.54</span></td><td><span style="color:blue;">44.8</span></td><td><span style="color:blue;">0.32</span></td><td><span style="color:blue;">220.0</span></td><td><span style="color:blue;">0.55</span></td><td><span style="color:blue;">100</span></td><td><span style="color:blue;">±9</span></td><td><span style="color:blue;">100</span></td><td><span style="color:blue;">±12</span></td></tr></tbody></table>

Test instances

<table><thead><tr><th rowspan="2">Method</th><th colspan="2">Set Covering</th><th colspan="2">Comb. Auction</th><th colspan="2">Max. Ind. Set</th><th colspan="2">Mult. Knapsack</th><th colspan="4">Norm. Score ± Conf. Interval</th></tr><tr><th>Node</th><th>Time</th><th>Node</th><th>Time</th><th>Node</th><th>Time</th><th>Node</th><th>Time</th><th>Node</th><th>CI</th><th>Time</th><th>CI</th></tr></thead><tbody><tr><td>Presolve</td><td>—</td><td>12.3</td><td>—</td><td>2.67</td><td>—</td><td>5.16</td><td>—</td><td>0.46</td><td>—</td><td>—</td><td>—</td><td>—</td></tr><tr><td>Random</td><td>271632</td><td>842</td><td>317235</td><td>749</td><td>215879</td><td>2102</td><td>93452</td><td>70.6</td><td>8050</td><td>±1646</td><td>3870</td><td>±847</td></tr><tr><td>SB</td><td>672.1</td><td>398</td><td>389.6</td><td>255</td><td>169.9</td><td>2172</td><td><span style="color:red;">1709</span></td><td><span style="color:red;">12.5</span></td><td>13</td><td>±0</td><td>2243</td><td>±47</td></tr><tr><td>SCIP</td><td>3309</td><td>48.4</td><td>1376</td><td>14.77</td><td>3368</td><td>90.0</td><td>30620</td><td>22.1</td><td>121</td><td>±0</td><td>132</td><td>±1</td></tr><tr><td>IL<sup>*</sup></td><td><span style="color:red;">2610</span></td><td>23.1</td><td><span style="color:red;">1282</span></td><td>9.4</td><td><span style="color:red;">1993.0</span></td><td><span style="color:red;">38.6</span></td><td>11730</td><td>43.5</td><td><span style="color:red;">70</span></td><td><span style="color:red;">±7</span></td><td><span style="color:red;">83</span></td><td><span style="color:red;">±7</span></td></tr><tr><td>IL-DFS</td><td>3103</td><td><span style="color:red;">22.5</span></td><td>1828</td><td>10.2</td><td>3348</td><td>51.9</td><td>43705</td><td>130.8</td><td>151</td><td>±30</td><td>136</td><td>±21</td></tr><tr><td>PG-tMDP</td><td>44649</td><td>221</td><td>6001</td><td>30.7</td><td>3133</td><td>43.6</td><td>35614</td><td>123</td><td>373</td><td>±48</td><td>290</td><td>±42</td></tr><tr><td>DQN-tMDP</td><td>8632</td><td>71.3</td><td>20553</td><td>116</td><td>45634</td><td>477</td><td>22631</td><td>65.1</td><td>787</td><td>±128</td><td>679</td><td>±78</td></tr><tr><td>DQN-Retro</td><td>6100</td><td>59.4</td><td>2908</td><td>18.4</td><td>119478</td><td>1863</td><td>27077</td><td>79.5</td><td>1166</td><td>±256</td><td>1254</td><td>±218</td></tr><tr><td>PlanB&B</td><td><span style="color:blue;">5869</span></td><td><span style="color:blue;">46.2</span></td><td><span style="color:blue;">1665</span></td><td><span style="color:blue;">9.1</span></td><td><span style="color:blue;">2853</span></td><td><span style="color:blue;">41.1</span></td><td><span style="color:blue;">13574</span></td><td><span style="color:blue;">51.2</span></td><td><span style="color:blue;">100</span></td><td><span style="color:blue;">±9</span></td><td><span style="color:blue;">100</span></td><td><span style="color:blue;">±8</span></td></tr></tbody></table>

Transfer instances

<caption>Table 1: Performance comparison of branching agents on four standard MILP benchmarks. For each method, we report the total number of B&B nodes, presolve time, and total solving time excluding presolve. The presolve phase is identical across all methods. Lower values indicate better performance. Red highlights the overall best agent, while blue marks the best-performing RL-based agent. Following prior work, results are reported as the geometric mean over 100 unseen test instances and an additional 100 higher-dimensional transfer instances, averaged across 5 random seeds. Norm. Score represents the aggregate average performance of each agent across the four MILP benchmarks, normalized by the score of PlanB&B. Aggregate confidence intervals (CI) are reported for each baselines; additional per-benchmark confidence intervals are provided in Appendix I.</caption>

on aggregate transfer instances, underscoring the superior generalization capabilities of PlanB&B relative to prior RL agents. PlanB&B also outperforms the IL-DFS agent on both test and transfer instances, providing, to our knowledge, the first evidence of an RL-based branching strategy surpassing an IL agent trained to mimic strong branching. Specifically, our experiments demonstrate that, under a DFS node selection policy, PlanB&B learns branching strategies superior to that of the IL agent from Gasse et al. (2019). When compared against the standard IL\* baseline, PlanB&B manages to achieve ≈ 10% lower solving time on test instances, despite producing ≈ 5% larger trees in average. However, on transfer instances, PlanB&B is globally unable to overcome the performance limitations imposed by DFS, although it still manages to outperform the IL\* baseline on combinatorial auction. The influence of DFS on the performance of branching agents is further analyzed in (Q4). Finally, PlanB&B clearly outperforms the default SCIP baseline on both test and transfer instances, despite operating under DFS, a performance achieved by no other learning-based baseline.

**Planning in B&B (Q2)** Although PlanB&B demonstrates strong performance while relying solely on its policy network, we further investigate its capacity to derive stronger policies by leveraging its learned model to plan at evaluation time. Figure 4 shows the effect of increasing PlanB&B’s simulation budget *N* on both node and time performance over MIS test and transfer instances. On test instances, PlanB&B achieves lower average tree size than the IL\* baseline as soon as *N* > 12, reaching up to ≈ 20% tree size reduction for *N* = 50. On transfer instances, not only increased simulation budget enables to reduce average tree size up to ≈ 50%, but this reduction also translates into improved solving time performance, with best solving time, achieved at *N* = 9, matching the solving time performance of the IL\* agent. Remarkably, when planning over its internal model, PlanB&B produces branching strategy yielding smaller trees than that produced by the IL\* agent, despite operating under DFS.

**Is PlanB&B learning to strong branch? (Q3)** Given the performance trends observed in Figure 4, a natural question
<figure><img src="image_6.png" /><figcaption>(a) Test instances</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Transfer instances</figcaption></figure>

<caption>Figure 4: Policy improvement associated with increased simulation budget over the MIS benchmark.</caption>

arises: does PlanB&B manage to derive better branching decisions than IL baselines by following SB more closely, or does it discover genuinely novel strategies? After all, strong branching can be interpreted as a one-step MCTS procedure aimed at maximizing immediate dual gap reduction. To answer this, Table 2 reports several alignment metrics designed to assess which of the IL\* and PlanB&B policies more closely resembles strong branching. Across all metrics, PlanB&B policies exhibit lower alignment with SB than IL\* policies. Remarkably, the refined branching policy returned by the MCTS is roughly as close to SB as the policy yielded by the policy network. This suggests that PlanB&B surpasses IL baselines not through closer imitation of strong branching, but by discovering and exploiting original strategies.

**Influence of DFS (Q4)** We finally turn to analyzing the impact of DFS on the performance of branching agents. From Table 1, two key observations emerge. First, the performance gap between DFS and non-DFS variants varies significantly across benchmarks: for instance, MK exhibits a particularly large gap, while SC shows a much narrower one. Second, across all benchmarks, this gap consistently widens as the problem dimensionality increases from test to transfer instances. This trend can be attributed to the typical discovery step $t_d$ at which the B&B algorithm discovers the global optimal solution $x^*$. In fact, as soon as $\bar{x} = x^*$, the primal gap is closed, and, consequently, all node selection policies are equivalent for $t \ge t_d$. Therefore, in theory, the smaller the value of $t_d$, the smaller the performance gap. Table 3

<table><caption>Table 2: Alignment metrics between ML baselines and SB on MIS test and transfer instances. Obviously, SB is perfectly aligned with SB. Experimental setup and thorough metrics description is provided in Appendix I.</caption><thead><tr><th>Instances</th><th>Policy</th><th>Iter.</th><th>(↓) SB C-Entropy</th><th>(↑) SB Score</th><th>(↑) SB Freq.</th></tr></thead><tbody><tr><td></td><td>SB</td><td>—</td><td>0.00</td><td>1.00</td><td>1.00</td></tr><tr><td rowspan="3">Test</td><td>IL<sup>*</sup></td><td>—</td><td>0.84</td><td>0.69</td><td>0.45</td></tr><tr><td>PlanB&B</td><td>0</td><td>1.97</td><td>0.63</td><td>0.39</td></tr><tr><td>PlanB&B</td><td>50</td><td>2.08</td><td>0.65</td><td>0.40</td></tr><tr><td rowspan="3">Transfer</td><td>IL<sup>*</sup></td><td>—</td><td>0.86</td><td>0.76</td><td>0.40</td></tr><tr><td>PlanB&B</td><td>0</td><td>1.46</td><td>0.72</td><td>0.39</td></tr><tr><td>PlanB&B</td><td>50</td><td>1.34</td><td>0.71</td><td>0.38</td></tr></tbody></table>

<table><caption>Table 3: IL\* agent discovery times, with $t_r = t_d/T$ on SC and MIS benchmarks, see Appendix I for further results.</caption><thead><tr><th></th><th>SC Test</th><th>SC Transfer</th><th>MK Test</th><th>MK Transfer</th></tr></thead><tbody><tr><td>t<sub>d</sub></td><td>29</td><td>514</td><td>376</td><td>10934</td></tr><tr><td>t<sub>r</sub></td><td>0.14</td><td>0.25</td><td>1.0</td><td>1.0</td></tr></tbody></table>

reports both absolute and relative average discovery times obtained by IL on SC and MK benchmarks. The results are consistent with our theoretical intuition, see Appendix I for further discussion. Moreover, they highlight a fundamental limitation of applying DFS when solving higher-dimensional MILPs: as problem size grows, closing the primal gap becomes increasingly difficult, which in turn exacerbates the computational burden associated with DFS. To address this issue, future RL contributions need moving beyond the traditional MILP bipartite graph representation and adopt more expressive global representations of the B&B tree, as recently proposed by Zhang et al. (2025).

# 6 Conclusion and perspectives

Combinatorial optimization has proven in the past to be a challenging setting for traditional RL approaches. In this work, we introduced PlanB&B, a novel model-based reinforcement learning framework leveraging a learned internal model of B&B to discover new variable selection strategies. Our experimental study leads to three main findings. First, PlanB&B's dynamics network approximates LP resolution in the latent space with sufficient fidelity to enable policy improvement through model-based planning, thereby extending the applicability of MBRL algorithms originally developed for combinatorial board games to mixed-integer linear programming. Second, in the context of repeated MILPs, our MBRL agent learns branching strategies that clearly outperform both SCIP and former RL baselines. Moreover, further analysis shows instances where PlanB&B surpasses IL, not by more closely replicating expert behavior, but by actively diverging from strong branching patterns, highlighting the potential of RL to uncover branching strategies going beyond existing expert heuristics. Third and finally, our computational study highlights the burden imposed by the DFS node selection policy when seeking to solve higher-dimensional
MILPs. In order to fully unlock the potential of MBRL in exact combinatorial optimization, we expect future research to explore the design of scalable observation functions capable of efficiently encoding evolving B&B trees.

## References

Achterberg, T.; and Wunderling, R. 2013. Mixed integer programming: Analyzing 12 years of progress. In *Facets of combinatorial optimization: Festschrift for martin grötschel*, 449–481. Springer.

Applegate, D.; Bixby, R.; Chvátal, V.; and Cook, W. 1995. *Finding cuts in the TSP (A preliminary report)*, volume 95. Citeseer.

Balas, E.; and Ho, A. 1980. Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. *Combinatorial Optimization*, 37–60.

Bergman, D.; Cire, A. A.; Van Hoeve, W.-J.; and Hooker, J. 2016. *Decision diagrams for optimization*, volume 1. Springer.

Berto, F.; Hua, C.; Park, J.; Kim, M.; Kim, H.; Son, J.; Kim, H.; Kim, J.; and Park, J. 2023. RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark. ArXiv:2306.17100 [cs].

Bestuzheva, K.; Besançon, M.; Chen, W.-K.; Chmiela, A.; Donkiewicz, T.; Doornmalen, J. v.; Eifler, L.; Gaul, O.; Gamrath, G.; Gleixner, A.; Gottwald, L.; Graczyk, C.; Halbig, K.; Hoen, A.; Hojny, C.; Hulst, R. v. d.; Koch, T.; Lübbecke, M.; Maher, S. J.; Matter, F.; Mühmer, E.; Müller, B.; Pfetsch, M. E.; Rehfeldt, D.; Schlein, S.; Schlösser, F.; Serrano, F.; Shinano, Y.; Sofranac, B.; Turner, M.; Vigerske, S.; Wegscheider, F.; Wellner, P.; Weninger, D.; and Witzig, J. 2021. The SCIP Optimization Suite 8.0. Technical Report, Optimization Online.

Bixby, R. E. 2012. A brief history of linear and mixed-integer programming computation. *Documenta Mathematica*, 2012: 107–121.

Chalumeau, F.; Surana, S.; Bonnet, C.; Grinsztajn, N.; Pretorius, A.; Laterre, A.; and Barrett, T. 2023. Combinatorial optimization with policy adaptation using latent space search. *Advances in Neural Information Processing Systems*, 36: 7947–7959.

Chen, X.; and He, K. 2020. Exploring Simple Siamese Representation Learning. ArXiv:2011.10566 [cs].

Danihelka, I.; Guez, A.; Schrittwieser, J.; and Silver, D. 2022. Policy improvement by planning with Gumbel. In *International Conference on Learning Representations*.

Dey, S. S.; Dubey, Y.; Molinaro, M.; and Shah, P. 2021. A Theoretical and Computational Analysis of Full Strong-Branching. ArXiv:2110.10754 [math].

Etheve, M. 2021. *Solving repeated optimization problems by Machine Learning*. phdthesis, HESAM Université.

Etheve, M.; Alès, Z.; Bissuel, C.; Juan, O.; and Kedad-Sidhoum, S. 2020. Reinforcement Learning for Variable Selection in a Branch and Bound Algorithm. In Hebrard,

E.; and Musliu, N., eds., *Integration of Constraint Programming, Artificial Intelligence, and Operations Research*, Lecture Notes in Computer Science, 176–185. Cham: Springer International Publishing. ISBN 978-3-030-58942-4.

Farebrother, J.; Orbay, J.; Vuong, Q.; Taïga, A. A.; Chebotar, Y.; Xiao, T.; Irpan, A.; Levine, S.; Castro, P. S.; Faust, A.; Kumar, A.; and Agarwal, R. 2024. Stop Regressing: Training Value Functions via Classification for Scalable Deep RL. ArXiv:2403.03950 [cs, stat].

Fukunaga, A. S. 2011. A branch-and-bound algorithm for hard multiple knapsack problems. *Annals of Operations Research*, 184(1): 97–119.

Gasse, M.; Chetelat, D.; Ferroni, N.; Charlin, L.; and Lodi, A. 2019. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. In *Advances in Neural Information Processing Systems*, volume 32. Curran Associates, Inc.

Gleixner, A.; Hendel, G.; Gamrath, G.; Achterberg, T.; Bas-tubbe, M.; Berthold, T.; Christophel, P.; Jarck, K.; Koch, T.; and Linderoth, J. 2021. MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. *Mathematical Programming Computation*, 13(3): 443–490. Publisher: Springer.

Gusfield, D. 2019. *Integer linear programming in computational and systems biology: an entry-level text and course*. Cambridge University Press.

Hansen, N.; Su, H.; and Wang, X. 2023. Td-mpc2: Scalable, robust world models for continuous control. *arXiv preprint arXiv:2310.16828*.

He, H.; Daume III, H.; and Eisner, J. M. 2014. Learning to Search in Branch and Bound Algorithms. In *Advances in Neural Information Processing Systems*, volume 27. Curran Associates, Inc.

Hillier, F. S.; and Lieberman, G. J. 2015. *Introduction to operations research*. McGraw-Hill.

Imani, E.; and White, M. 2018. Improving Regression Performance with Distributional Losses. In *Proceedings of the 35th International Conference on Machine Learning*, 2157–2166. PMLR. ISSN: 2640-3498.

Karnin, Z.; Koren, T.; and Somekh, O. 2013. Almost optimal exploration in multi-armed bandits. In *International conference on machine learning*, 1238–1246. PMLR.

Kool, W.; van Hoof, H.; and Welling, M. 2019. Attention, Learn to Solve Routing Problems! ArXiv:1803.08475 [cs, stat].

Kool, W.; Van Hoof, H.; and Welling, M. 2019. Stochastic beams and where to find them: The gumbel-top-k trick for sampling sequences without replacement. In *International Conference on Machine Learning*, 3499–3508. PMLR.

Land, A.; and Doig, A. 1960. An Automatic Method of Solving Discrete Programming Problems. *Econometrica*, 28(3): 497–520.

Leyton-Brown, K.; Pearson, M.; and Shoham, Y. 2000. Towards a universal test suite for combinatorial auction algorithms. In *Proceedings of the 2nd ACM conference on Electronic commerce*, 66–76.
Lin, J.; Zhu, J.; Wang, H.; and Zhang, T. 2022. Learning to branch with Tree-aware Branching Transformers. *Knowledge-Based Systems*, 252: 109455.

Liu, H.; Kuang, Y.; Wang, J.; Li, X.; Zhang, Y.; and Wu, F. 2023. Promoting Generalization for Exact Solvers via Adversarial Instance Augmentation. ArXiv:2310.14161 [cs].
Mansini, R.; Ogryczak, W.; Speranza, M. G.; and of European Operational Research Societies, E. T. A. 2015. *Linear and mixed integer programming for portfolio optimization*, volume 21. Springer.

Nair, V.; Bartunov, S.; Gimeno, F.; von Glehn, I.; Lichocki, P.; Lobov, I.; O'Donoghue, B.; Sonnerat, N.; Tjandraatmadja, C.; Wang, P.; Addanki, R.; Hapuarachchi, T.; Keck, T.; Keeling, J.; Kohli, P.; Ktena, I.; Li, Y.; Vinyals, O.; and Zwols, Y. 2021. Solving Mixed Integer Programs Using Neural Networks. ArXiv:2012.13349 [cs, math].

Parsonson, C. W. F.; Laterre, A.; Barrett, T. D.; Doe, J.; and Doe, J. 2022. Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories. ArXiv:2205.14345 [cs].

Paulus, M. B.; Zarpellon, G.; Krause, A.; Charlin, L.; and Maddison, C. 2022. Learning to Cut by Looking Ahead: Cutting Plane Selection via Imitation Learning. In *Proceedings of the 39th International Conference on Machine Learning*, 17584–17600. PMLR. ISSN: 2640-3498.

Pirnay, J.; and Grimm, D. G. 2024. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. *arXiv preprint arXiv:2403.15180*.

Prouvost, A.; Dumouchelle, J.; Scavuzzo, L.; Gasse, M.; Chételat, D.; and Lodi, A. 2020. Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers. ArXiv:2011.06069 [cs, math].

Qian, C.; Chételat, D.; and Morris, C. 2023. Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems. ArXiv:2310.10603 [cs, math, stat].

Scavuzzo, L.; Aardal, K.; Lodi, A.; and Yorke-Smith, N. 2024. Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming. ArXiv:2402.05501 [cs, math].

Scavuzzo, L.; Chen, F. Y.; Chételat, D.; Gasse, M.; Lodi, A.; Yorke-Smith, N.; and Aardal, K. 2022. Learning to branch with Tree MDPs. ArXiv:2205.11107 [cs, math].

Schrittwieser, J.; Antonoglou, I.; Hubert, T.; Simonyan, K.; Sifre, L.; Schmitt, S.; Guez, A.; Lockhart, E.; Hassabis, D.; Graepel, T.; Lillicrap, T.; and Silver, D. 2020. Mastering Atari, Go, chess and shogi by planning with a learned model. *Nature*, 588(7839): 604–609. Number: 7839 Publisher: Nature Publishing Group.

Seyfi, M.; Banitalebi-Dehkordi, A.; Zhou, Z.; and Zhang, Y. 2023. Exact Combinatorial Optimization with Temporal-Attentional Graph Neural Networks. ArXiv:2311.13843 [cs]. Silver, D.; Hubert, T.; Schrittwieser, J.; Antonoglou, I.; Lai, M.; Guez, A.; Lanctot, M.; Sifre, L.; Kumaran, D.; Graepel, T.; Lillicrap, T.; Simonyan, K.; and Hassabis, D. 2018. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. *Science*, 362(6419): 1140–1144.

Sonnerat, N.; Wang, P.; Ktena, I.; Bartunov, S.; and Nair, V. 2022. Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs. ArXiv:2107.10201 [cs, math].

Tang, Y.; Agrawal, S.; and Faenza, Y. 2020. Reinforcement Learning for Integer Programming: Learning to Cut. In *Proceedings of the 37th International Conference on Machine Learning*, 9367–9376. PMLR. ISSN: 2640-3498.

Wang, S.; Liu, S.; Ye, W.; You, J.; and Gao, Y. 2024. Efficient Zero V2: Mastering Discrete and Continuous Control with Limited Data. In *International Conference on Machine Learning*, 51041–51062. PMLR.

Wang, Z.; Li, X.; Wang, J.; Kuang, Y.; Yuan, M.; Zeng, J.; Zhang, Y.; and Wu, F. 2023. Learning cut selection for mixed-integer linear programming via hierarchical sequence model. *arXiv preprint arXiv:2302.00244*.

Wu, D.; and Lisser, A. 2023. A deep learning approach for solving linear programming problems. *Neurocomputing*, 520: 15–24.

Ye, W.; Liu, S.; Kurutach, T.; Abbeel, P.; and Gao, Y. 2021. Mastering Atari Games with Limited Data. ArXiv:2111.00210 [cs].

Zhang, S.; Zeng, S.; Li, S.; Wu, F.; and Li, X. 2025. Learning to Select Nodes in Branch and Bound with Sufficient Tree Representation. In *The Thirteenth International Conference on Learning Representations*.
## A Instance dataset

Instance datasets used for training and evaluation are described 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 $\mathcal{A}$ is equal to the number of integer variables in $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.

## B Model architecture

In this section, we formally describe the overall architecture and prediction mechanism of the model introduced in Section 3.

**State representation** Following the works of Gasse et al. (2019), MILPs are best represented by bipartite graphs $\mathcal{G} = (\mathcal{V}_G, \mathcal{C}_G, \mathcal{E}_G)$ where $\mathcal{V}_G$ denotes the set of variable nodes, $\mathcal{C}_G$ denotes the set of constraint nodes, and $\mathcal{E}_G$ denotes the set of edges linking variable and constraints nodes. Nodes $v_G \in \mathcal{V}_G$ and $c_G \in \mathcal{C}_G$ are connected through the edge $\epsilon_G \in \mathcal{E}_G$ if and only if the variable associated with $v_G$ appears in the constraint associated with $c_G$. We note respectively $d_v, d_c, d_e$ the input dimension of variable nodes, constraint nodes and edges. Bipartite graphs can be thus interpreted as vectors from the observation space $\mathcal{M} = \mathbb{R}^{n \times d_v} \times \mathbb{R}^{m \times d_c} \times \mathbb{R}^{n \times m \times d_e}$. In our experiments, IL and PG-tMDP agents use the list of features of Gasse et al. (2019) to represent variable nodes, constraint nodes and edges, while PlanB&B, DQN-TreeMDP and DQN-Retro agents also make use of the additional features introduced by Parsonson et al. (2022).

**Representation network** The representation network $h: \mathcal{M} \to \mathbb{R}^{n \times d_h} \times \mathbb{R}^{m \times d_h} \times \mathbb{R}^{n \times m \times d_h}$, maps graph bipartite observations to a triplet of embeddings vectors of higher dimension $d_h$. It is composed of three fully-connected modules: the variable encoder $e_v$, the constraint encoder $e_c$ and the edge encoder $e_e$, which independently compute initial embeddings for the corresponding components. In the following, we note $\mathcal{H} = \mathbb{R}^{n \times d_h} \times \mathbb{R}^{m \times d_h} \times \mathbb{R}^{n \times m \times d_h}$ the latent space associated with internal representations.

**Prediction network** The prediction network $f$ consists of a shared convolutional core followed by three output heads $\mathbf{p}, \bar{\mathbf{p}}, \mathbf{b}$, which maps internal representations $\hat{o} \in \mathcal{H}$ to their estimated policy, subtree value and branchability score respectively. In order to enhance its generalization capacity to higher-dimensionnal MILP instances with higher associated tree size, the value network represents subtree values as histogram distributions over the support of the value function. Crucially, histogram distributions outputed by $\bar{\mathbf{v}}$ can be transformed back and forth into scalar values using the HL-Gauss transform operators introduced in Appendix H.

We now describe the overall architecture of the prediction network. The shared core comprises two graph convolutional layers $\mathcal{G}_{v \to c}^f: \mathcal{H} \to \mathcal{H}$ and $\mathcal{G}_{c \to v}^f: \mathcal{H} \to \mathcal{H}$ followed by an output module $\mathbf{o}_m: \mathcal{H} \to \mathbb{R}^{n \times d_h}$. This module consists in two fully connected layers followed by non-linear activations. Finally, the three output heads are computed by dedicated linear networks: $\mathbf{o}_v: \mathbb{R}^{n \times d_h} \to \mathbb{R}^{m_b}, \mathbf{o}_p: \mathbb{R}^{n \times d_h} \to \mathbb{R}^n, \mathbf{o}_b:

$\mathbb{R}^{n \times d_h} \to \mathbb{R}^2$ which produce the final predictions from the shared feature representation:

$$ \mathbf{p}: \left\{ \begin{array}{l} \mathcal{H} \to \mathbb{R}^{m_b} \\ \mathbf{p}(\mathbf{x}) = \mathbf{o}_p \circ \mathbf{o}_m \circ \mathcal{G}_{c \to v}^f \circ \mathcal{G}_{v \to c}^f(\mathbf{x}) \end{array} \right. $$

$$ \bar{\mathbf{v}}: \left\{ \begin{array}{l} \mathcal{H} \to \mathbb{R} \\ \bar{\mathbf{v}}(\mathbf{x}) = \text{pool} \circ \mathbf{o}_v \circ \mathbf{o}_m \circ \mathcal{G}_{c \to v}^f \circ \mathcal{G}_{v \to c}^f(\mathbf{x}) \end{array} \right. $$

$$ \mathbf{b}: \left\{ \begin{array}{l} \mathcal{H} \to \mathbb{R}^2 \\ \mathbf{b}(\mathbf{x}) = \text{pool} \circ \mathbf{o}_b \circ \mathbf{o}_m \circ \mathcal{G}_{c \to v}^f \circ \mathcal{G}_{v \to c}^f(\mathbf{x}) \end{array} \right. $$

where $\text{pool}(\cdot)$ designates the mean pooling operation and $m_b$ the number of bins used to partition the support of the value function, see Appendix H for more details.

**Dynamics network** In MBRL, the agent has reversible access to the environment's dynamics $(\mathcal{T}, \mathcal{R})$, either through a simulator or a learned model. This constitutes one of the main differences between AlphaZero (Silver et al. 2018) and MuZero (Schrittwieser et al. 2020): in AlphaZero, the model consists in a perfect board game simulator, whereas in MuZero the model is a neural network $g$ trained jointly with the prediction network $f$. As described in Section 2, our setting adopts a constant reward function $\mathcal{R} = -1$ and a deterministic transition function $\mathcal{T} = \kappa_{\rho}$ which boils down to the composition of the branching operation $\kappa$, and the node selection policy $\rho$, such that $\kappa_{\rho} = \kappa \circ \rho$. In this work, we adopt an hybrid approach between AlphaZero and MuZero: we train $g$ to replicate the branching operation $\kappa$ and we simulate $\rho = \text{DFS}$, such that our overall B&B model is part learned and part simulation.

Our dynamic network $g$ comprises two independent heads $\mathbf{g}^l$ and $\mathbf{g}^r$ dedicated respectively to the left and right child nodes. In our convention, the left node is the node first visited by the DFS node selection policy, while the right node is the node visited once its sibling node's subtree has been fathomed. We describe the architecture of $\mathbf{g}^l$, which is identical to the one of $\mathbf{g}^r$. The $\mathbf{g}^l$ module is composed of an action embedding module $\mathbf{e}_a^l$, two graph convolutional layers $\mathcal{G}_{v \to c}^l, \mathcal{G}_{c \to v}^l$ and an output module $\mathbf{o}_g^l$. The action embedding module $\mathbf{e}_a^l: \mathcal{H} \times \mathcal{A} \to \mathcal{H}$ only transforms the representation of the variable node in the bipartite graph corresponding to the variable $a$, by feeding it to a 2-layer fully connected neural network. The output of $\mathbf{e}_a^l$ is fed to the convolutional block $\mathcal{G}_{v \to c}^l, \mathcal{G}_{c \to v}^l$, and in turn to the output module $\mathbf{o}_g^l: \mathcal{H}^2 \to \mathcal{H}$, which is also connected to the output of $\mathbf{e}_a^l$ through a residual link. The dynamic network does not predict rewards, although such functionality could be easily added if one wishes to experiment with alternative reward models. Finally $g$ can be summarized as:

$$ \mathbf{g}^l: \left\{ \begin{array}{l} \mathcal{H} \times \mathcal{A} \to \mathcal{H} \\ \mathbf{g}^l(\mathbf{x}) = \mathbf{o}_g^l \circ (\mathbf{Id} + \mathcal{G}_{c \to v}^l \circ \mathcal{G}_{v \to c}^l) \circ \mathbf{e}_a^l(\mathbf{x}) \end{array} \right. $$

$$ \mathbf{g}^r: \left\{ \begin{array}{l} \mathcal{H} \times \mathcal{A} \to \mathcal{H} \\ \mathbf{g}^r(\mathbf{x}) = \mathbf{o}_g^r \circ (\mathbf{Id} + \mathcal{G}_{c \to v}^r \circ \mathcal{G}_{v \to c}^r) \circ \mathbf{e}_a^r(\mathbf{x}) \end{array} \right. $$

**Simulating subtree trajectories** Let $\hat{o} \in \mathcal{H}$ be the internal representation of the B&B current node $o = \rho(s_t)$
<table><caption>Table 4: Instance size for each benchmark. Performance is evaluated on test 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.</caption><thead><tr><th rowspan="2">Benchmark</th><th rowspan="2">Generation method</th><th rowspan="2">Parameters</th><th colspan="2">Parameter value</th><th colspan="2"># Int. variables</th></tr><tr><th>Train / Test</th><th>Transfer</th><th>Train / Test</th><th>Transfer</th></tr></thead><tbody><tr><td rowspan="2">Combinatorial auction</td><td rowspan="2">Leyton-Brown, Pearson, and Shoham (2000)</td><td>Items</td><td>100</td><td>200</td><td rowspan="2">100</td><td rowspan="2">200</td></tr><tr><td>Bids</td><td>500</td><td>1000</td></tr><tr><td rowspan="2">Set covering</td><td rowspan="2">Balas and Ho (1980)</td><td>Items</td><td>500</td><td>1000</td><td rowspan="2">100</td><td rowspan="2">130</td></tr><tr><td>Sets</td><td>1000</td><td>1000</td></tr><tr><td>Maximum independent set</td><td>Bergman et al. (2016)</td><td>Nodes</td><td>500</td><td>1000</td><td>480</td><td>980</td></tr><tr><td rowspan="2">Multiple knapsack</td><td rowspan="2">Fukunaga (2011)</td><td>Items</td><td>100</td><td>100</td><td rowspan="2">30</td><td rowspan="2">50</td></tr><tr><td>Knapsacks</td><td>6</td><td>12</td></tr></tbody></table>

and let $a \in A$ be an action to perform. The dynamics network $g$ generates $\hat{o}_l, \hat{o}_r$ the internal representations of the two child nodes created when branching on variable $a$ at $s_t$: $\hat{o}_l, \hat{o}_r = g(\hat{o}, a)$. The policy, subtree value and branchability associated with $\hat{o}_l, \hat{o}_r$ are computed using the prediction network: $p_{\hat{o}_l}, \bar{v}_{\hat{o}_l}, b_{\hat{o}_l} = f(\hat{o}_l); p_{\hat{o}_r}, \bar{v}_{\hat{o}_r}, b_{\hat{o}_r} = f(\hat{o}_r)$. Then, the two child nodes are added to the imagined tree $\hat{T} = \{\hat{O}, \hat{C}\}$ based on their predicted branchability. Unsurprisingly, if $\hat{o}_i \in \{\hat{o}_l, \hat{o}_r\}$ is predicted to be branchable, it is added to the set of imagines open nodes $\hat{O}$, otherwise, it is added to the set of imagined closed nodes $\hat{C}$. Crucially, the predictions $p_{\hat{o}_i}, \bar{v}_{\hat{o}_i}, b_{\hat{o}_i}$ are stored in $\hat{T}$ along with $\hat{o}_i$ to enable future computations of the imagined tree's associated policy and state value. For example, let $\hat{T}^k = (\hat{O}^k, \hat{C}^k)$ be the imagined subtree obtained after unrolling the PlanB&B model for $k$ step from $s_t$. Our node selection policy simulator selects the next node to expand $\bar{o} = \rho(\hat{O}^k)$ as the node in $\hat{O}^k$ with the greatest depth. In case of equality, the next current node is the left most node in $\hat{O}$ with highest depth. This way, our model is compatible with any DFS priority criterion discriminating between nodes of equal depth. As highlighted in Section 3, the estimate policy $\hat{p}_t^k$ and state value $\hat{v}_t^k$ associated with $\hat{T}^k$ can be retrieved from $\hat{O}^k$ through the formulas: $\hat{p}_t^k = p_{\bar{o}}$; $\hat{v}_t^k = \sum_{\bar{o} \in \hat{O}^k} \bar{v}_{\bar{o}}$. To simplify notations, in the following sections we abusively write $\hat{p}_t^k, \hat{v}_t^k = f(\hat{T}^k)$ and $\hat{T}^{k+1} = g(\hat{T}^k, a)$ to summarize the global interaction between $f$ and $g$ to simulate subtree trajectories.

## C Search

We describe the planning algorithm used in PlanB&B. Our approach builds on Gumbel Search, a variant of Monte Carlo Tree Search (MCTS) that provides stronger policy improvement guarantees, particularly in settings with limited simulation budgets. In PlanB&B, every node of the search tree is associated with an imagined B&B subtree $\hat{T}$ rooted in the current B&B node $o = \rho(s_t)$. For each action $a \in A$ available at node $\hat{T}$, there is a corresponding edge storing the statistics $N(\hat{T}, a), Q(\hat{T}, a), P(\hat{T}, a)$ respectively representing the visit count, normalized Q-value and policy prior

associated with the pair $(\hat{T}, a)$. As in MCTS, the search algorithm is divided in three stages: path selection, search tree expansion and value backpropagation, repeated for a number $N$ of simulations. In Gumbel search, only the path selection procedure differs from traditional MCTS implementations.

**Selection** Each simulation consists in a path $(a^1, \dots, a^l)$ starting from the root of the search tree, represented by the initial subtree $\hat{T}^0 = (\mathcal{O}^0, \mathcal{C}^0)$ where $\mathcal{O}^0 = \{\hat{o}\}$ and $\mathcal{C}^0 = \emptyset$, and diving towards a leaf node $\hat{T}^l$ that is yet to be expanded. To generate such paths, Gumbel Search uses two different types of selection criterion for choosing $a^k$ for $k = 1 \dots l$, depending on whether $\hat{T}^{k-1}$ correspond to the root of the search tree or to a deeper node. In fact, as emphasized by Danihelka et al. (2022), since the goal is to derive a policy improvement procedure via planning, the search algorithm should aim not to minimize cumulative regret over the $N$ simulations, as is the case in traditional MCTS implementations, but rather the simple regret associated with the action selected at the root of the search tree at iteration $N+1$. Accordingly, at the root node, our search algorithm employs the Sequential Halving procedure (Karnin, Koren, and Somekh 2013) in combination with the Gumbel-Top-k trick (Kool, Van Hoof, and Welling 2019), as described by Danihelka et al. (2022), to efficiently sample a promising subset of $M < |A|$ actions for exploration. This procedure is particularly well suited to the MILP setting, as it preserves the policy improvement property even when the available simulation budget is small relative to the size of the action set. In contrast, beyond root node, $a^k$ is simply selected as :

$$a^k = \arg \max_{a \in A} \left( \pi'(\hat{T}^{k-1}, a) - \frac{N(\hat{T}^{k-1}, a)}{1 + \sum_{b \in A} N(\hat{T}^{k-1}, b)} \right)$$

where $\pi'(\hat{T}^{k-1}, a)$ is a function of $Q(\hat{T}^{k-1}, a)$ and $P(\hat{T}^{k-1}, a)$ introduced in the next paragraphs.

**Expansion** At the final step of the simulation, upon reaching the unvisited edge $(\hat{T}^{l-1}, a^l)$, the transition $\hat{T}^l = g(\hat{T}^{l-1}, a^l)$ is computed by applying the dynamics network.
The policy and value estimates for $\hat{T}^l$ are then obtained via the prediction network such that $\hat{p}^l, \hat{v}^l = f(\hat{T}^l)$. The search tree is subsequently expanded by initializing each outgoing edge $(\hat{T}^l, a)$ with the statistics: $\{N(\hat{T}^l, a) = 0, Q(\hat{T}^l, a) = 0, P(\hat{T}^l, a) = \hat{p}^l\}$. Importantly, each simulation requires a single call to the dynamics function, and two calls to the prediction network.

**Backpropagation** Once the search tree is expanded, the statistics $N$ and $Q$ are updated along the simulation path, starting from $\hat{T}^l$. For $k = l...1$, noting $G^k = -(l-k) + \hat{v}^l$, each edge $(\hat{T}^{k-1}, a^k)$ is updated following:

$$Q(\hat{T}^{k-1}, a^k) := \frac{N(\hat{T}^{k-1}, a^k) \cdot Q(\hat{T}^{k-1}, a^k) + G^k}{N(\hat{T}^{k-1}, a^k) + 1}$$

$$N(\hat{T}^{k-1}, a^k) := N(\hat{T}^{k-1}, a^k) + 1$$

**Improved policy target** After completing $N$ simulation steps, an improved policy target $\pi_t$ is computed from the statistics accumulated at the root of the search tree, such that $\pi_t(a) = \pi'(\hat{T}^0, a)$ for $a \in A$, with $\pi'$ defined as:

$$\pi'(\hat{T}^k, a) = \mathrm{softmax}(P(\hat{T}^k, a) + \sigma(\tilde{Q}(\hat{T}^k, a))).$$

with $\sigma(\tilde{Q}(\hat{T}^k, a))) = (c_{visit} + \max_{b \in A} N(\hat{T}^k, b)) \cdot c_{scale} \cdot \tilde{Q}(\hat{T}^k, a))$. In turn, $\tilde{Q}(\hat{T}^k, a))$ is defined as:

$$\tilde{Q}(\hat{T}^k, a) = \begin{cases} Q(\hat{T}^k, a) & \text{if } N(\hat{T}^k, a) > 0 \\ \sum P(\hat{T}^k, a) \cdot Q(\hat{T}^k, a) & \text{else.} \end{cases}$$

Similar to the policy targets generated by standard MCTS procedures, the improved Gumbel Search policies achieve a trade-off between exploration and exploitation to guide action selection. Importantly, as in MuZero, the $Q$-value statistics used to balance exploration and exploitation are in fact normalized values $Q^\dagger \in [0, 1]$, computed using a simple normalization scheme applied across the search tree:

$$Q^\dagger(\hat{T}^{k-1}, a^k) = \frac{Q(\hat{T}^{k-1}, a^k) - \min_{(\hat{T}, a) \in \text{Tree}} Q(\hat{T}, a)}{\max_{(\hat{T}, a) \in \text{Tree}} Q(\hat{T}, a) - \min_{(\hat{T}, a) \in \text{Tree}} Q(\hat{T}, a)}$$

## D Strong Branching

In this section, we present strong branching (SB), the branching expert used in Gasse et al. (2019), and show how it can be reformulated as a MCTS procedure when considering a dual bound maximization objective.

**Strong branching** Among the various branching heuristics proposed in the literature, strong branching stands out as one of the most powerful and effective, albeit computationally expensive, techniques. The core idea of SB is to simulate the effect of branching on several candidate variables before actually committing to a decision. This is achieved by tentatively imposing the two branching disjunctions associated

with each candidate variable (e.g., $x_i \le \lfloor \hat{x}_i \rfloor$ and $x_i \ge \lceil \hat{x}_i \rceil$ for fractional variable $x_i$) and solving the corresponding child nodes' LP relaxations to obtain dual bounds. The SB score of a variable is typically based on the estimated dual bound improvement, that is, how much the LP relaxation's objective increases under each branching direction. Intuitively, a variable is promising for branching if both child nodes yield significantly higher associated dual bounds $c^T x_{LP}^*$ than the current node, indicating that branching on this variable may help prune the search tree more effectively. Mathematically, for a candidate variable $x_i$, let $\Delta_l^i$ and $\Delta_r^i$ denote the increases in the LP relaxation objective value under the left and right branch respectively. A common scoring function for SB writes score($x_i$) = min($\Delta_l^i, \Delta_r^i$). Such scoring schemes aim to identify variables that exhibit balanced improvement in both branches, thus maximizing the likelihood of early node fathoming.

Despite its effectiveness in reducing the size of generated B&B trees, the primary drawback of strong branching is its computational overhead. At each node, it requires solving potentially hundreds of LPs, one for each branching direction of every fractional variable, which quickly becomes prohibitive even for medium-scale MILPs. As a result, modern solvers typically reserve strong branching for early tree nodes or use it in hybrid strategies, where a small number of variables are pre-selected based on cheaper scoring functions, and S is applied selectively. In recent years, S has also served as a supervised learning target for data-driven branching strategies. Due to its high computational cost but high accuracy, its decisions provide a valuable signal for training imitation learning models that seek to replicate expert decisions at a fraction of the computational expense (Gasse et al. 2019). In summary, strong branching represents a gold standard for variable selection in B&B, as it produces best known expert branching decisions. Its study continues to inform both theoretical analyses of B&B efficiency and the design of advanced branching heuristics, including those based on learning.

**Strong Branching as Lookahead Planning** Strong branching can be naturally interpreted as a one-step Monte Carlo Tree Search (MCTS) procedure aimed at maximizing the dual bound. In this perspective, the current B&B node corresponds to the root of the search tree, and each candidate variable $x_i$ defines a branching action $a_i$ leading to a leaf node associated with an expanded B&B tree. For each action $a_i$, strong branching simulates both branches by solving the LP relaxations of the left and right child nodes, thus obtaining dual bounds $z_l^i$ and $z_r^i$. The aggregated score score($x_i$) = min($z_l^i, z_r^i$) serves as an estimate of the value of the branching decision $a_i$, and is propagated back to the root of the search tree to guide variable selection.

Crucially, strong branching differs from traditional MCTS in that it performs a full-width, depth-one expansion of all available actions without search tree rollouts or simulations. It estimates action quality based purely on immediate lookahead, and selects the action with the best estimated dual bound improvement. This can be interpreted as an extremely expensive form of planning under a one-step horizon, where the dynamics model is replaced by LP solvers, and the value
function corresponds to the dual bound improvement. In this light, strong branching serves as a handcrafted, domain-specific instantiation of value-based planning, motivating the exploration of more general model-based planning approaches for improving variable selection in B&B.

## E Learning

We describe the overall training mechanism of PlanB&B. Crucially, PlanB&B is trained over K-step subtree trajectories ($s_t, a_t, ..., s_{t+K}$). As illustrated in Figure 3, the PlanB&B model is unrolled along the same action sequence as the historical sampled trajectory, generating a sequence of imagined subtrees ($\hat{T}^0, ..., \hat{T}^K$). Along these subtree trajectories, the policy network $\mathbf{p}$ is trained to replicate $\pi_{t+k}$ the policy outputed by the search algorithm, while the subtree value network $\bar{\mathbf{v}}$ is trained to match $z_{t+k}$, the n-step return target. As in MuZero, our value network is trained via classification, using the HL-Gauss loss introduced in Appendix H. Moreover, in PlanB&B the branchability network $\mathbf{b}$ is trained to discriminate between branchable and unbranchable nodes. Losses used to train each network are described by the following equations:

$$ 
\begin{aligned}
\hat{\mathbf{p}}_t^k &= \{\mathbf{p}_{\hat{o}} | \hat{o} = \rho(\hat{O}^k)\} \\
\hat{\mathbf{v}}_t^k &= \sum_{\hat{o} \in \hat{O}^k} \bar{\mathbf{v}}_{\hat{o}} \\
\pi_{t+k} &= \text{Gumbel}(s_{t+k}, h, f, g; \theta) \\
z_{t+k} &= -n + \hat{\mathbf{v}}_t^{k+n} \\
\mathcal{L}_{\text{p}}(\pi, \hat{\mathbf{p}}) &= \pi^\top \log \hat{\mathbf{p}} \\
\mathcal{L}_{\text{v}}(z, \hat{\mathbf{v}}) &= z^\top \log \hat{\mathbf{v}} \\
\mathcal{L}_{\text{b}}(b, \hat{\mathbf{b}}) &= b^\top \log \hat{\mathbf{b}}
\end{aligned}
$$

**Tree consistency loss** Following Ye et al. (2021), we introduce a new self-supervised loss $\mathcal{L}_t$ to enforce tree consistency between consecutive internal B&B node representations. Let $\hat{o} \in \mathcal{H}$ be the internal representation associated with $o = \rho(s_t)$ the current B&B node. By definition, $\hat{o} = h(o, \bar{x}_t)$. When feeding $\hat{o}$ to the dynamics network $g$ along with $a_t$, we obtain $\hat{o}_l, \hat{o}_r$, the internal representation of the child nodes associated with branching on $a_t$ at $s_t$. Let us write $\tau_l, \tau_r$ the time steps at which the real nodes $o_l, o_r$ associated with $\hat{o}_l, \hat{o}_r$ are visited. Provided that these time steps are finite, we can compute the latent representation targets $h(o_l, \bar{x}_{\tau_l}), h(o_r, \bar{x}_{\tau_r}) \in \mathcal{H}$ for $\hat{o}_l$ and $\hat{o}_r$. Otherwise, $o_i$ is unbranchable, in that case we refrain from enforcing tree consistency.

Our self-supervised loss $\mathcal{L}_t$ takes inspiration from the SimSiam architecture from Chen and He (2020). Let $\hat{o} \in \mathcal{H}$ be the internal representation of node $o \in \mathcal{O}_{t+k}$ obtained after unrolling the PlanB&B model for $k$ steps, and let $\hat{o} \in \mathcal{H}$ be its associated target representation as defined in the previous paragraph. As illustrated in Figure 5, given $\mathbf{r}_{proj}$ and $\mathbf{r}_{pred}$ two fully connected block modules with associated hidden dimension $d_{proj}$, the self-supervised consistency loss writes:

<figure><img src="image_8.png" /><figcaption>Figure 5: PlanB&B tree-consistency loss modeled after the SimSiam architecture from (Chen and He 2020).</figcaption></figure>

$$ \mathcal{L}_t(\hat{o}, \hat{o}) = \text{sim}(\text{flat} \circ \text{sg} \circ \mathbf{r}_{proj}(\hat{o}), \text{flat} \circ \mathbf{r}_{pred} \circ \mathbf{r}_{proj}(\hat{o})) $$

with flat(·) the flattening operation, sg(·) the stop-gradient operation and sim(·) the cosine similarity. Thus, the overall training objective associated with a trajectory ($s_t, a_t, ..., s_{t+K}$) is given by:

$$ \mathcal{L}_t(\theta) = \frac{1}{K+1} \sum_{k=0}^{K} \left[ \lambda_p \mathcal{L}_p(\pi_{t+k}, \hat{\mathbf{p}}_t^k) + \lambda_v \mathcal{L}_v(z_{t+k}, \hat{\mathbf{v}}_t^k) \right] \\ + \frac{1}{|\hat{T}^K|} \sum_{\hat{o} \in \hat{T}^K} \left[ \lambda_b \mathcal{L}_b(b_o, \hat{b}_{\hat{o}}) + \lambda_t \mathcal{L}_t(\hat{o}, \hat{o}) \right] \quad (3) $$

with $\lambda_p, \lambda_v, \lambda_b$ and $\lambda_t$ hyper-parameter loss weights.

## F Training pipeline

Our PlanB&B implementation builds on the official implementation from Ye et al. (2021) and Wang et al. (2024). Table 5 reports the hyperparameter values that were modified to suit our training setting. Our training pipeline follows the parallelized architecture introduced in EfficientZero, implementing a double-buffering mechanism, as illustrated in Figure 6. The training process operates synchronously across multiple components:

* MILP actors run B&B episodes using the current model, updated every 100 training steps, to produce policy targets $\pi_t$ via Gumbel Search and push generated trajectories into a shared replay buffer.

* CPU rollout workers sample these trajectories from replay buffer, and preprocess them by extracting B&B subtree trajectories from full B&B episodes, an operation confined to CPU resources.

* GPU batch workers unroll the PlanB&B model for K step using the target model, executing the most compute-intensive steps on the GPU.

* Finally, the learner worker receives both historic and imagined subtree trajectories and performs gradient updates according to Eq. (3).
<table><caption>Table 5: Training parameters for PlanB&B. Crucially, missing hyperparameter settings were kept fixed as in Wang et al. (2024) implementation.</caption><thead><tr><th>Parameter</th><th>Setting</th></tr></thead><tbody><tr><td>Training steps</td><td>10<sup>5</sup></td></tr><tr><td>Batch size</td><td>128</td></tr><tr><td>Optimizer</td><td>Adam</td></tr><tr><td>Learning rate l<sub>r</sub></td><td>10<sup>-3</sup> → 10<sup>-5</sup></td></tr><tr><td>Model unroll step (K)</td><td>3</td></tr><tr><td>TD steps (n)</td><td>3</td></tr><tr><td>Discount factor γ</td><td>1.0</td></tr><tr><td>Policy loss coefficient λ<sub>p</sub></td><td>1</td></tr><tr><td>Value loss coefficient λ<sub>v</sub></td><td>1</td></tr><tr><td>Branchability loss coefficient λ<sub>b</sub></td><td>1</td></tr><tr><td>Tree consistency loss coefficient λ<sub>t</sub></td><td>1</td></tr><tr><td>HL-Gauss min log value z<sub>min</sub></td><td>-1</td></tr><tr><td>HL-Gauss max log z<sub>max</sub></td><td>16</td></tr><tr><td>HL-Gauss number of bins m<sub>b</sub></td><td>18</td></tr><tr><td>HL-Gauss σ<sub>G</sub></td><td>0.75</td></tr><tr><td>Number of simulations N</td><td>50</td></tr><tr><td>Gumbel search root node action number M</td><td>10</td></tr><tr><td>Gumbel search shift factor c<sub>visit</sub></td><td>50</td></tr><tr><td>Gumbel search scaling factor c<sub>scale</sub></td><td>0.1</td></tr><tr><td>Variable node feature dimension d<sub>v</sub></td><td>43</td></tr><tr><td>Constraint node feature dimension d<sub>c</sub></td><td>5</td></tr><tr><td>Edge feature dimension d<sub>c</sub></td><td>1</td></tr><tr><td>Latent space embedding dimension d<sub>h</sub></td><td>64</td></tr><tr><td>Projection space dimension d<sub>proj</sub></td><td>16</td></tr><tr><td>Replay buffer capacity</td><td>10<sup>5</sup></td></tr><tr><td>MILP solving time limit (s)</td><td>3600</td></tr></tbody></table>

All components run in parallel. The replay buffer is shared between MILP actors and CPU workers, while a context queue is used for communication between CPU and GPU workers. A separate batch queue connects GPU workers and the learner. This design ensures efficient utilization of both CPU and GPU resources throughout training. Importantly, all workers except for CPU workers leverage GPU acceleration to evaluate the PlanB&B model. All experiments were conducted on a server equipped with an Intel(R) Xeon(R) Platinum 8480CL 128-core processor, 1024 GB of RAM and 4xNVIDIA A100 GPUs (40GB VRAM each). Resources were efficiently allocated across all workers using the Ray library, ensuring optimal workload distribution.

## G Baselines

**Imitation learning** We trained and tested IL agents using the official implementation of Gasse et al. (2019) shared at https://github.com/ds4dm/learn2branch-ecole/tree/main.

**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 exactly the same network architectures and training parameters as in DQN-Retro.

**PG-tMDP** We used the official implementation of Scavuzzo et al. (2022) to evaluate PG-TreeMDP. For each benchmark, we used the tMDP+DFS network weights shared at https://github.com/lascavana/rl2branch.

<figure><img src="image_9.png" /><figcaption>Figure 6: PlanB&B training pipeline, build upon the framework from Ye et al. (2021).</figcaption></figure>

**DQN-Retro** As Parsonson et al. (2022) only trained on set covering instances, we took inspiration from the official implementation shared at https://github.com/cwfparsonson/retroahaning to train and evaluate the DQN-Retro agent on the four Ecole benchmarks. Crucially, we trained and tested DQN-Retro following SCIP default node selection strategy.

Importantly, on the multiple knapsack benchmark, given the high computational cost associated with opting for a depth-first search node selection policy, all baselines excepted IL-DFS are evaluated following SCIP default node selection policy.

## H HL-Gauss Loss

As they investigated the uneven success met by complex neural network architectures such as Transformers in supervised versus reinforcement learning, Farebrother et al. (2024) found that training agents using a cross-entropy classification objective significantly improved the performance and scalability of value-based RL 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 on multiple neighboring histogram bins, to be a reliable solution across multiple RL benchmarks. Concretely, in HL-Gauss, the support of the value function $\mathcal{Z} \subset \mathbb{R}$ is divided in $m_b$ bins of equal width forming a partition of $\mathcal{Z}$. Bins are centered at $z_i \in \mathcal{Z}$ for $1 \le i \le m_b$, we use $\eta = (z_{max} - z_{min})/m_b$ to denote their width. Given a scalar $z \in \mathcal{Z}$, we define the random variable $Y_z \sim N(\mu = z, \sigma_G^2)$ and note respectively $\phi_{Y_z}$ and $\Phi_{Y_z}$ its associate probability density and cumulative distribution function. $z$ can then be encoded into a histogram distribution on $\mathcal{Z}$ using the function $p_{hist}: \mathbb{R} \to [0, 1]^{m_b}$. Explicitly, $p_{hist}$ computes the aggregated mass of $\phi_{Y_z}$ on each bin as $p_{hist}(z) = (p_i(z))_{1 \le i \le m_b}$ with:

$$p_i(z) = \int_{z_i - \frac{\eta}{2}}^{z_i + \frac{\eta}{2}} \phi_{Y_z}(y) dy = \Phi_{Y_z}(z_i + \frac{\eta}{2}) - \Phi_{Y_z}(z_i - \frac{\eta}{2}).$$
Conversely, histogram distributions $(p_i)_{1 \le i \le m_b}$ such as the ones outputted by agents' value networks can be converted to scalar simply by computing the expectation: $z = \sum_{i=1}^{m_b} p_i \cdot z_i$.

PlanB&B is a challenging setting to adapt HL-Gauss, as the support for value functions spans over several order of magnitude. In practice, we observe that for train instances of the Ecole benchmark, $\mathcal{Z} = [-10^6, -1]$. Since value functions predict the number of node of binary trees built with B&B, it seems natural to choose bins centered at $z_i = -2^i$ to partition $\mathcal{Z}$. In order to preserve bins of equal size, we consider distributions on the support $\psi(\mathcal{Z})$ with $\psi(z) = \log_2(-z)$ for $z \in \mathcal{Z}$, such that $\psi(\mathcal{Z})$ is efficiently partitioned by bins centered at $z_i = i$ for $0 \le i \le m_b$. Thus, histograms distributions are given by $p_{hist}(z) = (p_i \circ \psi(z))_{1 \le i \le m_b}$ for $z \in \mathcal{Z}$, and can be converted back to $\mathcal{Z}$ through $z = \sum_{i=0}^{m_b} p_i \cdot \psi^{-1}(z_i)$ with $\psi^{-1}(z) = -2^z$.

# I Further computational results

In this section, we provide additional background information to support and complement claims presented in Section 5.

**Additional performance metrics (Q1)** Table 7 provides additional performance metrics to compare the different baselines across test and transfer instances. 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 a baseline solves a 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 8 recapitulates the computational results presented in Table 1, and provides for each baseline the per-benchmark standard deviation over five seeds, as well as the fraction of test instances solved to optimality within the time limit.

**Targeted ablations (Q1) To be added.**

**Value network generalization (Q2)** To contextualize the results presented in Section 5, we provide additional discussion on the impact of leveraging the PlanB&B model to improve branching decisions. In our experiments, we observe that outside of the MIS benchmark, the value head $\bar{v}$ of the prediction network $f$ struggles to generalize to higher-dimensional MILPs. We attribute this to out-of-distribution effects: the value network is trained on instances with structurally smaller subtrees than those encountered in the transfer benchmarks. Similar limitations are observed in prior RL baselines: PG-tMDP demonstrates stronger generalization than both DQN agents, likely due to its reliance on a policy network rather than a $Q$-network to make branching decisions. Fortunately, this limitation does not prevent the policy network $p$ from producing efficient branching strategies on transfer instances, as shown in Table 1. However, it does hinder the ability of PlanB&B to refine branching decisions at inference time using its learned model, as the inaccuracies of the value predictions undermine planning. This is

<figure><img src="image_10.png" /><figcaption>Figure 7: Policy improvement associated with increased simulation budget over the CA benchmark.</figcaption></figure>

illustrated in Figure 7 on combinatorial auction instances: improved node performance can be achieved by leveraging model-based planning on test instances, but not on transfer instances. This limitation could potentially be addressed in future work by gradually increasing the dimensionality of the instances solved during training by the MILP actors, thereby allowing the value network to progressively adapt to larger B&B trees such as the one encountered in transfer benchmarks.

**Strong branching alignment metrics (Q3)** Table 2 reports three metrics designed to quantify the alignment between learned policies and the strong branching (SB) expert over MIS instances. First, we report the average cross-entropy between the predicted policy and the SB policy, normalized by the cross-entropy between the SB policy and a uniform random policy (SB C-Entropy). Second, we report the average strong branching score of the action selected by the learning baseline, normalized by the SB score of the action selected by the SB expert (SB Score). Third, we report the average frequency with which the learning baseline selects the same action as the SB expert (SB Freq). All metrics are averaged over 100 test instances and 20 higher-dimensional transfer instances.

**Influence of DFS on B&B solving time (Q4)** The overall impact of adopting a depth-first search (DFS) node selection policy is more nuanced than initially suggested in Section 5. In fact, as previously argued, DFS generally yields larger branch-and-bound (B&B) trees compared to
<table><thead><tr><th></th><th colspan="5">Test instances</th></tr><tr><th></th><th>Set Cov.</th><th>Comb. Auct.</th><th>Max. Ind. Set</th><th>Mult. Knap.</th><th></th></tr></thead><tbody><tr><th>SCIP</th><td>11.0</td><td>21.4</td><td>12.2</td><td>22.0</td><td></td></tr><tr><th>DFS</th><td>7.2</td><td>18.3</td><td>8.7</td><td>19.9</td><td></td></tr><tr><th>Gain</th><td>-30%</td><td>-10%</td><td>-25%</td><td>-14%</td><td></td></tr></tbody></table>

<table><caption>Table 6: Average transition time (ms) associated with the execution of $\kappa_p$ across the Ecole benchmark. We evaluate both SCIP's default node selection policy and depth-first search.</caption><thead><tr><th></th><th colspan="5">Transfer instances</th></tr><tr><th></th><th>Set Cov.</th><th>Comb. Auc.</th><th>Max. Ind. Set</th><th>Mult. Knap.</th><th></th></tr></thead><tbody><tr><th>SCIP</th><td>16.3</td><td>12.4</td><td>36.0</td><td>4.3</td><td></td></tr><tr><th>DFS</th><td>11.8</td><td>9.3</td><td>28.1</td><td>3.6</td><td></td></tr><tr><th>Gain</th><td>-25%</td><td>-25%</td><td>-22%</td><td>-16%</td><td></td></tr></tbody></table>

the advanced node selection heuristics used in modern MILP solvers, which often results in longer solving times. However, DFS also introduces a notable computational advantage: when nodes are explored along diving trajectories, solvers can leverage warm-start techniques to accelerate the resolution of successive linear programs. This speed-up can be quite substantial, as illustrated in Table 6. As a result, the net performance impact of DFS arises from the interplay between these two opposing effects: larger trees that increase computational workload, and faster LP solves that help mitigate this cost. This trade-off helps explain part of the performance gaps observed in Table 1 between DFS and non-DFS baselines. In particular, it clarifies how PlanB&B manages to solve test instances faster than the IL\* baseline despite producing larger trees in average. Nonetheless, DFS remains suboptimal overall when compared to the more advanced node selection strategies implemented in modern solvers.
<table><thead><tr><th rowspan="2">Method</th><th colspan="2">Train / Test</th><th colspan="4">Set Covering</th></tr><tr><th>Solved</th><th>Wins</th><th>Rank</th><th>Solved</th><th>Transfer<br>Wins</th><th>Rank</th></tr></thead><tbody><tr><td>SCIP</td><td>100/100</td><td>3/100</td><td>5.73</td><td>100/100</td><td>2/100</td><td>4.31</td></tr><tr><td>IL*</td><td>100/100</td><td>0/100</td><td>3.53</td><td>100/100</td><td>29/100</td><td>1.85</td></tr><tr><td>IL-DFS</td><td>100/100</td><td>33/100</td><td>2.10</td><td>100/100</td><td>58/100</td><td>1.70</td></tr><tr><td>PG-tMDP</td><td>100/100</td><td>0/100</td><td>6.6</td><td>78/100</td><td>0/100</td><td>6.95</td></tr><tr><td>DQN-tMDP</td><td>100/100</td><td>12/100</td><td>2.74</td><td>96/100</td><td>1/100</td><td>4.92</td></tr><tr><td>DQN-Retro</td><td>100/100</td><td>0/100</td><td>4.67</td><td>99/100</td><td>0/100</td><td>5.12</td></tr><tr><td>PlanB&B</td><td>100/100</td><td>52/100</td><td>2.76</td><td>100/100</td><td>10/100</td><td>3.17</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Method</th><th colspan="2">Train / Test</th><th colspan="4">Combinatorial Auction</th></tr><tr><th>Solved</th><th>Wins</th><th>Rank</th><th>Solved</th><th>Transfer<br>Wins</th><th>Rank</th></tr></thead><tbody><tr><td>SCIP</td><td>100/100</td><td>4/100</td><td>6.16</td><td>100/100</td><td>5/100</td><td>3.86</td></tr><tr><td>IL*</td><td>100/100</td><td>10/100</td><td>3.3</td><td>100/100</td><td>28/100</td><td>2.12</td></tr><tr><td>IL-DFS</td><td>100/100</td><td>26/100</td><td>2.7</td><td>100/100</td><td>26/100</td><td>2.47</td></tr><tr><td>PG-tMDP</td><td>100/100</td><td>2/100</td><td>5.08</td><td>100/100</td><td>0/100</td><td>5.83</td></tr><tr><td>DQN-tMDP</td><td>100/100</td><td>2/100</td><td>5.08</td><td>100/100</td><td>0/100</td><td>9.97</td></tr><tr><td>DQN-Retro</td><td>100/100</td><td>7/100</td><td>3.47</td><td>100/100</td><td>1/100</td><td>4.63</td></tr><tr><td>PlanB&B</td><td>100/100</td><td>42/100</td><td>2.6</td><td>100/100</td><td>40/100</td><td>2.12</td></tr></tbody></table>

<table><thead><tr><th rowspan="2">Method</th><th colspan="2">Train / Test</th><th colspan="4">Maximum Independent Set</th></tr><tr><th>Solved</th><th>Wins</th><th>Rank</th><th>Solved</th><th>Transfer<br>Wins</th><th>Rank</th></tr></thead><tbody><tr><td>SCIP</td><td>100/100</td><td>2/100</td><td>5.72</td><td>100/100</td><td>5/100</td><td>4.40</td></tr><tr><td>IL*</td><td>100/100</td><td>38/100</td><td>2.21</td><td>100/100</td><td>33/100</td><td>2.11</td></tr><tr><td>IL-DFS</td><td>100/100</td><td>14/100</td><td>2.9</td><td>100/100</td><td>0/100</td><td>3.23</td></tr><tr><td>PG-tMDP</td><td>100/100</td><td>0/100</td><td>4.62</td><td>100/100</td><td>23/100</td><td>3.1</td></tr><tr><td>DQN-tMDP</td><td>100/100</td><td>0/100</td><td>4.68</td><td>85/100</td><td>0/100</td><td>6.06</td></tr><tr><td>DQN-Retro</td><td>100/100</td><td>2/100</td><td>5.51</td><td>22/100</td><td>0/100</td><td>6.84</td></tr><tr><td>PlanB&B</td><td>100/100</td><td>44/100</td><td>2.45</td><td>100/100</td><td>32/100</td><td>2.26</td></tr></tbody></table>

<table><caption>Table 7: Additional performance metrics for each baseline on train / test and transfer instance benchmarks, see Appendix A 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 is defined as the number of instances where a baseline solves a MILP problem faster than all other baselines. When multiple baselines fail to solve an instance to optimality within time limit, their performance is ranked based on dual gap.</caption><thead><tr><th rowspan="2">Method</th><th colspan="2">Train / Test</th><th colspan="4">Multiple Knapsack</th></tr><tr><th>Solved</th><th>Wins</th><th>Rank</th><th>Solved</th><th>Transfer<br>Wins</th><th>Rank</th></tr></thead><tbody><tr><td>SCIP</td><td>100/100</td><td>73/100</td><td>1.60</td><td>100/100</td><td>53/100</td><td>2.11</td></tr><tr><td>IL*</td><td>100/100</td><td>0/100</td><td>4.60</td><td>100/100</td><td>7/100</td><td>3.39</td></tr><tr><td>IL-DFS</td><td>100/100</td><td>2/100</td><td>5.83</td><td>100/100</td><td>0/100</td><td>6.11</td></tr><tr><td>PG-tMDP</td><td>100/100</td><td>0/100</td><td>6.03</td><td>98/100</td><td>4/100</td><td>5.19</td></tr><tr><td>DQN-tMDP</td><td>100/100</td><td>1/100</td><td>3.71</td><td>99/100</td><td>11/100</td><td>5.71</td></tr><tr><td>DQN-Retro</td><td>100/100</td><td>3/100</td><td>3.61</td><td>100/100</td><td>9/100</td><td>4.01</td></tr><tr><td>PlanB&B</td><td>100/100</td><td>21/100</td><td>2.63</td><td>100/100</td><td>16/100</td><td>3.48</td></tr></tbody></table>
<table><caption>Table 8: Computational performance comparison on four MILP benchmarks. Following prior works, we report geometrical mean over 100 instances, averaged over 5 seeds, as well as per-benchmark standard deviations.</caption><thead><tr><th>Method</th><th>Nodes</th><th>Train / Test Time</th><th>Solved</th><th>Nodes</th><th>Transfer Time</th><th>Solved</th></tr></thead><tbody><tr><td>Random</td><td>3289 ± 4.2%</td><td>5.94 ± 4.3%</td><td>100/100</td><td>271632 ± 12.7%</td><td>842 ± 9.8%</td><td>60/100</td></tr><tr><td>SB</td><td>35.8 ± 0.0%</td><td>12.93 ± 0.0%</td><td>100/100</td><td>672.1 ± 0.0%</td><td>398 ± 0.2%</td><td>82/100</td></tr><tr><td>SCIP</td><td>62.0 ± 0.0%</td><td>2.27 ± 0.0%</td><td>100/100</td><td>3309 ± 0.0%</td><td>48.4 ± 0.1%</td><td>100/100</td></tr><tr><td>IL*</td><td>133.8 ± 1.0%</td><td>0.90 ± 4.8%</td><td>100/100</td><td>2610 ± 0.7%</td><td>23.1 ± 1.5%</td><td>100/100</td></tr><tr><td>IL-DFS</td><td>136.4 ± 1.8%</td><td>0.74 ± 5.3%</td><td>100/100</td><td>3103 ± 2.0%</td><td>22.5 ± 3.1%</td><td>100/100</td></tr><tr><td>PG-tMDP</td><td>649.4 ± 0.7%</td><td>2.32 ± 2.4%</td><td>100/100</td><td>44649 ± 3.7%</td><td>221 ± 4.1%</td><td>78/100</td></tr><tr><td>DQN-tMDP</td><td>175.8 ± 1.1%</td><td>0.83 ± 4.5%</td><td>100/100</td><td>8632 ± 4.9%</td><td>71.3 ± 5.8%</td><td>96/100</td></tr><tr><td>DQN-Retro</td><td>183.0 ± 1.2%</td><td>1.14 ± 4.1%</td><td>100/100</td><td>6100 ± 4.2%</td><td>59.4 ± 4.2%</td><td>98/100</td></tr><tr><td>PlanB&B</td><td>186.2 ± 0.4%</td><td>0.87 ± 6.0%</td><td>100/100</td><td>5869 ± 2.5%</td><td>46.2 ± 3.1%</td><td>100/100</td></tr><tr><td colspan="7" style="text-align: center;">Set covering</td></tr><tr><th>Method</th><th>Nodes</th><th>Train / Test Time</th><th>Solved</th><th>Nodes</th><th>Transfer Time</th><th>Solved</th></tr><tr><td>Random</td><td>1111 ± 4.3%</td><td>2.16 ± 6.6%</td><td>100/100</td><td>3172355 ± 7.5%</td><td>749 ± 9.1%</td><td>64/100</td></tr><tr><td>SB</td><td>28.2 ± 0.0%</td><td>6.21 ± 0.1%</td><td>100/100</td><td>389.6 ± 0.0%</td><td>255 ± 0.2%</td><td>88/100</td></tr><tr><td>SCIP</td><td>20.2 ± 0.0%</td><td>1.77 ± 0.1%</td><td>100/100</td><td>1376 ± 0.0%</td><td>14.77 ± 0.1%</td><td>100/100</td></tr><tr><td>IL*</td><td>83.6 ± 0.8%</td><td>0.65 ± 8.5%</td><td>100/100</td><td>1282 ± 1.6%</td><td>9.4 ± 2.0%</td><td>100/100</td></tr><tr><td>IL-DFS</td><td>95.5 ± 0.9%</td><td>0.56 ± 7.2%</td><td>100/100</td><td>1828 ± 2.0%</td><td>10.2 ± 1.6%</td><td>100/100</td></tr><tr><td>PG-tMDP</td><td>168.0 ± 2.8%</td><td>0.94 ± 6.0%</td><td>100/100</td><td>6001 ± 2.7%</td><td>30.7 ± 2.4%</td><td>100/100</td></tr><tr><td>DQN-tMDP</td><td>203.3 ± 4.2%</td><td>1.11 ± 4.0%</td><td>100/100</td><td>20553 ± 3.8%</td><td>116 ± 3.9%</td><td>100/100</td></tr><tr><td>DQN-Retro</td><td>103.2 ± 1.2%</td><td>0.78 ± 7.5%</td><td>100/100</td><td>2908 ± 1.7%</td><td>18.4 ± 2.7%</td><td>100/100</td></tr><tr><td>PlanB&B</td><td>84.7 ± 1.4%</td><td>0.54 ± 7.9%</td><td>100/100</td><td>1665 ± 2.3%</td><td>9.1 ± 2.4%</td><td>100/100</td></tr><tr><td colspan="7" style="text-align: center;">Combinatorial auction</td></tr><tr><th>Method</th><th>Nodes</th><th>Train / Test Time</th><th>Solved</th><th>Nodes</th><th>Transfer Time</th><th>Solved</th></tr><tr><td>Random</td><td>386.8 ± 5.4%</td><td>2.01 ± 4.8%</td><td>100/100</td><td>215879 ± 6.7%</td><td>2102 ± 6.2%</td><td>25/100</td></tr><tr><td>SB</td><td>24.9 ± 0.0%</td><td>45.87 ± 0.4%</td><td>100/100</td><td>169.9 ± 0.2%</td><td>2172 ± 0.9%</td><td>15/100</td></tr><tr><td>SCIP</td><td>19.5 ± 0.0%</td><td>2.44 ± 0.4%</td><td>100/100</td><td>3368 ± 0.0%</td><td>90.0 ± 0.2%</td><td>100/100</td></tr><tr><td>IL*</td><td>40.1 ± 3.45%</td><td>0.36 ± 3.4%</td><td>100/100</td><td>1882 ± 4.0%</td><td>38.6 ± 3.3%</td><td>100/100</td></tr><tr><td>IL-DFS</td><td>68.5 ± 6.5%</td><td>0.44 ± 4.1%</td><td>100/100</td><td>3501 ± 2.7%</td><td>51.9 ± 2.1%</td><td>100/100</td></tr><tr><td>PG-tMDP</td><td>153.6 ± 5.0%</td><td>0.92 ± 2.6%</td><td>100/100</td><td>3133 ± 4.6%</td><td>43.6 ± 2.9%</td><td>100/100</td></tr><tr><td>DQN-tMDP</td><td>168.0 ± 5.6%</td><td>1.00 ± 3.4%</td><td>100/100</td><td>45634 ± 7.4%</td><td>477 ± 5.1%</td><td>85/100</td></tr><tr><td>DQN-Retro</td><td>223.0 ± 4.1%</td><td>1.81 ± 3.6%</td><td>100/100</td><td>119478 ± 6.1%</td><td>1863 ± 4.8%</td><td>22/100</td></tr><tr><td>PlanB&B</td><td>44.8 ± 7.6%</td><td>0.32 ± 6.4%</td><td>100/100</td><td>2853 ± 4.9%</td><td>41.1 ± 5.4%</td><td>100/100</td></tr><tr><td colspan="7" style="text-align: center;">Maximum independent set</td></tr><tr><th>Method</th><th>Nodes</th><th>Train / Test Time</th><th>Solved</th><th>Nodes</th><th>Transfer Time</th><th>Solved</th></tr><tr><td>Random</td><td>733.5 ± 13.0%</td><td>0.55 ± 6.9%</td><td>100/100</td><td>93452 ± 14.3%</td><td>70.6 ± 9.2%</td><td>99/100</td></tr><tr><td>SB</td><td>161.7 ± 0.0%</td><td>0.69 ± 0.1%</td><td>100/100</td><td>1709 ± 0.5%</td><td>12.5 ± 0.9%</td><td>100/100</td></tr><tr><td>SCIP</td><td>289.5 ± 0.0%</td><td>0.53 ± 0.2%</td><td>100/100</td><td>30260 ± 0.0%</td><td>22.1 ± 0.2%</td><td>100/100</td></tr><tr><td>IL*</td><td>272.0 ± 12.9%</td><td>0.69 ± 8.1%</td><td>100/100</td><td>11730 ± 7.1%</td><td>43.5 ± 6.4%</td><td>100/100</td></tr><tr><td>IL-DFS</td><td>411.5 ± 13.0%</td><td>1.07 ± 8.8%</td><td>100/100</td><td>43705 ± 9.2%</td><td>130.8 ± 8.3%</td><td>98/100</td></tr><tr><td>PG-tMDP</td><td>436.9 ± 21.2%</td><td>1.57 ± 16.9%</td><td>100/100</td><td>35614 ± 14.3%</td><td>123 ± 15.4%</td><td>98/100</td></tr><tr><td>DQN-tMDP</td><td>266.4 ± 7.2%</td><td>0.73 ± 4.6%</td><td>100/100</td><td>22631 ± 8.6%</td><td>65.1 ± 5.5%</td><td>99/100</td></tr><tr><td>DQN-Retro</td><td>250.3 ± 9.5%</td><td>0.67 ± 5.0%</td><td>100/100</td><td>27077 ± 8.8%</td><td>79.5 ± 6.2%</td><td>100/100</td></tr><tr><td>PlanB&B</td><td>220.0 ± 5.9%</td><td>0.55 ± 4.9%</td><td>100/100</td><td>13574 ± 6.6%</td><td>51.2 ± 4.8%</td><td>100/100</td></tr><tr><td colspan="7" style="text-align: center;">Multiple knapsack</td></tr></tbody></table>