acceptodds
Under review as a conference paper at ICLR 2027

Learning to Branch In Context: Adaptive Variable Selection for MILP

Abstract

A branch-and-bound solve produces observations of how individual branching variables affect the search. Pseudocost rules use these observations to update variable-specific estimates, whereas learned branchers usually consume them only through solver-maintained features or a history of states and actions. We study in-context branching (ICB), which exposes observed directional bound gains as an explicit, identity-linked memory. A learned prior and an evidence-weighted estimator predict directional gains; a fixed scoring rule selects the branching variable. The model is trained by strong-branching distillation and uses new observations without updating its parameters. On canonical combinatorial-auction instances, removing memory from the same checkpoint increases the medium-size node aggregate from 1,205 to 3,204, with all runs solved. On a reconstructed class-disjoint MILP-Evolve cohort, context raises the solved fraction from 55.6% to 69.1% and reduces the paired primal–dual integral by approximately 15%. Comparisons with reproduced branching policies are family-dependent: some transfer results are competitive, but reliability pseudocost branching remains stronger overall. The experiments distinguish improvements due to event memory from those retained when the same policy is evaluated without memory.

Primary area:
optimization
Keywords:
mixed-integer linear programming, branch and bound, variable selection, learning to branch, in-context learning, strong branching, pseudocost branching, sequence models, test-time adaptation, combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_e6CqOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes in-context branching (ICB). During an SCIP solve, observed directional branching outcomes (per-unit bound gains attributed to the branched variable and direction) are stored in a rolling memory of 256 events. A frozen network uses this memory to predict directional gains for the current candidates. Its parts are:

  • a learned feature-based prior with learned pseudo-counts;
  • shrinkage toward exact-identity evidence, plus an optional similarity channel;
  • a cross-attention residual;
  • a fixed min/max score readout.

Training distills strong-branching decisions on exploration-diversified trajectories. Pseudocost features are masked from the inputs. The paper evaluates on the four Gasse et al. (2019) families and on a reconstructed class-disjoint MILP-Evolve cohort of 340 instances. It compares against reruns of RPB, GCNN, and Mamba-Branching, and runs interventions on the memory of a fixed checkpoint (context-off, exact-only, similarity-only, shuffles).

Critical strengths
  1. A clean interface and careful interventions. The causal event definition (Eq. 3) is clear. Fixed-checkpoint interventions (context-off, exact-only, shuffled similarity, similarity-only; Table 3) are a good way to ask whether a frozen policy actually uses the information stream.
  2. A meaningful effect within the paper's own setup. On combinatorial auctions, removing memory raises the medium-scale node aggregate from 1,205 to 3,204. On the class-disjoint MILP-Evolve cohort, memory raises completion from 55.6% to 69.1% (Table 4).
  3. Unusually candid reporting. The paper reports negative results (facility location, multiple knapsack, independent-set big), variation across training seeds (Table 10), and exposure of test cells during development (Appendix C). It also states which claims it does not make.
