Towards Better Branching Policies: Leveraging the Sequential Nature of Branch-and-Bound Tree
Authors: Ce Zhang
Bin Zhang
Guoliang Fan
Venue: ICLR 2026 Poster (2026)
Keywords: Mixed-Integer Linear Programming
Branch-and-Bound
Branching Variable Selection Policy
Generalization
Mamba
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We propose a branching policy that utilizes the sequential branching path of the branch-and-bound tree to guide current decision.

Abstract: The branch-and-bound (B\&B) method is a dominant exact algorithm for solving Mixed-Integer Linear Programming problems (MILPs). While recent deep learning approaches have shown promise in learning branching policies using instance-independent features, they often struggle to capture the sequential decision-making nature of B\&B, particularly over long horizons with complex inter-step dependencies and intra-step variable interactions. To address these challenges, we propose Mamba-Branching, a novel learning-based branching policy that leverages the Mamba architecture for efficient long-sequence modeling, enabling effective capture of temporal dynamics across B\&B steps. Additionally, we introduce a contrastive learning strategy to pre-train discriminative embeddings for candidate branching variables, significantly enhancing Mamba's performance. Experimental results demonstrate that Mamba-Branching outperforms all previous neural branching policies on real-world MILP instances and achieves superior computational efficiency compared to the advanced open-source solver SCIP. The source code can be accessed at https://github.com/doctor-watson626/Mamba-Branching/.

Published as a conference paper at ICLR 2026
TOWARDS BETTER BRANCHING POLICIES: LEVER- AGING THE SEQUENTIAL NATURE OF BRANCH-AND- BOUND TREE
Guuliingg The Key Laboratory of Cognition and Decision Intelligence for Complex Systems, Institute of Automation, Chinese Academy of Sciences
Ce Zhang'.2, Bin Zhang Guoliang Fan
2 School of Artificial Intelligence, University of Chinese Academy of Sciences [zhangce2023, zhangbin2020, guoliang. fan) ia ac en
ABSTRACT
The branch-and- ann-bound (B&B) method is dominant exact algorithm for solving Wixed-Integer Linear Programming problems (MILPs). While recent deep learning approaches have shown promise in learning branching policies using instance- independent features, they often struggle to capture the sequential decision-making nature of B&B, partieularly over long horizons with complex inter-step depen- dencies and intra-step variable interactions. To address these challenges, we propose Mamba- Branbbhi-annnng, a novel learning based branching policy that leverages the Mamba architecture for efficient long- sequence modeling, enabling effective capture of temporal dynamics across B&B steps. Additionally, we introduce a contrastive learning strategy to pre-train discriminative embeddings for candidate branching variables, significantly enhancing Mamba's performance. Experimen- tal results demonstrate that branching policies on real-world MILP instances and achieves superior computa- tional efficiency compared to the advanced soun-souree solver SCIP. The source code can be accessed at https:: :tna:///iin /tttthg...b//tt////// com Mamba Branching/
Branching outperforms all previous neural
cww/doctor doctor wwt.wwwtsnnaao
INTRODUCTION
Mixed Integer Linear Programming problems (MILPs) constitute class of computationally chal- lenging NP-hard problems with widespread applications across diverse domains, including schedul- ing (Chen 2010), planning (Pochet & Wolsey (006), and transportation (Barnhart & Laporte (0066). The branch-and-bound (B&B) method (Land & Doig 2010) represents the predominant solution methodology for MILPs in practice. This approach begins with the relaxation of the original problem and iteratively branches on variables that violate integer constraints. By maintaining global upper and lower bounds, the method progressively converges toward an optimal solution. Many high- performance MILP solvers such as SCIP (Bolusani et al., (202)) and Gurobi (Gurobi Optimization [LC. 2024) employ the B&B framework as their core solution architecture.
Within the B&B framework, the selection of branching variables plays critical role in determining computational efficiency. To this end, learning-bass based branching methods have been proposed (Gasse et al. 2019: Gupta et al.) [2020] 2022, [Scauzzzo et al.) 2022): by constructing a bipartite graph that incorporates instance features and intra-tree dynamic features, and utilizing graph convolutional networks (GCNN) (Gasse et al. 2019) for state encoding. Nevertheless, reliance on instance-specific features restricts their generalization to heterogeneous MILP instances. To enable cross-ine -nsstnnnttnnce adaptability, recent approaches have focused parameterizing the B&B tree to construct shared feature space independent of specific problem data. For example, Zarpellon et al. (Zarpellon et al. 2021) develop a parameterized B&B tree framework to create shared feature space, decoupling branching decisions from instance-specific features. Further advancing this approach, T-BranT (Lin al. 2022) evaluates the mutual connections between candidate variables by the self-attention
"Corresponding zhanghin2020@ian ia..c. and Munliang.fam@ia.ee.

---

Published as a conference paper at ICLR 2026
mechanism and employs Graph Attention Networks to encode the empirical branching history in the search tree.
However, existing works universally overlook the sequential nature inherent in B&B tree expansion. In this paper, our key insight lies in that the "branching path" from the root node to the optimal solution node essentially constitutes serialization process. This "branching path". which encompasses the parameterized tree states and corresponding branching variables from each preceding step, significantly influences the current branching decision. While T-Bran' incorporates historical data, it models the tree from an unordered graph perspective, failing to explicitly capture this essential sequential nature. Effectively modeling this sequential nature presents two key challenges: (1) Design of long sequence modeling architectures. The sequence model must simultaneously capture inter-step dependencies and intra-step candidate variable relationships. Given that each state comprises multiple candidate variables, the length of the sequence input will increase exponentially with the number of branching steps. Therefore, is essential to develop specialized architectures that can accommodate ultra-Iong sequences. (2) Construction of discriminative feature embeddings. An embedding layer needs to be designed to map the features of candidate variables into a high-dimensional vector space with high discriminative power. This will enable the sequence model to effectively discern the dynamic evolution patterns of different variables.
To address these challenges, propose Mamba- Mamba-Branching Branching. Mamba (Gu & Dao 2024 Dao & Gu 2024) is a novel network architecture characterized by its computational complexity that scales linearly with sequence length. This represents significant improvement over the quadratic complexity associated with Transformers (Vaswani et al., (017). making Mamba particularly well-suited for addressing challenge (1), Meanwhile, we employ contrastive learning to train the embedding layer prior to the overall imitation learning process, effectively tackling challenge (2). Experimental results demonstrate that instances and achieves superior solving efficiency over the advanced open- solver SCIP's default branching nule on challenging instances.
outperforms all neural branching baselines across all real- world
RELATED WORK
Learning-based approaches for accelerating MILP solving can be mainly divided into two paradigms (Bengio et al. 2021 Scavuzzo et al. 2024): : replacing heuristic rules with neural networks within exact solution frameworks and employing neural networks as primal hcuristics. Research under the first paradigm includes addressing branching variable selection (Khalil et al. (0166) Gasse
al. 2019: Gupta al., 2020, 2022 Scavuzzo et al. 2022. Kuang et al. 2024a (b) and node selec- tion (ee et al.) 2014 Labassi et al. [022] Zhang et al. 2025) problems within the B&B framework, as well as tackling cut selection issues cutting- planne algorithms (Tang et al. 2020; Huang et al.) 2022, Wang et al. 2023). These methods solely employ neural networks to replace heuristic rules within exact solution frameworks, without compromising solution exactness. The second paradigm aims to efficiently produce high-quality feasible solutions- rather than exact solutions to tighten the primal bound early in the process. A high-quality primal bound enables the B&B to eliminate significant number of non-promising nodes an early stage through its pruning process. This typically involves two key aspects: solution prediction (Ding et al., 2020): Nair et al. 2021 | Khalil al. 2022 Han et al., 2023 Huang al., 22224] Liu et al. 2025) and neighborhood selection (Wu et al.
2021 Sonnerat et al. 2022 Huang et al. 2023 Yuan et al. 2025). The solution prediction approach typically employs neural networks to directly predict optimal solutions, then uses these predictions to guide the search process. Neighborhood selection starts from a feasible solution and fixes a subset of integer variables while optimizing the remainder, with neural networks selecting which variables to fix.
Our work focuses on the generalization of neural branching variable selection policies. particularly their ability to handle heterogeneous MILPss different from training instances. These approaches can be mainly divided into two categories: parameterizing the B&B tree and diversifying training instances. The first category aims to learn branching policies within a shared feature space across different MILP instances. TreeGate (Zarpellon et al. 2021) processes instance- iisance-iddeeendemt features through specialized neural architecture designed for branching decisions. Building this, T- BranT (Lin et al., 2022) retains historical data, modeling it as a graph structure processed by Graph Attention Networks for current decision-making. The second category focuses generating diverse
2

---