Critical weaknesses
  1. The main ablation is close to tautological. The event memory holds per-variable, per-direction unit gains, which is exactly what pseudocosts are. The model masks the pseudocost features (columns 8–14) from its inputs. "Context-off" therefore removes all pseudocost-type information from a model trained to rely on it through the memory. A large drop is expected and says little about whether an explicit, identity-linked memory beats the standard way of giving a learned brancher this information. The informative comparison is a separately trained state-only model that sees the pseudocost and history features (as GCNN-style and hybrid branchers do), with the same data and training budget. The paper acknowledges this is missing (Section 5), but without it the central question in the introduction is not answered. The single 40-run screen of an unmasked variant (4 runs solved) is too small to settle it.

  2. No practical improvement over the classical rule. RPB solves at least as many instances as ICB in every Gasse cell except facility-location big (93% vs 96%), and often many more (45% vs 26% on independent-set big, 65% vs 35% on set-cover big). It also solves more of the MILP-Evolve cohort (79.1% vs 69.1%). Wall time is worse in most cells: 508.1 s vs 124.6 s on independent-set medium even though ICB builds fewer nodes there, and 40.0 s vs 8.4 s on independent-set easy. Given the conditional nature of the tree-size ratios (computed only on jointly solved runs), the evidence does not show that ICB is a better brancher than the pseudocost rule it imitates in memory.

  3. The reproduced baselines look weak and incomplete.

    • GCNN solves only 47% of independent-set medium runs and 1% of big. This is well below what the original learn2branch study reported for this generator and scale.
    • Mamba solves 7% of independent-set big.
    • GCNN is missing entirely for set-cover easy and medium and independent-set easy.
    • The released MILP-Evolve GCN reproduction "does not recover the published completion rate" (Appendix F).

    When the learned comparators underperform their published numbers, "ICB beats Mamba/GCNN" in some cells is hard to interpret. Please investigate these gaps, or use the authors' released checkpoints and settings where available.

  4. Timing is not reliable. Reported time is external wall time on a shared host, "including contention"; per-run internal CPU times "were not retained" (Appendix B.2). GCNN inference uses a GPU while ICB and Mamba use the CPU. Speed is the main reason to learn a brancher, so the time columns should be re-measured on an isolated machine with solver-clock times, or removed from the comparison.

  5. Test-set exposure and variance. Recipe choices for independent set and set cover were informed by results on the canonical evaluation cells (Appendix C). Three training seeds yield 1,383, 3,759, and 1,401 nodes on the independent-set medium (Table 10), a spread larger than many reported between-method differences. Main tables use a single checkpoint per family, and no class-clustered intervals are given for MILP-Evolve. A clean protocol is needed: recipes chosen only on validation, several training seeds, and intervals for every headline comparison.

  6. The experimental platform is dated. All main experiments use SCIP 6.0.1 (2018) with root-only cuts and no restarts. This matches the learn2branch protocol, but it makes it hard to judge relevance to current solvers. One cell repeated on a recent SCIP release would help.

  7. Presentation. The paper is heavily hedged. Many sentences state what a result does not show, and Section 3 introduces notation not needed in the main text. Table 1 is dense, and its time columns are not comparable across methods (Weakness 4). A clearer statement of the positive claim, plus a matched-data comparison, would make the contribution easier to assess.

Questions for authors
  1. Can you train a state-only model with pseudocost and history features unmasked, on the same data and budget, and compare it with full-context ICB? This is the comparison that would show the value of an explicit memory.
  2. Why do the GCNN and Mamba reruns underperform their published results (e.g., GCNN at 47% on independent-set medium)? Were the original checkpoints, features, and SCIP settings used?
  3. Can the time comparisons be re-run on an isolated machine using SCIP's internal clock, with every policy on the same device?
  4. How do the main conclusions hold across at least three training seeds for every family, with recipes chosen on validation only?
  5. Does ICB improve on RPB when RPB's reliability parameters are tuned on the same training data? Can the learned prior be used to initialize pseudocosts within RPB rather than replace it?
  6. What are the class-clustered confidence intervals for the MILP-Evolve completion and PDI differences?
Reviewer_B4nrOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes In-Context Branching (ICB), a context-learning-based branching strategy for mixed-integer linear programming (MILP). By explicitly storing the branching outcomes observed during the solving process, it enables the neural network to adjust subsequent variable selection using historical feedback without updating model parameters. In essence, this way of exploiting branching history bears similarity to pseudocost branching.

Specifically, the method constructs an event memory associated with variable identities, and combines a learned prior, an evidence-weighted shrinkage estimator, and a cross-attention residual network to predict the bound improvement of candidate variables under different branching directions. The model is trained via strong branching distillation.

The authors conduct experiments on four classic MILP problem classes and a reconstructed MILP-Evolve dataset. The results show that the historical event memory can improve the performance of learned branching strategies on some problem classes and in size-transfer scenarios, but such gains are not consistent, and the full ICB method does not stably outperform all baselines.

Critical strengths

S1. Proposes an adaptive neural network branching mechanism that explicitly exploits historical branching feedback.

Through an event memory associated with variable identities, ICB incorporates the actually observed branching gains into subsequent decisions, enabling the model to exploit feedback information from the solving process without updating its parameters.

S2. Validates the effectiveness of historical event memory through targeted experiments.

Through context-intervention experiments under fixed model parameters, the authors demonstrate the performance gains of event memory on the combinatorial auction problem and on unseen MILP-Evolve problem classes, and they report results in which no significant gains were obtained on some problem classes.