Published as a conference paper at ICLR 2026
instances and incorporating them into the training of branching policies to enhance their generalization. AdaSolver (Liu et al. 2023) introduces adversarial instance augmentation, which generates more diverse instances in directions that hinder policy training. Mcanwhile, MILP-Evolve (Li al. 2025) proposes a novel I.L.-based evolutionary framework capable of generating a set of diverse MILP classes with unlimited number of instances. Specifically, our method falls into the first category.
3 PRELIMINARIES
3.1 B&B ALGORITHM AND BRANCHING RULES
B&B Algorithm. The standard form of MILPs is: arg {c"x Ax b, 2" x R" where the vector x represents n variables to be optimized, with p being the number integer variables. A, b, represent constraint matrix, constraint right term, and objective coefficient. For MILPs, an exact solution framework commonly used B&B. This method first ignores the integer constraints to obtain and solve the relaxed problem at the root node. Subsequently, it iteratively searches for the global optimal solution through branching, bounding, and pruning. Branching involves selecting a variable with a fractional solution æ; by the current node and adding the constraints æj S [b,] and 2, 2 bby] + 1 to form two child nodes. During bounding, the global upper and lower bounds (also known as the primal and dual bounds) are determined based on all existing nodes. The pruning process eliminates obviously infeasible nodes according to these bounds. This procedure repeats until the upper and lower bounds converge, yielding the global optimal solution.
Branching Rules. Here, the branching variable selection during B&B significantly impacts solving efficiency by influencing tree size. In (Achterberg et al. (005), several heuristic branching rules are introduced. Among them, strong branching evaluates candidate variables by creating child nodes for each candidate and selecting the one maximizing dual bound improvement. While highly effective, this approach incurs significant computational overhead that counteracts its benefits for solution speed. Pscost branching guides current branching by leveraging historical branching records, avoiding extra computation but performing poorly early in the search tree due insufficient branching records. Hybrid approaches combine both methods' advantages by using strong branching initially to establish reliable branching patterns, then transitioning to pscost branching once sufficient historical data is accumulated. The state-of-the-art (SOTA) relpscost branching (Achterberg 2025), SCIP's default rule, implements this strategy-a variable's pscost is only considered trustworthy after undergoing sufficient strong branching steps.
3.2 PARAMETERIZED B&B TREE
To parameterize the B&B tree and obtain cestuncc-indeeendeeen features for heterogeneous MILP problems, Zarpellon et al. (Zarpellon et al. (022)) design state representation Here, C, E [2 denotes candidate variable features, and Tree; E R represents tree features, where C, denotes candidate variable set and |C, represents candidate variable number. Since all features reflect the dynamic process of B&B trees, all MILP instances can be processed uniformly in same feature space by a neural network named TreeGate, which jointly processes candidate and tree features through two components: a candidate network and a tree network. The candidate network first embeds each variable's s 25 didmmennionall features into an h-dimensional space, then progressively reduces the dimensionality from h to d through multiple layers that halve the dimension each step. Meanwhile, the tree network projects the tree features Tree, into an H-dimensional space (where I! h + h/2 + ... + d) using sigmoid activation produce a gating vector g [0, 1 This gating vector modulates the candidate network's 's layer outputs through element-wise multiplication. The final output e, e IR (/Cx) xd undergoes average pooling across the d-dimensional features, then being processed by softmax layer to generate the candidate variable selection probabilities.
(Ct, Tree.).
4 METHODOLOGY
In this section, formally introduce Hamba-Branching. neural branching policy specifically designed to capture the sequential structure B&B trees. We begin by discussing the contrastive learning approach utilized for the embedding layer and the detailed design of the sequence inputs,
3

---

Published as a conference paper at ICLR 2026
Step 1. Contrastive Learning
Step 2. Imitation Learning
Cross Entropy
Avg Pooling Softmax
Prika
c
and
Similar
Not Similar
(effi a E C3)
Max Poolinggg
Sequence Model (Mambe)
Expert Embedding
Other Embeddings
Pos Ids o,.. 0,0
Pos ids
Pos Ids Tiqu T
Embedding
C f
Layer
eg Col
ot. ef
%t (C,, Treee)
Embedding Layer
Data Flow
B&&B Tree
Gradient Flow
(5p: Qg Sqc Og Sy)
Figure/ 1: Overall framework of Baabbb-rannchig. The training process involves two stages: contrastive learning and autoregressive imitation learning. During the contrastive learning process, the state and expert decision a, at each branching step are used to train the embedding layer via the designed contrastive loss function Le. During imitation learning, the branching trajectory
(8o, 40: ..., ST) is mapped to embeddings. At step i, expanded variable embeddings (e) .... e(c.)) ( and expert embedding et form a group with shared positional encoding. These groups create "branching path" input to the sequence model, where only outputs or corresponding to the variable embeddings are selected, with a, serving as the label for imitation learning.
followed by the detailed implementation of imitation learning. The overall framework of Mamba- Branching is illustrated in Figure
4.1 CONTRASTIVE LEARNING FOR EMBEDDING LAYER
The embedding layer serves critical interface between state representations and downstream sequence models. In natural language processing (NLP), the success of embedding techniques has been well-established. These methods leverage the inherent distinguishability of discrete word tokens, where each word's unique identity naturally translates to separable embedding vectors through standard training paradigms. (Bengio et al.) 2000; Mikolov et al., 2013) However, the branching variable selection problem in B&B presents a fundamentally different challenge. The state representation at each branching step I, denoted as 8, = (C,, Tree;) (see (see/subsectionn 3.2), contains set of candidate variables C. that frequently exhibit remarkably similar feature characteristics. This high degree of intra-step similarity arises from the shared constraints and problem structure inherent in combinatorial optimization problems. Unlike the clear distinctions between words in NLP tasks, the subtle but decision-critica differences between candidate variables in B&B require a more sophisticated approach to embedding learning.
To address this challenge, we develop principled framework for learning discriminative embeddings in B&B decision making. The core of our approach lies in recognizing that effective branching decisions require the embedding space to maintain consistent separation between selected and non- selected variables. We formalize this requirement through Proposition [ This condition specifies that the similarity between the selected variable's ' embedding and a reference vector must exceed all other candidate similarities by positive margin 5.
Proposition 1. For effective branching decisions, the embedding space must satisfy:
Vt, 38 > 0 s.t. sim(e,,ee")
maxxim(e,, e(i))
ifa
where sim(-) is similarity judgment function, e, denotes embeddings, et is an anchor. denotes the selected variable index.
The intuitive understanding and proof of Proposition J detailed in Appepdied A To approximately satisfy this condition during training, we design contrastive loss Les with the specific form as follows:
La(r)
Σ
Σ tsto
(2)
le
eff
[c,
|e
4

---

Published as a conference paper at ICLR 2026
Here, use cosine similarity sim(.). y denotes the parameters of TreeGate, T denotes the total number of branching steps, é = TreeGate, (st) and et" is a context-aware anchor embedding (obtained via max-pooling over candidate embeddiing)).
The intuition behind this loss function design is to make the selected branching variable the most prominent and distinctive among all candidate variables. The max-pooling operation extracts salient global feature as an anchor. By increasing the cosine similarity between the anchor and the selected branching variable while decreasing the cosine similarity between the anchor and other candidate variables, the loss amplifies their differences and drives the feature of the selected branching variable toward the globally most salient direction.
4.2 SEQUENTIAL MODELING DESIGN
In B&B tree, nodes are progressively expanded until the upper and lower bounds converge. This process can be viewed as navigating through a complex maze to find a "branching path" from the root node to the optimal solution node. Traditional neural approaches to branching decisions have predominantly relied on the immediate state of the tree, neglecting the historical sequence of visited nodes and prior branching choices. This myopic perspective is fundamentally limiting, it fails to leverage the rich sequential information inherent the branching process. Just as an effective maze- solving strategy requires reasoning about the entire traversed path to avoid dead ends and redundant exploration, optimal branching decisions demand a holistic understanding of the search trajectory. This underscores the imperative for paradigm shift toward path-aware sequential modeling.
To effectively model branching decisions, the sequence model must capture not only the sequential progression of states but also the intricate interrelationships among candidate variables within each state. Therefore. we explicitly encode the features of each candidate variable at all branching steps. We formally define the branching path S as a structured sequence of embeddings, where each state at step is decomposed into its constituent candidate variables along with the selected branching decision. Specifically, represented as:
S = (e0
CCo
80
0
0
Coll11
1c,+11
CT
where [C,] denotes the number of candidate variables at branching step f, a represents the index of the selected branching variable, e, denotes the embedding feature, and T is the maximum number of branching steps in the branching path. This formulation ensures that both the sequential dynamics and the variable-level interactions are preserved, enabling the model to leverage granular features for improved decision-making
To ensure temporal coherence across branching steps, we employ positional encodings that assign identical positional indices to embeddings within the same step. The complete input representation S' constructed by combining the branching path S with learnable positional encoding matrix Epos:
po8 0,...,,0 0,0,
S' = -Epos @ S,
[Cal+-1
where @ denotes element-wise addition, Epos E ROT [c,l+T)xxd represents the learnable positional encoding matrix obtained by mapping pos.
Subsequently, S' is fed into Mamba obtain the output O,:
O Mamba(S') = [o o Col ao ob ,..,..., [Cal
ooc. . .T: ......., of
JCrl
(5)
within each group, only the outputs corresponding to |Cel variable positions are extracted, denoted as Ot ......... ofCt ), which are then processed through average pooling and softmax to obtain the variable probability distribution.
can be observed that for the branching path S. the sequence model actually needs to process an input length of E C.I+T. TT When either T or |C,] becomes large, the length of S increases substantially, presenting significant challenges to the sequence model's 's ability handle long sequences. Therefore, Transformer Decoder as our sequence model, also utilize Mamba (Gu & Dao. 2024) (see Appendix B for architectural details). In contrast.
in addition to employing the most commonly-use
5

---

Published as a conference paper at ICLR 2026
to the Transformer's quadratic complexity, Mamba achieves linear complexity relative sequence length, making it unequivocally better suited for such long-sequence application scenarios. This is particularly critical in application, where computational speed is paramount. If the neural branching policy's 's inference complexity becomes excessively high and computationally prohibitive, it would fundamentally undermine our original objective of acceleration.
4.3 IMITATION LEARNING UNDER AUTOREGRESSIVE PARADIGM
Following prior works (Zarpellon et al. 2021 Lin et al. 2022). we employ relpscost branching as
the expert to collect demonstration datasets for imitation learning. Unlike (Gasse et al. 2019; Gupta
ctt al. 2020), we do not employ strong branching as the expert, for reasons detailed in Appendix C For dataset collection, each instance is solved using SCIP. We sequentially record every state in the instance's tree along with the corresponding relpscost-selectee in complete trajectory denoted (su, do $1, .1....). In dataset D, each instance's trajectory is
branching decisions, resulting
partitioned into fixed-length sub-trajectories for storage.
In Mamba- Branching, the branching policy is defined no, which operates in autoregres- sive paradigm. The joint loss function L(0,7) of embedding layer and sequence model is as follows: (( = - ErED L( log тe (T: where denotes trajectory in D, The = (80, do....,, a,-1, 8e), and (D) represents the total number of trajectories in D. During infer- ence, the predictions from previous branching steps serve as input for the current step, yielding the probability distribution Toe (o:r) over candidate variables, where for = (so, . at)
5
EXPERIMENTS
5.1
SETUP
5.1.1
BENCHMARKS
Benefiting from instance-independee feature inputs, our method can generalize to heterogeneous MILPs, thus requiring distinct training and test instances to be selected separately.
MILP dataset.
Following the selection of instances from previous works (Zarpellon al. 2021 Lin al. 2022), we construct two MILP datasets of different scales using instances from MIPLIB (Gleixner et al. 2021)
and CORAL (Lehigh University COR @ Lab m.d.):: smaller-scale dataset (MILP-S) and a larger-
scale dataset (MILP-I.). The MILP.S is entirely derived from (Zarpellon et al.) 2021 comprising 19 training instances and test instances. MILP-L extends (Lin et al. (022) with training and test instances. Using SCIP reference, we categorize the test set into 57 "casy" instances (solved in 20 minutes) and 16 "difficult" instances (more than minutes). The details of MILP-S and MILP-L are provided in Appendix D
Branching Dataset Collection. Consistent with prior works (Zarpellon et al.. 2021 Lin et al. 2022 use random branching for the first steps improve B&B exploration, then switch to relpscost branching for data collection. For each training instance, we set E {0, 1, 5, 10, 15} and collect training data using seeds 1, 2, 3), reserving seed 4 solely for validation.
5.1.2 METRICS
Nodes and Fair Nodes. The node count in the B&B tree a key performance indicator for branching policies, it directly affects solving time. However, observed in (Gamrath & Schubert 2018). this measure can be influenced by side effects of sophisticated branching rules like strong branching. To address this, we also adopt the fair node count (Gamrath & Schubert (0088). which removes such biases and offers more precise assessment of a branching policy's 's effectiveness.
Primal-Dual Integral. Under 1-hour time constraint, it is impossible find the optimal solution for difficult instances in MILP-L. In such cases, neither time nor node count can serve as metrics, and the primal-dual integral (PD integral) serves as a more appropriate evaluation criterion (Gasse et al.)
2022). With a time limit Tú, the PD integral is expressed as dual bound at time f, x; is the best feasible solution at time
م c cTx; - yy dt, where y? is the best

---

Published as a conference paper at ICLR 2026
Table 1:
The experimental results on MILP-S and MILP-L. blue background indicates the best
results, bold font indicates the best results in neural policies, and denotes reaching the time limit (1 hour), OOM stands for CUDA out of memory.
MILP-S
MILP-L Easy
MILP-L Difficult
Method
Nodes
Nodes
Nodes
Time
Integral
Hamba-BBannhinng
2068.83
2091.54
111.78
1819.32
2053.91
123.79
12319.55
TreoGate
2146.755
2180.04
113.85
2218.29
2534,09
145.44
14625 68
T- I
2668.62 6268.62
2715.16
165.59
2009.77
2298.76
210.27
13538.47
Transformer Branching
3078.566
3120.04
3153.66
0OM
0OM
00M
OOM
GCNN
13.63
337 13.63
730.89"
random
664887 88**
66487.87 87*
1189.57
pscost
7308 23
7308.25
209.30
3681.06
3681.06
183.36
17097.06
relpscusi
730.21
1227.25
82.51
667.93
1455.49
68.43
12741.36
5.1.3 BASELINES AND SETTINGS
We evaluate our method against two categories of branching policies: neural- based models and classical heuristics. Neural baselines include: (1) GCNN Gasse et al. (2019). the seminal GNN-base
branching policy; (2) TreeGate (Zarpellon al., 2021) and T-Bran'T (Lin al. 2022), instance- independent architectures serving as primary comparators to Bamba--ranchhig: (3) Transformer- Branching, a requence-modellee
baseline using Transformer, designed to isolate and highlight Mamba's 's architectural advantages. The heuristic rules include random, pscost, and relpscost, where relpscost serves the expert and constitutes the upper bound of branching performance. though neural policies may surpass it in efficiency under certain conditions.
In our evaluation, we replace SCIP solver's (v8.0.4) branching policy with our neural branching policy. To isolate the study of branching policies and eliminate interference from other solver components, we disable all primal heuristics and provide each test instance with a known optimal solution value as cutoff. However, during branching data collection, we intentionally omit the cutoff to obtain longer branching sequences. For neural baselines, during training, Mamba-Branchin up to T 99 seeps-cooresponding to significantly long input lengths (see subsection 4.2). Due to excessive GPU memory consumption, Transformer- Brrancchhe--nnnninngggg is trained with a truncated horizon of T = 9. For evaluation consistency, all models generate decisions autoregressively under unified budget of T = 24. More details for baselines and implementation can be found in [Appendix and Appendix
processes sequences
5.2 BRANCHING PERFORMANCE
The experimental results in MILP-S and MILP-L can be found in Table with the fair node results of all neural branching policies per instance in MILP-S shown in Figure 2 Each instance is evalu- ated with 5 random seeds and the results are presented as geometric means. Notably, T-Bran'T necessitates at least one set of historical data, prompting the use of relpscost at the root node. This precise branching decision at the root significantly influences overall per- formance. For consistency, all neural policies use relpscost the root node. To evaluate the performance of purely neural branching, also evaluate variants without relpscost initialization denoted Mamba-Branching--e Branching-p), as reported in Table 2) It can be observed that Mamba- BrabbhhinB the best branching policy besides relpscost. First, Mamba-BB Mamba-Branching significantly outperforms the three lower-bound references: GCNN, random, and pscost. Compared with several neural branching policy baselines, whether initialized with relpscost or purely neural- based, Mamba-Bram Branchinngchggg surpasses T-Bran'T, TreeGate, and Transformer- Branneerr-rrnnnngg... achieving a new SOTA for neural branching policies. As shown in Figure 2 3 of the 8 test instances, surpassing other neural branching policies. This demonstrates that the advantage of Mamba- Branching over other neural branching policies is not attributable to any single outlier but rather constitutes overall superiority. Additionally, in terms of single-step inference time, as shown in Figure 3] Mamba significantly outperforms Transformer, highlighting its advantage as sequence model.
Table 2: The neural branching results without relpscost initial- ization on MILP-S.
Methed
Nodes Fair Nodes
Time
Branching Transformer
Mamba
2272.43
2272.43
147.96
-Branching-p
5138.15
5138.15
5237.15
TreeGatc-p
3179.55
3179.55
163.39
T-BranTTpp
3922.63
257.23
with the suffix "-p" (e.g., TreeGate-p. Mamba-
Mamba-Branching achieves the best performance
Mamba-Branching
7

---

Published as a conference paper at ICLR 2026
renser
10000
Mamba TreeGate
T-BranT Transformer
1923
0.037
8000
Invtances
neod11
6,00:92
neas18
1L0099
4000
maple
1:001
0.015
G.0193
miin 106--
9-mean map18 mime-16s-3
neosi1
"eozia" 211830653
nu25-pr12
ralis07 soymourl
soymour
0.013
10'
30"
15-1
Instances
Time (saconds, log scale)
Figure 2: The fair node results of all neural branching policies in Figure 3: The inference time MILP-S. The black shading indicates the method with the fewest comparison between Mamba fair nodes for each instance.
and Transformer in MILP-S.
In MILP-L, further evaluate several methods that demonstrated strong performance in MILP-S. For the 57 easy instances, performance assessed using nodes, fair nodes and time. For the 16 difficult instances, geometric mean results are presented in Table The results demonstrate that for easy MILPs, Mamba-Branching remains the best neural branching policy, but still inferior to relpscost. For difficult instances, (laabb-Brrnnchhe policies, even surpassing relpscost. This indicates that within the same time limit, Mamba-Branchie enables the fastest convergence of primal and dual bounds. Compared to MILP-S, demonstrates more pronounced improvement over the previous best neural branching method (on solving time, 17% in MILP-L vs. 2% in MILP-S). Since MILP-L contains more test instances (57 vs. 8), the more substantial improvement by Mamba-Branching more clearly demonstrates its advantages from statistical perspective. Furthermore, the violin plot in Figure 4) intuitively illustrates the distribution density of the solving time and presents the quantile information (e.g.. for Mamba-Branching Branching, 75% of the instances are solved in 390.8 seconds). Mamba- Mamba-Branching achieves the lowest time at the 25th, 50th, and 75th percentiles, demonstrating superior and consistent performance across all difficulty levels. This indicates that its lower geometric mean results from robust, balanced improvements throughout the benchmark, not just few outliers. More statistical analysis show the advantages of Hamba-Branching the performance of Mamba-Branchine on more difficult instances, we have conducted a set of supplementary experiments testing on all difficult instances from the MIPLIB 2017 benchmark set that begin with the letter 'r'. Additional details are provided in AAppendix I
the PD integral with 1-hour time limit as the evaluation metric. The
achieves the best PD integral performance among all branching
detailed in Appendix G] To further validate
We also conduct a of auxiliary verification experiments under homogeneous scenario. Specifically, all training and testing in- stances are Set Covering, with only the parameters differing (Table 3). The results indicate that Mamba- Mamba-Branching requires more nodes but achieves a shorter solving time compared to relpscost. demon- strates that, in terms of solving efficiency, Mamba-Branchinn which uses relpscost as an expert- has the potential to surpass it. Furthermore, since heterogeneous scenarios inherently more challenging than homogeneous ones, Hamba-Branching 's superiority over relpscost on difficult instances (despite being worse on easy ones) highlights its substantial promise and importance.
Table 3: Auxiliary verification results Set Covering.
Mamba -Branching
Method
TreeGate relpacost
Nodes
265.07
280.38
170.81
Fair Nodes
265.07
280.38
170.81
Time
9.64
9.89
11.96
5.3 DISCUSSION
Advantage of Sequential Nature. First, T-Bran'T across all scenarios due its consideration of the sequential nature of B&B trees. Neither TreeGate (which completely ignores historical data) nor T-BranT (which utilizes historical data non- sequentially) achieves the effectiveness of sequential historical data utilization. This aligns with our maze analogy subbecctn 4.2 sequentially recalling paths facilitates better current decision-making.
consistently outperforms TreeGate and
Limitation of Transformer. Transformer-Branchhngg also leverages sequential nature but performs poorly, with Transformer- Bereffrmmer-Bracchnngg Branching-p even underperforming the bound pscost. The subop- timal performance stems from its 10-step branching history limit during training (due to hardware constraint), while Mamba-Brann Branching accommodates 100 steps. Furthermore, the inference time
8

---

Published as a conference paper at ICLR 2026
expert
expert
Mannba
2272
1.*
Cal Cu
2001
300
(log)
10
75%: $33.0
75%: 390.8
75% 855,9
Hambe
(61)
4267
200
i
228.3
5138
50%:
50%: 140.3
25%: 83.5
25.:48.2
Hombe Brace
pradhing-
5994
-200
104
Treedate Mamba- Branchhnng T-BranT
1000 2300 30.00 4000
Nodes
5000
300
Method
Figure 4: The violin plots for time on the easy instances in the MILP-L.
Figure 5: Ablation study results for the Mamba-Branchin Branching archi- tecture on MILP-S.
Figure 6: At a random given state, the embeddings with and without contrastive learning.
comparison in Figure 3 demonstrates that in our time- sensitive scenario aimed reducing solving time, Transformer is entirely unsuitable as a branching policy. The underlying reason here is that Transformer's complexity is quadratic with respect sequence length, while Mamba's 's is linear. Although Transformer is theoretically suitable as sequence model, employing Mamba offers greater practicality and feasibility. A more detailed comparison can be found in Appendix
Factors Outperforming Relpscost. As for relpscost, BaabaaBraanchiggg does not outperform in easy instances but surpasses it in difficult ones. The reason can be summarized as follows: (1) Relpscost is hybrid method combining strong and pscost branching. incorporating reliability criterion: variable can only switch to pscost after being selected by strong branching a certain number of times. Therefore, for difficult instances with more variables, the initialization process is time-consuue timecconuumin, leading to potential inefficiency. In contrast, neural policies benefit from fast inference and exhibit advantages difficult instances. (2) In relpscost, the of pscost for leveraging historical data does not account for the sequential nature, whereas Mamba- Mamba-Branching explicitly incorporates this consideration. (3) As mentioned in (Zarpellon et al.) (002I) the relpscost in SCIP has been fine-tuned for a large number of instances, resulting in excellent performance on easy instances. However, for more complex and challenging instances, such parameter tuning may not provide adequate coverage.
5.4 ABLATION STUDY
In this section, an ablation study is conducted to quantify the impact of contrastive pretraining: (1) we compare Mamba-Branching- Branching-p with and without contrastive learning isolate CL's contribution to branching performance; (2) we introduce a supervised pretraining baseline Maamaa-ranching-- SL), in which embeddings variables and the prediction head removed prior to downstream use. It serves as a discriminative representation learning alternative to CL; (3) we remove the positional encoding to highlight the effect of sequence modeling (Mamba-Branching Branching-p w/o PE); and (4) in addition to the Transformer, we also employ GRU the sequence model
p w/o CL) to
optimized via classification of expert-selected
Results on MILP-S reported in FFigure To validate CL's efficacy in enhancing embedding separability, we visualize learned representations via t-SNE (van der Maaten & Hinton, 2008) in Figure 6 We have also further investigated the impact of different forms of contrastive loss functions on the performance of Mamba-Branching as detailed in Appendix J
In terms of branching performance, Mamba-Branching. significantly outperforms both its CL- ablated variant (w/o CL) and the supervised baseline (SL). While supervised learning offers a conceptually straightforward alternative. it proves insufficient for inducing embeddings that generalize effectively to the branching task. After removing the positional encoding of Mamba-Brand Branching, the performance drops significantly, which underscores the importance of sequential modeling and aligns with the original motivation for proposing Mamba- -aanba-Branchig.. Meanwhile, replacing the sequence model with either a GRU or a Transformer yields poor results, demonstrating the necessity of Mamba as the sequence model. Visualization via t-SNE further corroborates the necessity of contrastive pretraining. Under CL, embeddings of expert-selected variables exhibit greater separation and outlier-like distinctiveness relative to candidate variables. In its absence, these embeddings collapse toward the distribution of non-expert candidates, losing discriminative structure.

---

Published as a conference paper at ICLR 2026
6 CONCLUSION AND FUTURE WORK
In this paper, we propose Mamba-Branching Branching, the first approach to consider the sequential nature in B&B trees. To address the challenges long sequences and embedding distinctiveness posed by sequential nature, we employ Mamba the sequence model and design a contrastive learning method to train the embedding layer, enabling the sequence model to distinguish between different candidate variables. In experiments, Mamba Branching outperforms all neural branching policies and achieves superior solving efficiency compared to relpscost on challenging instances. One limitation of our approach is the reliance imitation learning, which requires time-consuming collection of expert demonstrations. future work, we will focus on investigating the potential of sequential nature in reinforcement learning-bas based branching policies, thereby eliminating the dependency on expert data.
ETHICS STATEMENT
Our work does not involve any human subjects, animal experimentation, or the collection/use of personal data. We have reviewed the ICLR ethics guidelines and confirm that this submission raises no ethical concerns.
REPRODUCIBILITY STATEMENT
We provide the following information, which is sufficient to support the reproducibility of Mamba- Branching. The specific methodology is detailed in secciinn 4| and the proof of Proposition I is provided in Appeendix A] In the experiments, the details of the benchmarks are described in sub subsection 5.1.1 and Appendix D), while hyperparameters and implementation details are provided infsusuussettion 5.1.3 and Appendix F The source code of Mamba- Baarbb---rachingggg and the datasets used can be found in https: /tt::///gttttte com /wc/ootctoooo/ooooooooo/ son 6/Mamba Branching/
REFERENCES
Tobias Achterberg. Seip optimization suite documentation: Reliable pseudo costs branching rule.
SCIP Optimization Suite Documentation, 2025. URL httpt:t///// /ttttss///ww... //www/ scipopt. org /oc/
html http//bbanhh___ee____
8h. php. Accessed: 2025-04-27.
Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33(1):42-54, 2005.
Cynthia Barnhart and Gilbert Laporte. Handbooks in operations research and management science: Transportation. Elsevier, 2006.
Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. A neural probabilistic language model. In T. Leen, T. Dietterich, and V. Tresp (eds.), Advances in Neural Information Processing Sys- tems, volume 13. MIT Press, 2000. URL http:///////////peee.......oaaaa
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: methodological tour d' h'horizo.. European Jourmal of Operational Research, 290(2):405-221, 2021. ISSN 0377-2217. doi: http:://oo..ag///o..oooo.oooooot
063. URL httpsttss:/ /www
sciencedirect htt.a///cs.................aeaaa
Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionísio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammed Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Dominik Kamp, Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, Erik Mühmer, Mare E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, and Lixing Xu. The SCIP Optimization Suite 9.0. Technical report, Optimization Online, February 2024. URL bt wtt.s:tpptoooooo.....e. /tt.sttt////ppiiaaaat 2024/02/the-2 www.thhhhsssspstteeeeeeeeopoppee im zat on- su 1e--tte-9-
onl /rg/
10

---

Published as a conference paper at ICLR 2026
Zhi- Zhi-Long Chen. Integrated production and outbound distribution scheduling: review and extensions.
Operations research, 58(1):130-144 2010.
Tri Dao and Albert Gu. Transformers are SSMs: Generalized models and efficient algorithms through structured state space duality. In International Conference on Machine Learning (ICML), 2024.
Jian- Ya Ding, Chao Zhang, Lei Shen, Shengyin Li, Bing Wang. Yinghui Xu, and Le Song. Accelerating primal solution findings for mixed integer programs based on solution predic- tion. Proceedingy of the AAAI Conference Artificial Intelligence, 34(02):1452-1455) Apr. 2020. doi: 10.1609/aaii
V3..1600/ai..444055555550 v34102.5503, URL http:/tttt////o/tt... aaai, org/ index php/AAAI/
article/view/5500
Gerald Gamrath and Christoph Schubert. Measuring the impact of branching rules for mixed-intege programming. In Natalia Kliewer, Jan Fabian Ehmke, and Ralf Borndörfer (eds.). Operations Research Proceedings 2017, pp. 165-170, Cham, 2018. Springer International Publishing. ISBN 008-3-339-89920--5
Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combi- natorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019.
Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurcolent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M. Kazachkov, Elias Khalil, Pawel Lichocki, Andrea Lodi, Miles Lubin, Chris J. Maddison, Morris Christopher, Dimitri J. Papageorgiou, Augustin Parjadis, Sebastian Pokutta, Antoine Prouvost, Lara Scavuzzo, Giulia Zarpellon, Linxin Yang, Sha Lai, Akang Wang, Xiaodong Luo, Xiang Zhou, Haohan Huang, Shengcheng Shao, Yuanming Zhu, Dong Zhang, Tao Quan, Zixuan Cao, Yang Xu, Zhewei Huang, Shuchang Zhou, Chen Binbin, He Minggui, Hao Hao, Zhang Zhiyu, An Zhiwu, and Mao Kun. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In Douwe Kiela, Marco Ciccone, and Barbara Caputo (eds.), Proceedings of the NeurlPS 2021 Competitions and Demonstrations Track, volume 176 of Proceedings of Machine Learning Research, pp. 220-231. PMLR PMLR, 06-14 Dec 2022. URL ptttps://prooeeednngg mlr. wtt.ppess/v166/gss2222222
Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt. Ted K. Ralphs, Domenico Salvagnin, and Yuji Shi- nano. MIPLIB 2017: Data-Driven Compilation of the 6th Mixed-Integer Programming Library. URL
Mathematical Programming Computation, 2021. doi: 10. 020-00194-3
https:://do or orw.or..gg.... 1001
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. In First Conference on Language Modeling, 2024. URL http:ttpps///opeeeeeeeeeeeete//s htwp:///wwwwweeeeeoouoummmaa
EEYskw1VY2
Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigonda, Andrea Lodi, and Yoshua Bengio, Hybrid models for learning to branch. Advances in neural information processing systems, 33: 18087-18097, 2020.
Prateek Gupta, Elias Boutros Khalil, Didier Chételat, Maxime Gasse, Andrea Lodi, Yoshua Bengio, and M. Pawan Kumar. Lookback for learning to branch. Transactions on Machine Learn- ing Research, 2022. ISSN 2835-8856. URL htttps://opereeeeet net hwt.roormmddd EQpGkw5rvL Expert Certification.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL httpp::/ww/t /www gurobi com
Qingyu Han, Linxin Yang, Qian Chen, Xiang Zhou, Dong Zhang, Akang Wang. Ruoyu Sun, and Xiaodong Luo. A GNN-guided medict-and--eaarc framework for mixed-integer linear program- ming. In The Eleventh International Conference on Learning Representations, 2023. URL httpss//cppnrevii net http:e/e//oorrmmiiiiiiiporrssss

---

Published as a conference paper at ICLR 2026
He He, Hal Daume III, and Jason M Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Wein- berger (eds.), Advances in Neural Information Processing Systems, volume 27. Curran Asso- ciates, Inc., 2014. URL.ttps: / neuri cc/ppprr fi www.f/leppppppe /spppprr/
Taoan Huang. Aaron Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'22. JMLR.org. 2023.
Taoan Huang, Aaron M Ferber, Arman Zharmagambetov, Yuandong Tian, and Bistra Dilkina. Contrastive predict-and-search for mixed integer linear programs. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp (eds.), Proceedings of the 41st International Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 19757-19771. PMLR, 21-27 Jul 2024. URL https://prroceeiingg mlrr www.ppess/se..p.p maress/v235/huueee http2/3//uuagg22.... html
Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Weinan Zhang. Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning select for efficient mixed-integer programming. Puttern Recognition, 123:108353, 2022. ISSN 0031-3203, doi:
10835.. URL https:/ www. www.ecceiieet.ccoo.o.oooo com/ wtt.///iieecce//rrreee/////////e
0003132032100530
R. E. Kalman. new approach to linear filtering and prediction problems. Journal of Basic
Engineering, 82(1):35 45, 03 1960. ISSN 0021-9223. doi: 10.1115/1.11 (0.1115/1.366252 URL https!
7/doi oagi.org//10 10. 1111 366552.3662552
Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Feb. 2016. doi: 10.1609/aaii.v3000 v30i 10080. |tttttss:://ojs aaai www.aaaraaaaaaaaaaaaaaaaaaeeeeea wwwgg/nnex... php/ AAAT/ AAAL/atticle/vLew/DDO0
Elias Khalil, Christopher Morris, and Andrea Lodi. Mip-gnn: A data-driven framework for guiding combinatorial solvers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 10219-10227, 2022.
Yufei Kuang, Jie Wang, Haoyang Liu, Fangzhou Zhu, Xijun Li, Jia Zeng, Jianye HAO, Bin Li, and Feng Wu. Rethinking branching on exact combinatorial optimization solver: The first deep symbolic discovery framework. In The Twelfth International Conference Learning Representations, 2024a. URL
net forum -idnnnndddddKnBn NMh
Yufei Kuang, Jie Wang, Yuyan Zhou, Xijum Li. Fangzhou Zhu, Jianye HAO, and Feng Wu. Towards general algorithm discovery for combinatorial optimization: Learning symbolic branching policy from bipartite graph. In Forty-first International Conference on Machine Learning, 2024b. URL forum? 11w.mmmm1dd111111eeaaaaa
htttps://openreviie net htt.:
Abdel Ghani Labassi, Didier Chételat, and Andrea Lodi. Learning compare nodes in branch and bound with graph neural networks. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL https::/openne
net wwtp:/neeettnnotiiie.e... /ttp://mmmi--ooh//e.....
Ailsa H Land and Alison G Doig. An automatic method for solving discrete programming problems. Springer, 2010.
Lehigh University COR@L Lab. Mixed-integer programming benchmark instances, n.d. URL https: coral ise. wew.ehgh.eee.aaaaasstts////meeee ittp::ewwddddeeeeeeeeeeeeeeeeeee Accessed: 2025-4-30.
Sirui Li, Janardhan Kulkamni, Ishai Menache, Cathy Wu, and Beibin Li. Towards foundation models for mixed integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025. URL wtl.hhttpss//peeerriiieeeeeeeeep
12

---

Published as a conference paper at ICLR 2026
Jiacheng Lin, Jialin Zhu, Huangang Wang, and Tao Zhang. Learning branch with aware
branching transformers. Knowledge-Basee Systems, 252:109455, 2022. ISSN 0950- doi:
bttt::/::://// htt.://ww.............o///..eee. http://wwwwwcccncierrttttte com/
sci accieenc//arrtccle///////533/112 220077229
Haoyang Liu, Yufei Kuang. Jie Wang, Xijun Li, Yongdong Zhang, and Feng Wu. Promoting
generalization for exact solvers via adversarial instance augmentation, 2023. URL https
//arxiv.org//bb//311.0..
Haoyang Liu, Jie Wang. Zijie Geng, Xijun Li, Yuxuan Zong, Fangzhou Zhu, Jianye HAO, and
Feng Wu. Apollo-MILP: An alternating prediction-correction neural solving framework for mixed-integer linear programming. In The Thirteenth International Conference on Learning Representations, 2025. httpp::/opeereeiieeeee/// wwwpp//pppe.eeeeeoopepeee net. woweee/oooumnnddnnoee-eee.
Tomas Mikolov, Πly Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahra- mani, and K.Q. Weinberger (eds.), Advances Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL httpp::/ htt.://eeeeessro..rr......../.ia www.nneurii.cccoo cc/paerr weeeepaapa
Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O' O'Donoghue, Nicolas Sonnerat, Christian jaadraaataajaa Pengming Wang, Ravichandra Addanki, Tharindi Hapuarachchi, Thomas Keck, James Keeling, Pushmeet Kohli, Ira Ktena, Yujia Li, Oriol Vinyals, and Yori Zwols. Solving mixed integer programs using neural networks, 2021. URL
https://arxiv org/ awtp/ass...... 13349
Yves Pochet and Laurence A Wolsey, Production planning by mixed integer programming, volume 149. Springer, 2006.
Lara Scavuzzo, Feng Chen, Didier Chetelat, Maxime Gasse, Andrea Lodi, Neil Yorke- Smith, and Karen Aardal. Learning to branch with tree mdps. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp. 18514-18526. Curran Associates, Inc., 2022. URL htttpss:/ wwwp:iiinnnnnnuuuureeeeeeeee neur www.eerrsss.cpppppeeeeeeeeeeeeee wwtpppppppppppeeteetteeteee...ep F1le/75647cc33322222002222222222 Conprapeeeeettaaaaeeeeeereerrrer pdff
Lara Scavuzzo, Karen Aardal, Andrea Lodi, and Neil Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming. Mathematical Programming, pp. 1-44, 2024.
Nicolas Sonnerat, Pengming Wang, Ira Ktena, Sergey Bartunov, and Vinod Nair. Learning large neighborhood search algorithm for mixed integer programs, 2022. URL htttps://arx: org/ abg//bb//at 2107 10201
Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer programming: learning to cut. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JM.R. 2020.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Ma- chine Learning Research, (86) 2008.
//mlr. prg/papers//99
Vandermaaten08e: htm
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention all you need, I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL Ltt.tteeee//pooeeeeesse...ooooo.
wttp://wwwdinnn....ei.u.......ee ptppuripss.cpppppppeee files//aper/2017 File Tttee/ffoe2233//eeeel0003daaaaee Paap:0033....0...aaaeeeee.eee.r
Xiao Wang, Shiao Wang, Yuhe Ding, Yuehang Li, Wentao Wu, Yao Rong, Weizhe Kong, Ju Huang, Shihao Li, Haoxiang Yang, Ziwen Wang. Bo Jiang, Chenglong Li, Yaowei Wang. Yonghong Tian, and Jin Tang. State space model for new new-generation network alternative to transformers: A survey, 2024. URL hattpe///aaxii.oorr/abb//222 09516
13

---

Published as a conference paper at ICLR 2026
Zhihai Wang. Xijun Li, Jie Wang, Yufei Kuang. Mingxuan Yuan, Jia Zeng. Yongdong Zhang, and Feng Wu. Learning cut selection for mixed-integs linear programming via hierarchical sequence model. In The Eleventh International Conference Learning Representations, 2023. URL
/ttp:///ppeeeeieeee net forum? 3 dew.d=/724bPbrrr.
Yaoxin Wu, Wen Song, Zhiguang Cao, and Jie Zhang. Learning large neighborhood search policy for integer programming. A. Beygelzimer, Y. Dauphin, P. Liang, and Wortman Vaughan (eds.).
Advances in Neural Information Processing Systems, 2021. URL
net/forum?id--aMTTUA
Hao Yuan, Wenli Ouyang, Changwen Zhang, Yong Sun, Liming Gong, and Junchi Yan. BTBS-LNS: Binarized-tiggtennigg branch and search learning LNS policies for MIP. In The Thirteenth International Conference on Learning Representations, 2025. http::ttttp/peeeeeeeeso
f d= HHt HHgDZzv
Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and-bound search trees to learn branching policies. Proceedings of the AAAI Conference on Artificial Intelligence, 3565)33931-3939 May 2021. doi: 10.1609/uaii.v33 v35i5.16512. URL https:
1/o aaai. www.orgg....... index.ndxxxx..///mm php/ AAAT/AAAa TA.T/arric. eeveeeiviie ew/16512
Sijia Zhang, Shuli Zeng. Shaoang Li, Feng Wu, and Xiangyang Li. Learning to select nodes in branch and bound with sufficient tree representation. The Thirteenth International Conference on Learn- ing Representations, 2025, URL URL
net forum 2id=gyv'KLEmät
14

---

Published as a conference paper at ICLR 2026
A LNTUITIVE UNDERSTANDING AND PROOF OF PROPOSITION 1
To further clarify the connection between Proposition 1 and contrastive learning approach, well as the role of Proposition D an intuitive explanation from the conceptual standpoint; second, an attempt provide an explanation using mathematical formulations.
in our methodology, we provide explanations from two perspectives: first,
First, we make the following two assumptions, which will serve the foundation for our subsequent analysis:
1. The feature embeddings of the optimal branch decision variable (ef)) can be distinguished from those of other branch variables (ej, Vi C, i + a) in the vector space.
2. The feature embedding e, is informative for branch decision decision-making.
A.1 INTUITIVE EXPLANATION
Based on assumption I_ we establish an anchor point et" and employ contrastive learning to train model such that: (T) the optimal branch variable's s feature of pulled closer to ez", while (2) other variables' features are pushed away from et". This approach amplifies the separation between optimal and non-optimal features, thereby ensuring sufficient distinguishability when these features subsequently processed by the Mamba architecture.
A.2 MATHEMATICAL FORMULATIONS
For each branching variable i, we define F(i) as the branching score function (in this paper, the relpscost score) for variable i, such that the optimal branching variable satisfies
arg max F(i).
(6)
Assumption 2 posits that the embeddings can encode branching quality information, which we simplify to a linear relationship:
aF(i G,
where Rd is variable independent vector representing the quality sensity-en direction in the embedding space. e, E Rd a noise term satisfying E(e,) with small magnitude Jei]-
We max pooling over the embeddings the anchor point, defined as:
= [..,, max (()), .-= = [..,, max(((i))())++++++ + +())....
(8)
For et, we have:
et [..., max F(i)a() cc.())
(9)
Indeed, if we assume that all e; terms are sufficiently similar in magnitude, we can derive the approximation ef = e!". Therefore, we can reasonably establish that
Vi + a, sim(e?, > sim(ei, e?))
(10)
This formulation is mathematically equivalent the expression presented in Proposition I
Vt, 38 > 0 s.t. sim(e?, e(r) > max sim(et, e(")
(11)
ipa
The proof effectively reflect the underlying intuition behind our design: to make the optimal variable's features closer to the anchor point while pushing other features farther away, thereby making the optimal variable's features more distinctive in the vector space.
15

---

Published as a conference paper at ICLR 2026
B MAMBA ARCHITECTURE
Mamba is novel network architecture based on State Space Model (SSM) that may potentially replace dfffaattenioonbaaee Transformer models (Gu & Daoj [024 Dao & Gu 2024 Wang et al.) 2024). SSM is concept originating from control theory, with its earliest roots traceable to the
classical Kalman filter (Kalman 1960p. The continuous-time formulation of SSM can represented
as follows:
2(1) M())((() N(()(())
(12)
(() = ((t)z((),
where x(1) E RR. R9, u(() IR. After zero-order hold discretization, the discrete-time formulation is obtained as follows:
2. = Mz.1 Nu,
(13)
Yt Pzı,
where M = exp( N = (AM) (exx((MeeMMM)))) I) AN, A denotes the step size.
To meet the parallelization requirements of the training process, the SSM can alternatively be represented as follows:
== = IPN,PMM PM'N)
(14)
y K
Mamba builds upon SSM by introducing Selective SSM, which essentially treats N. P and A as functions of the input while keeping M unchanged. From a control theory perspective, this transforms the system from time-invariant to time-varying. Furthermore, Mamba incorporates hardware- algorithm design that enables efficient storage of intermediate results through parallel scanning, kernel fusion, and recalculation.
C REASONS FOR EMPLOYING RELPSCOST AS THE EXPERT
First, as mentioned in the original texts of (Zarpellon et al. 2021 and (Lin et al. 2022). strong branching rarely applied in practical scenarios, and relpscost provides a more realistic expert representation. However, the rationale for selecting relpscost as the expert is not limited to this point alone. Here, we further analyze and present additional reasons necessitating the choice of relpscost as the expert.
The application scenario of our work differs fundamentally from that of GCNN: while GCNN focuses training and testing on homogeneous instances, method specifically targets testing on completely heterogeneous instances, emphasizing the generalization capability the branching policy. Therefore, emphasize that approach fundamentally relies the TreeGate neural network architecture and feature design specifically tailored for generalized branching policies. Under this framework, experimentally validate the necessity of using relpscost the expert policy and provide thorough analysis of the underlying rationale.
C.I COMPARATIVE EXPERIMENTS
Under TreeGate, we train policies using both strong branching and relpscost as experts, with results in Table 4 The results demonstrate that under the TreeGate framework, imitating strong branching achieves significantly lower accuracy compared to imitating relpscost. Meanwhile, on test instances, the policy imitating relpscost shows clearly superior performance.
C.2 ANALYSIS AND CLARIFICATION
TreeGate emphasize incorporating rre-search-related features into the design without focusing on specific instances, while pseudo-costs align with the requirements of tree search by leveraging historical information. And relpscost essentially represents an improved form of pseudo-cost that incorporates historical strong branching experience.
16

---

Published as a conference paper at ICLR 2026
Table 4: The imitation learning results using TreeGate as the network framework, with strong branching and relpscost serving as the experts respectively. The training was conducted for 50 epochs in all cases. The table reports the final network's loss and accuracy on both the training and test sets, as well as the solving time performance on test instances from (Zarpellon et al. 2021).
Train Loss
Test Loss
Train Accuracy
Test Accuracy
Solving Time
Method
TreeGate + Relpscost 0.9954
0.9907
0.7453
0.7561
137.41
TreeGate + Strong Branching
2.1845
2.5912
0.3590
0.2465
512.32
The features capture imperfect pseudo-costs while the relpscost labels contain refined pseudo-coste The neural network learns to transform pseudo-costs from imperfect to refined versions. The feature design inherently results in better compatibility between TreeGate and relpscost, which consequently leads to the failure of TreeGate + strong branching.
Moreover, relpscost outperforms strong branching in terms dataset collection speed. Although compared to the fundamental limitations strong branching, this advantage might be relatively less significant.
D BENCHMARK DETAILS
All training and test instances in MILP-S are listed in Table 20 presented in Table 21 All easy test instances in MILP-L are shown in Table 22] while all difficult test instances are presented in Table 23 Here, an instance is considered easy if SCIP's solving time less than 20 minutes; otherwise,
The training instances in MILP-L are
classified difficult. These instances are sourced from MIPLIB Gleixnnr et al. (02T)) and CORAL (Lehigh University COR@L Lab n.d.). all collected from real-world application scenarios, with specific instance selections referenced to (Zarpellon et al., 2021) and (Lin et al. 2022). Serving as benchmarks, these instances effectively reflect the practical significance of neural branching policies in real-world applications.
Actually, apart from the instances already present in (Zapellon et al. 2021 and (Lin et al. 2022). we have only added 8 new challenging instances, all of which belong to the MILP-L. The criteria for selecting these eight challenging instances is as follows:
1. Instances marked as "hard" in the MIPLIB 2017 benchmark (Gleixner et al. 2021
2. Instances with known optimal solutions and not infeasible, which can provide cutoff values.
3. A large number of nodes (>100) within the 1-hour time limit: If the number of nodes too small, the time spent on solving the relaxed LP problem becomes excessively large. In such cases, the impact of branching rules may be negligible, making these instances unsuitable for comparing different branching policies.
4. The number of variables should be between 100 and 200k: For branching variable selection, larger number of variables increases the difficulty of the selection. Therefore, the lower bound is set to 100 variables to sufficiently evaluate branching policies. However, if the number of variables is too large, all branching policies may perform poorly within the 1-hour time limit, making it impossible to distinguish their performance; hence, the upper bound is set 200k.
Actually, in the MIPLIB 2017 benchmark set, there are only 19 instances labeled as "hard". After applying the aforementioned criteria for filtering, a total of 8 instances remain usable, and we have included all of them in MILP-L. Detailed information about these 19 hard instances-inchudinn the number of variables, objective value, and Nodes (within a 1-hour limit)-is provided in Table
E DETAILED REASONS FOR BASELINE SELECTION
The neural branching policies and their selection rationale are detailed below: (1) GCNN (Gasse al. 2019) : This method is not designed for heterogeneous MILPP and performs poorly on unseen
17

---

Published as a conference paper at ICLR 2026
Table 5: Information for all instances labeled as "hard" in the MIPLIB 2017 benchmark set. The details include: the objective value, the number of variables, the solving time and number of nodes using SCIP under 1-hour time limit, and whether each instance was selected for MILP-L. For those not selected, the reason for exclusion is provided in the note.
Instances Name
Ohjective
Variables
SCIP Time
Nodes
Note
bab2
3357544.1155 -284248.2307
147912
3600 3600
251.6
In MILP-L In MILP-L
bab6
114240
5U2.6
cryptanalysisk
Infeasible
48950
Infeasible
b128n5obj14 14
highschool1
The number of variables exceeds 200k
0
320404
-aigio
The number of variables is fewer than 100
markshare2
1
74
neos-3402454
Infeasible
2904
Infeasible
-bohle
neos-3656078
The number of nodes is fewer than 100
-13172.2
14870
3600
57.6
-kumeu
neos-4338804
1471
1344
3600
201684.2
In MILP-L
-snowy
neos-4387871
33.38472993
4004
3600
6871.6
MILP-L
-tavua
neos-4647030
776
12600
3600
7000.6
In MILP-L
-tutaki
ncos-5104907
The number of
935
345856
-jarama
variables exceeds 200k
ncos-5114902
The number of variables exceeds 200k
655
710164
-kasavu
nursesched
115
34248
3600
483.4
In MILP-L
-medium-hint03
opm2-z110s4
-33269
6250
3600
101.4
In MILP-L
radiationm40
155328
172013
3600
29963.6
In MILP-L
-10-02
The number of variables exceeds 200k
s100
-0.
-01669733227
364417
The number of nodes is fewer than 100
supportcase10
7
14770
3600
The number of variables exceeds 200k
supportcase19
12677206
1429098
The number of nodes is fewer than 100
thor50dday
40417
106261
3600
MILP instances outside the training distribution. The experimental results of GCNN highlight the advantage of ceettancc-indppendeed feature design in terms of generalization. (2) TreeGate (Zarpeloon) et al. ) The TreeGate network incorporates instance-independenl inputs by design, making 's embedding layer adopts the TreeGate architecture, TreeGate serves as a critical control group for our method. (3) T-BranT (Lin et al.] 2022): Building upon TreeGate's feature design, T-BranT employs attention to capture mutual connections among candidates. Meanwhile, T-BranT processes historical data from an unordered graph perspective. The comparison with T-BranT serves to evaluate whether Mamba-Brane Brabbbhi-annhng's sequential processing of historical data demonstrates superior performance over T-Bran''ss unordered graph approach. (4) Transformer- Transformer-Branchingg When selecting sequence model for our approach, the Transformer would naturally be the most immediate consideration. Thus, we include Transformer- Branhchin-Bannnnggg as comparative baseline against Mamba- crannbbaBrraching. specifically to highlight the advantages of employing Mamba as the sequence model.
suitable for heterogeneous MILPs. Additionally, since
The heuristic rules are selected with the following rationale: (1) Random: Serves the performance lower bound, demonstrating the detrimental effects of completely omitting a deliberate branching policy. (2) Pscost: A purely historical data-driven branching method that, like Random, also establishes a performance lower bound. (3) Relpscost: The expert policy in the imitation learning of Mamba- Brabba-rannchig.. Simultaneously, it is also the SOTA heuristic rule and the default rule in SCIP.
18

---

Published as a conference paper at ICLR 2026
Table 6: The hyperparameters of Namba-Branching
Name
Description
Value
Output dimension of the candidate net in TrecGate, which is equivalent to the embedding size of Mamba.
Hidden state dimension of the Candidate Net in TreeGate. Layer number of Tree Net in TreeGate. Batch size of Mamba Training
64
depth
batch_siiie size lr_cl
32
Learning rate of contrastive learning.
0.0001
optimizer_cl _c
Optimizer of contrastive learning.
Adam
Learning rate of imitation learning.
0.001
optimizer
Optimizer of imitation learning.
Adam W
wd
Weight decay coefficient of imitation learning.
0.01
T train
Maximum branching steps considered during training.
99
T __av
Maximum branching steps considered during evaluating.
24
d_ state
SSM state expansion factor in Mamba
64
d_conv expand
Local convolution width in Mamba
Block expansion factor in Mamba
2
Relpscost serves the upper bound of decision accuracy for neural branching policies. However, benefiting from the fast inference speed of neural networks, neural branching policies may surpass relpscost in terms of efficiency.
F IMPLEMENTATION DETAILS
All experiments this paper are run on NVIDIA A100-PCIE-40GB GPU and Intel(R) Xcon(R) Gold 5218 CPU. The hyperparameters in the training of camba-Branching are shown in Table 6
During training, sequences consisting every 100 branching steps are fed as input to Mamba. We systematically evaluate Mamba- Branbbb-Banchngggg with varying branching path lengths during training, as shown in Table 7 The results reveal clear performance peak = 99. Shorter sequences under- utilize the sequential information in B&B trees, while longer sequences exceed Mamba's effective processing capacity given our parameter constraints. Unlike standard Mamba implementations with small embedding size (8) to prioritize inference speed-this design choice necessitates the optimal T=99 configuration.
large embeddings (> 768), deliberately
During inference, the sequence fed into Mamba consists of: (1) states and predicted actions from the most recent 24 branching steps, and (2) the current state. We provide experimental results for step numbers of 5, 13, 25, 50, and 100, shown in Table 8 As be observed: Sequence length grows substantially with path length, reaching 14,412 tokens at 100 denos-ddmmtstraiingg why Mamba's linear complexity is essential for this task. 2) Node count exhibits U-shaped curve: initially decreases as longer contexts help the model better capture the sequential structure of the B&B tree, but then increases due егтог accumulation under autoregressive inference, where predictions from previous steps are fed into subsequent steps. 3) The impact on solving time is more complex: depends not only on the node count which reduces LP computations. but also on the inference time, which rises as more real tokens are processed. Under the joint influence of these two factors, a branching path length of emerges as the optimal choice, achieving shortest total solving time.
G ADDITIONAL STATISTICAL RESULTS
Since the test instances we use are entirely different, and the solving time and node count vary signifi- cantly across instances, the geometric mean is adopted as a metric to mitigate the impact of excessively large or small values to extent. However, evaluate the advantage of Mamba- Mamba-Branching over other baselines on each individual instance, rather than focusing solely on overall performance, more detailed statistical analysis is required. Therefore, further conduct fine-grained analysis of
19

---

Published as a conference paper at ICLR 2026
Table 7: Results of training Mamba- Baanba-Brannhing with varying Branching Path Lengths on MILP-S.
Branching Path Length
Actual Token Num (during training)
GPU Memory (during training)
Nodes
Fair Nodes
Time
(T)
10 (9)
2159.42
2188,49
118.09
2743.77
1.22 Gb
100 (99)
2068.83
2091.54
111.78
30667.39
7.94 Gb
200 (199)
3033.1
3085,48
164.28
63592.31
16.25 Gb
500 (499)
3575.88
3628.76
168.74
158533.33
35.89 Gb
Table 8: In MILP-S, performance of Branbbb-BBncinngggg and the actual number of tokens input to the Mamba model under different branching path lengths (number of steps: 5, 13, 25, 50, 100). For the metric 'real token num', we report the geometric mean over all instances of the maximum number of tokens required for each instance throughout the solving process.
Branching Path Length
Nodes
Fair Nodes
Time
Actual Token Num
2103.59
2126.81
111.97
986.1
13
2098.94
2120.28
113.05
2333.78
25
2068.83
2091.54
111.78
4132.02
50
2032.14
2054.39
112.77
7724.77
100
2091.46
2113.88
121.98
14412.15
Mamba-Branchin on each instance through quartile tables, violin plots, win/tie/loss statistics tables, and significance testing.
G.1 QUARTILE TABLES AND VIOLIN PLOTS
For neural branching policies, quartile tables and violin plots for time and nodes shown in ble T[able 10 Figure Figure 8, respectively. They convey similar information: for example, Klamba-Branchin achieves the time of 140.33 at the 50% in Table 9 meaning that 50% of the in- stances have solving time within 140.33. Additionally, violin plots intuitively illustrate the distribution density of the data across different values.
As shown, Mamba-Bran Baanba-Bannching attains the smallest time and node count at the 25th, 50th, and 75th percentiles, indicating consistently superior performance across all difficulty ranges compared to the other two methods. This suggests that Mamba-Branchin lower geometric mean is not due to exceptional performance on a few extreme instances but rather stems from robust and balanced improvements across the entire benchmark.
G.2 WIN/TIE/LOSS STATISTICS TABLE
In the win/tie/loss statistics table, present the pairwise win/tie/loss outcomes between each method across all instances. For each instance, we consider the median value across five seeds. The results for the easy instances and difficult instances of MILP-L are shown in Table Table 12 Table 13
It can be observed that Mamba- Brabba-Branching outperforms both TreeGate and T-Bran'T on both easy and hard instances, while also achieving superior performance finding aligns with the original conclusions presented in the main text.
relpscost on difficult instances. This
G.3 SIGNIFICANCE TESTING
Here, we employ the Friedman test with Conover post-hoc analysis to perform significance test- ing. The Friedman test with Conover post-hoc analysis is a non non- non-parametric statistical method for comparing multiple methods across multiple instances, especially when data may violate normality assumptions. Its procedure includes: (1) calculating instance-wiss ranks; (2) conducting the Friedman test for overall significance, and if p<0.05; (3) applying Conover's test for detailed comparisons.
20

---

Published as a conference paper at ICLR 2026
Table For the easy instances in the MILP-L dataset (57 instances, each with random seeds), the quartile table for time. For example, Mamba-Branchinn Branching achieves the time of 140.33 at the 50%, meaning that 50% of the instances have solving time within 140.33. Meanwhile, the solving time contains difficulty information, and from this table, we can observe the adaptability of the method to problems of varying difficulties.
Method
25%
50%
75%
Mamba- BranbbbBrrancing
48.17
140.33
390.84
T-Bran'T
83.54
228.26
855.90
TreeGate
55.22
140.85
617.96
Table 10: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the quartile table for Node counts.
Method
25%
50%
75%
Mamba- Branbbhig
536.0
2505.0
7827.0
T-BranTT
645.0
3109.0
8122.0
TreeGate
911.0
2928.0
8069.0
Following the aforementioned procedure, we conduct overall significance tests on nodes, time, and pd integral, followed by post-hoc tests. The results follows:
1. Friedman test results for nodes (57 easy instances in MILP-L): Test statistic=2.502, valuc=0.2862,, indicating no statistically significant differences.
2. Friedman test results for time (57 easy instances in MILP-L): Test statistic=1 (tattiic=8..00)) p- value=0.0001, indicating statistically significant differences. Conover post-hoc analysis can performed, as shown Table 14
3. Friedman test results for primal-dual integral (16 hard instances MILP-L): Test statis-
tic=8.625, p-value 0.0347, indicating statistically significant differences. Conover post-hoc analysis can be performed, as shown Table 15
On easy instances, in terms of runtime, Mamba- Brabba--Brnchingggg demonstrates statistically significant differences compared to T-Bran'T (p=0.0000144), while showing marginally significant differences with TreeGate (--00071887) For hard instances, Mamba-Branching has statistically significant differences vs. both TreeGate (p=0.01 1501) and T-Bran'T (p=0.007880), but no significant difference vs. relpscost (p=0.1 14340) here, reference to earlier statistical results in Table 13 is needed. This is reasonable its performance advantage over relpscost is smaller than over other methods.
H COMPUTATIONAL COMPLEXITY COMPARISON BETWEEN TRANSFORMER AND MAMBA
As is well-known, Mamba exhibits linear complexity with respect to sequence length, while Trans- former demonstrates quadratic complexity. In this section, we present experimental results that provide detailed comparison of the complexity between Mamba and Transformer when employed as branching policies. Our complexity analysis focuses on two key aspects: space complexity and time complexity. For space complexity, we compare the GPU memory consumption of Mamba and Transformer during both training and inference phases. Regarding time complexity, we primarily ex- amine the inference latency of both models when functioning branching policies. The experimental results are shown in Table 16
As shown in the experiments, when processing 100 branching steps during training (even with batch size 1), Transformer- Transformer-Branchinn fails to train altogether, while Mamba-BB maabb-Brannchng occupies minimal GPU memory. During inference, Mamba Braubba-Branchngg demonstrates significantly lower GPU memory consumption and inference time. In contrast, Transformer-raanchingg Branching not only requires substantially more GPU memory but, more critically, suffers from prohibitively long inference times.
21

---

Published as a conference paper at ICLR 2026
10a
10a
10a
8069.0
time (log)
75% 618.0
75%: 390.8
nodes (log)
10a
50%: 2928.0
25%: 911.0
50%: 2505.0
25%: 536.0
50%: 3109.0
25%: 645.0
50%: 140.9
50%: 140.3
10a
25%: 83.5
25%; 55.2
25%: 48.2
10a
10a
10a
TreeGate Mamba--ranchhin T-BranT Method
TreeGate Mamba- T-BranT Method
Figure 7: For the easy instances in the MILP- dataset (57 instances, each with random seeds), the violin plots for time.
Figure 8: For the easy instances in the MILP- I. dataset (57 instances, each with random seeds), the violin plots for nodes.
Table 11: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the win/tie/loss table for node counts. Since 57 instances too many display their results directly, we use the win/tie/loss format to show the median performance (across 5 random seeds) of different methods various instances when compared pairwise.
TreeGate
Mamba-Branching
T-Bran'T
TreeGate Mamba-Brn Branching T-BranT
24/1/32
30/2/25
32/1/24 25/2/30
33/1/23
23/1/33
Since the fundamental purpose of adopting neural branching policy is accelerate MILP solving, such excessive inference time directly contradicts our original objective.
I MORE CHALLENGING INSTANCES
Here, we selected all instances from the MIPLIB 2017 benchmark set that begin with the letter 'r' and applied filtering criteria similar to our previous approach to identify suitable challenging instances for evaluating Mamba Branching's 's performance.
We would like to emphasize that the selection instances starting with the letter 'r' was solely based their number in MIPLIIBevaluatiin evaluating too many instances would be prohibitively time- consuming, while too few would lack statistical significance. The distribution of instances is independent of their initial letters, which ensures the randomness of our selection. While could have simply randomly sampled from all available instances, such an approach might raise concerns about "cherry-picking" In contrast, the set of instances starting with 'r' is explicitly listed at pntttts:: iib...i.... zib. de / tag Baaaaggee_haaeeeeeee wwn.hharkk html making our selection process entirely transparent and verifiable, as we cannot omit any instances that might be unfavorable to our method.
The criteria for filtering challenging instances are as follows:
1. The solving time greater than 20 minutes.
2. Instances have known optimal solution and must be infeasible, ensuring that cutoff values can be provided.
3. Instances must generate a large number of nodes (>100) within the 1-hour time limit.
4. The number of variables should be between 100 and 200,000.
5. Not included in the training set.
For all instances beginning with the letter 'r', detailed information is provided in Table 17 As shown, total of instances meet our final criteria.
22

---

Published as a conference paper at ICLR 2026
Table 12: For the easy instances in the MILP-L dataset (57 instances, each with 5 random seeds), the win/tie/loss table for time.
TreeGate
Mamba- Haabba-Branchhng
T-Bran'T
TreeGate
23/0/34
37/0/20
Mamba- Braanchng
34/0/23 20/0/37
44/0/13
T-Bran'T
13/0/44
Table 13: For the hard instances in the MILP-L dataset (16 instances, each with 5 random seeds), the Win/Loss table for primal-dua integral.
relpscost
Mamba Mamba-Branching Branching
T-Bran'T
TreeCiate
relpscost
7/0/9
10/0/6
8/0/8
Mamba-Ba Branbbbnn
9/0/7
14/0/2
13/0/3
T- T-BranT
6/0/10
2/0/14
10/0/6
TreeGate 8/0/8
3/0/13
6/0/10
The experimental results for solving these instances using Mamba-Branching and relpscost, respec- tively, are presented in Table 18 Results on the primal dual integral show that Mamba- Baanba-Branchigg outperforms relpscost on majority instances (6 out of and also achieves better overall geomet- ric mean. These results provide further evidence of the superior performance of Mamba- maanbb-Branchingg across a broader set of instances.
FURTHER DISCUSSION ON DIFFERENT CONTRASTIVE LOSSES
While we focus on the novel application of contrastive learning (CL) to branching variable selection, we acknowledge the importance of validating our specific CL design against standard alternatives. Therefore, we conducted additional experiments comparing our CL approach with two widely-used contrastive losses: InfoNCE and Triplet loss. Crucially, we kept identical definitions for anchors (max- pooled candidate embeddings), positive samples (expert-chosed variables). and negative samples (other mannidates)-changiing only the loss function formulation. Results are shown in Table 19
These results demonstrate that our simple contrastive loss outperforms more sophisticated alternatives despite their theoretical advantages. We believe this validates core insight: the primary innovation lies not the loss function design but how we define the contrastive structure for branching decisions. Our contribution is thus conceptual: identify the appropriate elements contrast in the B&B context and provide theoretical justification (Proposition I for this design. This principled approach embedding diseriminability, rather than loss function engineering, constitutes the true innovation of our contrastive learning module.
THE USE OF LARGE LANGUAGE MODELS (LLMs)
In our paper. LLMs are utilized for writing, specifically for polishing the content to ensure standard- ized terminology and fluent writing.
23

---

Published as a conference paper at ICLR 2026
Table 14: Conover post-hoc results for time (57 easy instances in MILP-L). The content of the table p-values; if p-value <0.05, it can be considered that there is a significant difference.
Mamba- Mamba-Branchinn Branching
T-BranT
TreeGate
Mamba-Bres Bonba-Branching T-BranT
1.000000
0,000014
0.07 1.071287
0.000014
1.000000
0.007329
TreeGate
0.071287
0.007329
1.000000
Table 15: Conover post-hoe results for primal-dual integral (16 hard instances in MILP-L).
Mamba-Branching Branching
T-BranT
TreeGate
relpscost
Mamba-Branchin
1,000000
0.011501
0.007880
0.114340
T-BranT
0.011501
1.000000
0,884271
0.310984
TreeGate
0.007880
0,884271
1.000000
0.247731
relpscost
0.114340
0.310984
0.247731
1.000000
Table 16: comparison computational complexity between Mamba- BrabbhBrannchig... and Transformer- Branching. During training, uniformly set T. train=99 with batch size of 1. For inference, consistently use T_eva=24. After collecting 25 Branching steps, we measure the network's 's inference time and GPU memory consumption, take the geometric mean across all test instances of MILP-S.
GPU memory of Train (GB)
GPU memory of Inference Time (s) Inference (GB)
Method
Mamba- Haanba-Branchhng
0.017 out of memory
0.013
0.00093
Transformer Bannfcrmer-BBraachinng
1.051
0.075
24

---

Published as a conference paper at ICLR 2026
Table 17: For instances beginning with 'r', the information of objective, number of variables, number of nodes within the 1-hour time limit, and SCIP solving time. Each instance was evaluated against the aforementioned filtering criteria for identifying challenging instances, and the screening result is indicated in the "Note" column.
Instances Name
Objective
Variables
SCIP Time
Nodes
Note
radiationm
17566
40623
2092.69s
178498
Satisfy
18-12-05
radiationm
155328
172013
3600
24578.8
Satisty
40-10-02
The number of nodes is fewer than 100
rai101
-70.569964
117527
3600
24.6
The number of variables exceeds 200k
rail02
-200.44991
270869
The solving time of is fewer than 20min
rai1507
174
63019
160.55
515
ran14x18
3712
504
3108.4
184547.8
Satisfy
-dij--8
rd-rplusc-21
165395.275
622
3600
113932.4
Satisfy
reblock
-36800603
1150
3600
107606.4
Satisfy
1matr100-p10
423
7359
Included in training set
mmar2200p5
4521
37816
Included in training set
The solving time of is fewer than 20min Satisfy
rocI-4-11
-6020203
6839
279.93
21304.8
roclI-5-11
-6.6755047
11523
3600
66194.4
rococoB10
19449
4456
3600
15428.6
Satisfy
-000000
rococoC10
11460
3117
3153.87
79096.4
Satisfy
-001000
roi2alpha3n4
-63.208495
6816
1432.63
11463.4
Satisfy
roi5alphalOns
-52.322274
106150
Included training set
The solving time of fewer than 20min
ro113000
12890
1166
44.27
1297.6
Table 18: Primal dual integral results of relpscost and Mamba-Branching on the filtered challenging instances beginning with 'r'. As can be observed, Hamba-Branching maintains its performance advantage over relpscost even on these difficult instances.
Instances Name
relpscost
Mamba- Branching
radiationm 6-12-05
143.17
128.27
radiationm44-
40-10002
862.77
738.38
ran14x18 disjj-
7082.15
9582.3
rd-rpluse-21
359785.5
359786.96
reblock
2352.62
3914.59
rocII-5-11
132899.88 86
129013.09
rococoB vococoB10-011000
10-011000
75874.98
34417.52
rococoC10-001000
14484.75
2876.43
roi2alpha3n4
23719.46
19886.59
gmean of all
10489.28
7371.76
Table 19: Mamba-Brane BrabbhbBannchngggg performance with different contrastive loss functions.
Method
Nodes
Fair Nodes
Time
Maambh-Branchin (ours)
2068.83
2091.54
111.78
InfoNCE loss
2182.88
2216.32
123.49
Triplet loss
2322.41
2360.17
127.59
25

---

Published as a conference paper at ICLR 2026
Table 20: All instances MILP-S.
Instance
Variables
Constraints
Set
air04
8904
823
train
air05
7195
426
train
dcmulti
548
473
train
eil33-2
4516
32
train
istanbul-no-cutoff
5282
20346
train
1152lav
1989
97
train
Iseu
89
28
train
misc03
160
96
train
neos20
1165
2446
train
neos21
614
1085
train
neos-476283
11915
10015
train
neos648910 10
814
1491
train
Pp08aCUTS
240
246
train
mmtr110-pp10
7359
7260
train
mmatr100-p5
8784
8685
train
sp150x300d
600
450
train
stein27
27
118
train
swathl
6805
884
train
vpm2
378
234
train
map18
164547
328818
test
mine-166- 166-
830
8429
test
neosll
1220
2706
test
ncos18
3312
11402
test
ns 880653
1629
2932
test
nu25-pr12
5868
2313
test
rail507
63019
509
test
seymourl
1372
4944
test
26

---

Published as a conference paper at ICLR 2026
Table 21: Training instances in MILP-L
Instance
Variables
Constraints
30n20b8
18380
576
air04
8904
823
air05
7195
426
cod105
1024
1024
comp21-2idx
10863
14038
demulti
548
290
cil33-2
4516
32
istanbul-no-cutoff
5282
20346
11521av
1989
97
Iseu
89
28
misc03
160
96
neoS20
1165
2446
neoS21
614
1085
neos-476283
814
1491
neos648910
11915
10015
PpO8aCUTS
240
246
matr100-p10
8784
8685
matr100-p5
7359
7260
matr2200p5
37816
37617
roi5alpha10n8
106150
4665
sp150 x 300d
600
450
stein27
27
118
supportcase7
138844
6532
swathl
6805
884
ypm2
378
234
27

---

Published as a conference paper at ICLR 2026
Table 22: Easy test instances in MILP-L, SCIP's solving time is less than 20 minutes.
Instance
Variables
Constraints
SCIP Solving Time
aflow40b
2728
1442
375.32
app1-2
26871
53467
662.56
bel
1751
1913
237.68
bell3a
133
123
1.54
bell5
104
91
0.63
biellal
7328
1203
271.30
binkar10_]
2298
1026
47.79
blend2
353
274
0.37
dano3
13873
3202
189.77
fast0507
63009
507
150.11
map10
164547
328818 18
515.00
map18
164547
328818
250.49
map20
164547
328818
218.78
mik-250-20-75-4
270
195
55.67
mine-166-5
830
8429
36.83
misc07
260
212
28.94
n2seq36q
22480
2565
497.79
neos 11
1220
2706
171.35
neos 12
3983
8317
674.23
neos 1200887
234
633
16.46
ncos-1215259
1601
1236
110.12
neos 13
1827
20852
96.20
neos18
3312
11402
27.63
neos-4722443-widden
77723
113555
864.13
neos-4738912-atratt
6216
1947
304.32
ncos-480878
534
1321
52.92
ncos 5046-5
844
1344
114.11
5048-5
674
1067
34.61
neos-512201
838
1337
42.39
184851
445
661
7.11
neos-603073
1696
992
269.58
neos-612125
9554
1795
43.31
neos
neos-612162 612162
9893
1859
40.85
96os-662469
18235
1085
566.6
meas-686199
3660
3664
61.03
neos ccos-801834
3220
3300
$1.71
neas 903s-
640
901
32.99
scos-807639
1030
1541
20.52
neos-820879
9522
361
56.56
neos 8295522
40971
5153
353.99
neos- 9395-
1975
3251
64.10
neos- 592258
1800
2137
54.07
neos-950242
5760
34224
149.60
ns 2208000
2883
4289
111.91
1830653
1629
2932
148.27
nu25-pr12
5868
2313
22.01
nw04
87482
36
42.85
p0201
201
133
0.81
pg
2700
125
45.39
pp08a
240
136
1.44
rai507
63019
509
160.55
rol13000
1166
2295
44.27
rout
556
291
39.51
satellites1-25
9013
5996
952.04
seymour!
1372
4944
61.91
sp98ir
1680
1531
92.98
unitcal_7
25755
48939
889.85
28

---

Published as a conference paper at ICLR 2026
Table 23: Difficult test instances SCIP's solving time is more than 20 minutes.
Instance
Variables
Constraints
SCIP Solving Time
atlanta-ip
48738
21732
3600.00
bab5
21600
4964
2665.41
harp2
2993
112
1642.38
map16715-04
164547
328818
2423.74
msc98-ip
21 143
15850
3600,00
mspp16
29280
561657
2722.23
n3seq24
119856
6044
3600,00
pigeon-10
490
931
3600.01
bab2
147912
17245
3600.02
bab6
114240
29904
3600.01
neos-4338804-snowy
1344
1701
3600.08
neos-4387871-tave
4004
4554
3600.00
ncos-4647030--utaa
12600
8382
3600.09
nussechhed-meiiu--inn033
34248
14062
3600.00
opm2-z10-s4
6250
160633
3600.01
radiatiomm40-10-02
172013
173603
3600.00
29


Reviews:
[{"review_id": "b8ACZpkuzB", "reviewer": "Reviewer_sThn", "summary": "This paper introduces Mamba-Branching, a novel deep learning-based policy for selecting branching variables within the Branch-and-Bound (B&B) algorithm used to solve Mixed-Integer Linear Programming (MILP) problems. The core insight is that existing learning-based methods fail to capture the sequential nature of the B&B process, where the path of decisions from the root of the search tree to the current node influences the next best choice.\nThe focus here is on heterogenous problems and instances.\n\nSequential Modeling with Mamba: It models the \"branching path\"—the history of states and decisions—as a long sequence. It employs the Mamba architecture, a recent State Space Model (SSM), which can efficiently process these long sequences with linear-time complexity, unlike Transformers which have quadratic complexity.\nContrastive Learning for Embeddings: To help the model distinguish between highly similar candidate branching variables, the paper proposes a contrastive learning strategy. This pre-training step learns discriminative feature embeddings by maximizing the similarity between a context anchor and the expert-chosen variable while minimizing similarity with other candidates.\n\nExperiments show that it achieves superior computational efficiency compared to SCIP, a state-of-the-art open-source solver, on particularly difficult problem instances.", "questions": "1. The authors do report result as geometric mean across 5 random seeds, however, variance is not present in the paper. Request the authors to add variance studies.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Novel Conceptualization: A key strength of this work lies in its novel conceptualization of the Branch-and-Bound (B&B) branching process. By framing it as a sequential decision-making problem, the authors effectively model the entire \"branching path,\" a perspective that captures the historical context of the search in a way prior methods have not.\n\nAppropriate Architectural Choice: The selection of the Mamba architecture is exceptionally well-justified and proves to be highly effective for modeling the long B&B sequences where Transformers are computationally infeasible due to their quadratic complexity.\n\nEffective Embedding Strategy: The use of contrastive learning to generate more discriminative embeddings for candidate variables is an insightful solution to a significant challenge in this domain. The ablation studies compellingly confirm that this strategy has a significant and positive impact on performance.\n\nPerformance: The proposed method establishes a new state-of-the-art, demonstrating superior performance over existing neural branching policies and even surpassing the highly optimized relpscost heuristic in the SCIP solver on challenging instances. ( heterogeneous)\n\nEvaluation: The experimental setup is robust and comprehensive, featuring multiple datasets, a strong suite of baselines, appropriate evaluation metrics, and detailed ablation studies that clearly validate the efficacy of the proposed components.\n\nCode is shared.", "weaknesses": "1. Line 341: \"To isolate the study of branching policies and eliminate interference from other solver components,\nwe disable all primal heuristics and provide each test instance with a known optimal solution value as\na cutoff.\".\n\nHow realistic is this setting? Can the authors justify the impact of the above( providing optimal value before hand). It might be done in literature,  but what is the impact of this setting? Justification of this setting is important.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EbEP02jCxz", "reviewer": "Reviewer_7jpx", "summary": "The paper observes that existing GNN-based branching policies treat the B&B tree as an unordered graph and therefore ignore the sequential nature of branching decisions. The authors propose Mamba-Branching:\n1) Employ the Mamba architecture (linear-time state-space model) to encode long branching paths (100+ steps);\n2) Pre-train variable embeddings via contrastive learning so that the selected variable is closest to an anchor in embedding space;\n3) Use imitation learning with SCIP’s relpscost as the expert.\nOn MILP-S and MILP-L datasets Mamba-Branching beats TreeGate, T-BranT and Transformer-Branching in number of nodes and solving time, and surpasses relpscost on difficult instances.", "questions": "1) Does back-propagation through the entire Mamba hidden state remain memory-efficient if the sequence grows to hundreds of steps?\n2) For highly irregular instances, does the order of nodes in the sequence (DFS, BFS, or other) affect convergence, and have you tried alternative orderings?\n3) Contrastive pre-training introduces extra hyper-parameters (margin, temperature); do they need re-tuning when transferring across problem classes?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Fresh perspective: sequential modelling of branching history matches the dynamic nature of B&B.\n2) Sound engineering choice: Mamba’s linear complexity enables 100-step history without memory explosion; experiments confirm faster inference than Transformer.\n3) Strong empirical results on 73 heterogeneous instances; no problem-specific features required.", "weaknesses": "1) Baseline comparison limited to relpscost; no hybrid strong-branching/pseudocost rules used in commercial solvers are included.\n2) The anchor in contrastive learning is obtained by max-pooling, which can be sensitive to outliers; alternative aggregations are not evaluated.\n3) Sequence length (99 train / 24 test) is chosen empirically; no study on optimal truncation or attention-window size.\n4) No theoretical analysis, e.g., sample complexity or regret bounds for the sequential policy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "o0Ell8alir", "reviewer": "Reviewer_7iig", "summary": "This paper proposes Mamba-Branching, a novel method for the Branch and Bound (B&B) algorithm in Mixed Integer Linear Programming (MILP) solvers. The authors' key insight is that existing neural branching methods (e.g., TreeGate and T-BranT) fail to effectively exploit the sequential nature of B&B tree expansion. To address this, they propose using the Mamba architecture (a selective state-space model) to model the complete branching path from the root to the current node. The method treats the historical decisions and tree states along the path as a long sequence. Experiments on the MILP-S and MILP-L datasets show that Mamba-Branching outperforms existing neural branching methods (TreeGate, T-BranT) in solving time, primal-dual integral (PD Integral), and number of nodes, and significantly surpasses Transformer-based models in computational efficiency.", "questions": "+ Are Mamba-Branching and baselines (e.g., TreeGate) compared using identical input features? It is recommended to disclose the feature list to ensure a fair comparison.\n+ Has the method's generalization been validated on datasets beyond MILP-S/L, such as ML4CO 2021?\n+ How does model performance vary with the length of the B&B path? Are there any observed performance bottlenecks for very long sequences?\n+ Could the authors compare their approach with recent learning to branch methods [1, 2] to better position their contribution?\n+ What is the specific selection logic for the instances used in the experiments?\n\n**If the authors can convincingly demonstrate the method's generalization capability and the effectiveness of the contrastive learning component through additional experiments, I would be willing to update my score accordingly**.\n\n[1] Zhang C, Ouyang W, Yuan H, et al. Towards imitation learning to branch for mip: A hybrid reinforcement learning based sample augmentation approach[C]// ICLR 2024.\n\n[2] Parsonson C W F, Laterre A, Barrett T D. Reinforcement learning for branch-and-bound optimisation using retrospective trajectories[C]// AAAI 2023.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ Insightful problem formulation: The observation that traditional neural methods \"generally overlook the sequential nature of B&B tree expansion\" is a key insight. Modeling the \"branching path\" as a sequence is a novel and well-motivated idea that aligns with the intrinsic logic of the B&B process.\n+ Outstanding computational efficiency: The paper clearly demonstrates the memory and speed advantages of Mamba-Branching in training and inference through Table 13. Compared to Transformer-Branching, it consumes significantly less memory and achieves an 80x faster inference speed, a remarkable advantage crucial for practical applications.", "weaknesses": "+ **Insufficient validation of the contrastive learning module**: The effectiveness of the contrastive learning (CL) module is inadequately validated. Although the paper introduces CL for embedding layer training in Section 4.1 and presents its effect via t-SNE visualization in Figure 6, the argument remains weak. The authors only compare with the \"without CL\" setting, which only proves that CL itself is helpful, but fails to demonstrate that their specific CL design is superior or necessary. To more comprehensively assess the value of their approach, the authors should compare their CL framework against several standard and widely-used contrastive learning loss functions and paradigms, such as InfoNCE.\n+ **Ambiguous innovation attribution of Mamba**: The paper's demonstration of computational efficiency (Table 13, Figure 3) is excellent, strongly proving Mamba's significant advantage over Transformers in handling long sequential branching histories. However, these advantages primarily stem from the inherent properties of the Mamba architecture as an existing advanced model (e.g., linear complexity, selective state spaces), and the paper does not introduce any structural or algorithmic modifications or optimizations to the Mamba model itself. Therefore, the core innovation of the work leans more towards \"successfully applying the cutting-edge sequence model Mamba to B&B.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XQllddFcBO", "reviewer": "Reviewer_usDM", "summary": "### This paper presents ​Mamba-Branching, a novel neural branching policy for Mixed-Integer Linear Programming (MILP) that leverages the Mamba architecture to model the sequential nature of Branch-and-Bound (B&B) trees. The approach incorporates contrastive learning, which is a novel embedding layer trained with a contrastive loss to improve discriminability between candidate variables, which often have similar features. Experiments on heterogeneous MILP benchmarks (MILP-S and MILP-L) show that Mamba-Branching outperforms previous neural policies.", "questions": "1. During inference, does the input sequence contain the model's own previous predictions or the expert's actions? If it's the latter, how do you justify this setup for a practical scenario?\n2. The results indicate that on standard (\"easy\") instances, all neural branching policies, including Mamba-Branching, still underperform the expert rule-based relpscost method. This raises two important questions: what explains this performance gap, and what would be needed for neural methods to become practically viable?\n3. Why choose the difficult instances shown in Table 17? Is there justification for that, given the numerous difficult instances in MIPLIB 2017?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* This is the first work to explicitly model the sequential nature of B&B using a state-space model (Mamba). The idea of treating the search as a \"branching path\" is intuitive and well-motivated.\n* The method is well-designed, combining contrastive learning for representation learning with sequential modeling for decision-making. The use of Mamba is justified given the long-sequence nature of the problem.\n* The paper provides extensive experiments on real-world benchmarks, including easy and difficult instances. The results are interesting, demonstrating clear improvements over neural baselines.", "weaknesses": "1.  The description of the input sequence is confusing. It appears that at each step t, the model processes all candidate variable embeddings (e_t^1, ..., e_t^|C_t|) plus the expert's chosen variable embedding e_t^{a_t}. This leads to a sequence length of Σ(|C_t| + 1)over T steps. \n    * Concern 1:​​ Why include the expert action e_t^{a_t}in the input during imitation learning? During inference, the expert action is unavailable. This creates a train-test mismatch. The model might be learning to rely on seeing the expert's choice in the history.\n    * Concern 1:​​ The massive sequence length (Σ|C_t| + T) is acknowledged, but it's unclear how this is handled practically. How many tokens are typical for T=100? The paper mentions \"tens of thousands,\" which seems prohibitive even for Mamba. Please provide statistics on average sequence lengths in training/inference.\n2. The comparison to ​Transformer-Branching​ is unfair. Transformer-Branching is trained with only T = 9 steps due to hardware constraints, whereas Mamba-Branching uses T = 100. The performance gap is likely dominated by this difference in historical context rather than the architecture itself.\n3. The rationale for choosing relpscostover strong branching as the expert is crucial but relegated to the appendix. The argument that TreeGate features are more compatible with relpscost is interesting, but needs a more straightforward explanation in the main text \n4. The experimental setting on the difficult problem is limited. I would like to see more challenging instances being solved and compared to obtain a statistically persuasive experiment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)