Critical weaknesses

W1. Insufficient Ablation of Key Architectural Components

The paper introduces a learned prior, an evidence-weighted shrinkage estimator, and a multi-layer cross-attention residual network, but lacks sufficient ablation studies to isolate their individual contributions, making it difficult to justify the necessity of the proposed complex architecture.

In particular:

  • Does the cross-attention residual network provide an independent performance benefit?
  • Does the learned evidence-weighted shrinkage estimator outperform simpler fixed-weight evidence aggregation?
  • Why does the exact-only variant outperform the full-context model in some settings? Does the structural similarity channel provide additional benefits?

W2. Lack of loss function ablation experiments.

The training objective combines a strong branching classification loss with an auxiliary Huber loss, but the independent contribution of the auxiliary loss term is not verified.

W3. The fairness and reproducibility of the computational configuration are questionable.

The paper runs GCNN on GPU but runs Mamba-Branching and ICB on CPU. Since efficient implementations of Mamba rely on GPU-optimized operators, the authors do not adequately explain the specific CPU inference implementation and its impact on the performance comparison.

The core of this issue is not that GPU must be used uniformly, but rather that the CPU implementation of Mamba-Branching needs to be clearly explained and the timing comparison ensured to be interpretable.

W4. Lack of sufficient analysis of overall solving efficiency and model inference overhead.

Although ICB reduces the number of nodes in some experiments, this advantage does not consistently translate into shorter overall solving time, and in some scenarios it even exhibits longer solving time. Considering that the core goal of learned branching strategies is to improve practical solving efficiency, the paper lacks a quantitative analysis of neural network inference overhead, making it difficult to determine whether the gains brought by the complex network architecture are sufficient to offset its additional computational cost.

Questions for authors

Q1. Regarding ablations of key architectural components.

Could the authors add separate controlled experiments that remove the cross-attention residual network and that replace the learnable evidence weighting mechanism with a fixed-weight aggregation mechanism?

Q2. Regarding the structural similarity mechanism.

Why does the Exact-only variant outperform Full Context in some experiments? What independent benefits can the structural similarity mechanism actually provide?

Q3. Regarding the loss function.

How would the branching decision quality and final solving performance change after removing the auxiliary Huber loss or adjusting its weight λ\lambda?

Q4. Regarding the CPU implementation of Mamba-Branching.

Considering that the official high-performance implementation of Mamba uses GPU-optimized operators, which selective scan implementation did the authors adopt when running Mamba-Branching on CPU? Is this implementation consistent with the original GPU version in terms of functionality and inference efficiency?

Q5. Regarding the fairness of different inference devices.

Why is GCNN run on GPU while Mamba-Branching and ICB are run on CPU? Have the authors evaluated the impact of device choice on the final solving time comparison?

Q6. Regarding computational overhead.

What is the average inference time of ICB per branching decision? How does this overhead vary with the number of candidate variables and the number of historical events? If the computational overhead per inference is too large, would it offset the advantage of a smaller number of nodes and thus lead to longer overall solving time?

Reviewer_XYAzOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper speeds up a branch-and-bound solver. It uses a neural net to choose among the current fractional variables j, by attending to the 256 past "events." An event is a previously chosen variable once its pseudocosts have become known.

There are some training trajectories, and candidates in these trajectories are assessed offline using strong branching and pseudocosts. The strong branching rule provides a classification target, and transformed versions of the pseudocosts provide a regression target. These two losses are used together to train a model that is used at runtime for classification.

Critical strengths

The research problem remains important. We should be able to train solvers (within-domain or cross-domain) to adapt online to a problem instance by conditioning on information they've collected so far. Neural nets might be able to beat conventional heuristics for this.

Critical weaknesses

== Results ==

No clear improvement over the baseline, which I had expected given the complexity of the approach.

  • Table 1 shows that of 12 competitions (4 tasks at 3 sizes), it never solves more problems than the standard RPB method. (One exception: For large facility location problems, it gets 96/100 instead of 93/100, but this can't be a significant difference under a sign test, I think.)
  • Table 7 compares node count on instances that both nodes solve, a fair comparison with appropriate significance tests. That table does show a few wins over RPB ...
  • ... but what I really want to see is a version of Table 7 for runtime, and that's not provided! (Simple optimized search methods often win on runtime despite exploring more nodes, as everyone knows from Deep Blue and zChaff. A priori, I'd certainly expect the proposed method to be slower per node than RPB.)

Based on Table 1, the proposed method looks like it loses on runtime in the cases where Table 7 shows it wins on nodes, although the numbers in Table 1 are hard to compare meaningfully because they're geometric means of right-censored runtimes, and there was no attempt (like a paired permutation test) to assess significance of differences.

== Lack of analysis ==

If the method is providing benefits in some cases, it's not clear why. Evaluation is mainly end-to-end. But the neural net is trained to do classification and regression, as I noted above, so I'd like to know whether its complicated architecture even succeeds at those tasks. There's no assessment of regression. For classification, Table 12 provides evidence (off-policy) that the classifier is at least paying attention to the input, since perturbing the input makes it worse at matching the strong branching result. But it's not clear whether the unperturbed method is doing "well," since it's not compared to any simpler baseline; maybe a trivial method would be comparable.

== AI slop ==

The presentation needs a complete overhaul. I was not able to follow the method well in its current form. The paper is clearly written by AI -- I really wish submitters wouldn't do this! -- and I eventually had to resort to AI to help me read it. This is partly because the method is complicated (overly so?), and partly because the paper isn't user-friendly. It should give a clear story in the main paper, perhaps starting with a bare-bones version of the method, and provide enhancements and replication details in the appendices. Instead, it skips the clear story and does not respect the distinction between main paper and appendices. It dumps lots of details in rapid successioconcisen, without the context necessary to understand them, and often scatters related details across multiple sections. Many details are disclosed via an offhand phrase that is too compact to really understand without more context.

So I basically interviewed a (privacy-preserving instance of) Claude Sonnet 5.5 Medium about the paper. It has parallel attention over a long context window and was typically able to piece together quotes from 3 different sections (!) to answer my questions or report that my question was not answered anywhere in the paper.

Even with this kind of help, it would be difficult to replicate the method. For example, the 40 features listed in Table 6 and Appendix A.2 are only sketched with a few words, not clearly defined. I don't think there's a code release.

The problems start right with the abstract. I wrote in my notes as I started:

The method "exposes observed directional bound gains as an explicit, identity-linked memory" - huh? "Directional bound gains" might refer to the tightening of the LP bound after branching on a fractional variable. But bounds substitute for something that isn't observed (the true value of a node). And I don't know what it means to "expose" them or what an "explicit, identity-linked memory" is. Maybe the phrase "in-context branching" is meant to refer to in-context learning, and "memory" means the context? Does "identity" mean the identity of a node in the tree? Is this overall a method like TabPFN, applied to the specific problem of predicting future bounds from past ones?

I was able to figure these things out later. But I want the authors to understand that they should never write like this (or teach a class like this). It should be possible to read a paper from start to finish, in order, without being confused at any point. You may develop shorthand phrases when talking to co-authors or chatbots. But don't let your AI throw these internal shorthands at a reader until you prepare the reader with context, motivation, and definitions. Your goal is not to "get a paper accepted." It is to teach a valuable method to readers who will actually use it or build on it.

Questions for authors

These are questions about the neural network design. They are provided mainly as feedback to the authors, although I would be curious about answers.

This is a conference on learning representations. What do you expect the 4 layers of attention to learn? And how do they work? You say candidates attend to events (cross-attention). In contrast I can't find evidence of self-attention, where candidates attend to one another, or events attend to one another. In fact I'm not sure the events actually have higher-level representations at all.

There don't seem to be any absolute or relative position embeddings, such that candidate or events know their absolute and relative positions in the tree. But those positions seem potentially important in predicting pseudocosts. So if that's correct, would it be helpful to add this, along with enough self-attention to make it useful? (Cols 2-3 have the average branching depth of past nodes that use the same variable, but that's not the same as the depth of the current node.)

Instead of using random keys to detect identity, have you considered using relational attention (Shaw et al., 2018)? I've tried both in other settings and have found relational attention to work better. It would also allow the network to consider relations other than identity.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.