acceptodds
Under review as a conference paper at ICLR 2027

Evo-B&B: Behavior-Aware LLM-Guided Joint Evolution of Branching and Node Selection Policies for MILP

Abstract

In branch-and-bound for Mixed-Integer Linear Programming (MILP), branching and node selection are two critical and tightly coupled decisions, yet most existing learning-based approaches focus on optimizing them separately. We propose Evo-B&B, an LLM-guided evolutionary framework that jointly evolves executable branching and node selection policies using end-to-end SCIP solving feedback. To improve search efficiency and reduce redundant evaluations of behaviorally similar policies, Evo-B&B introduces a behavior-aware multi-island evolutionary mechanism. It measures policy similarity from branching and node-selection behaviors on a fixed set of B&B decision states and uses this similarity to preserve population diversity. We evaluate Evo-B&B on four standard MILP benchmarks across multiple instance scales. Experimental results show that Evo-B&B achieves competitive solving performance and generalizes well to larger-scale instances, while ablation studies further demonstrate the effectiveness of joint evolution and behavior-aware diversity management.

Primary area:
optimization
Keywords:
Automated Heuristic Design, Mixed-Integer Linear Programming, Branch-and-Bound

Reviews

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

This paper proposes Evo-B&B, an LLM guided evolutionary framework for jointly discovering branching and node selection policies for mixed integer linear programming. While ML has been used in the past for branching and node selection, their joint optimization is a relatively novel direction, especially with LLMs in the loop. In the Evo-B&B framework, candidate policies are represented as executable programs and evaluated via their performance under the SCIP solver. To reduce redundant evaluations, Evo-B&B measures behavioral similarity between policies on a fixed set of branch-and-bound decision states and uses this information within a multi-island evolutionary process. The method also selectively tunes the continuous parameters of promising policies. Experiments on four benchmark families show solid performance. Strong results are obtained particularly for independent set and facility location problems.

Critical strengths

Thank you for submitting your work to ICLR. The main strengths of the paper are:

S1. Jointly optimizing branching and node selection is a promising and fairly novel direction.

S2. I liked the idea of measuring diversity through the decisions induced by policies, rather than only through syntactic differences between their programs. The broad evaluation against a variety of baselines (including learning-based, symbolic, and LLM-based) demonstrates the potential of the proposed framework.

Critical weaknesses

W1. The main issue I have with the paper is that the added value of LLM guidance is somewhat unclear. The paper demonstrates that the overall evolutionary framework can discover effective policies, but it does not isolate what is gained by using an LLM as the program-generation operator. As far as I can tell, there's no comparison against conventional evolutionary or genetic-programming operators under a comparable evaluation budget. Moreover, on the presentation side, the paper does not provide crisp parent-prompt-offspring examples illustrating how the LLM interprets solver feedback and produces meaningful algorithmic modifications that ordinary mutation or crossover would be unlikely to discover (there's a dump of examples in Appendix J, but they don't provide the full picture). On a related note, the reported evolution trajectory describes how the policies change over time but does not demonstrate that these improvements specifically arise from the LLM's reasoning or code-generation capabilities.

W2. Limited evidence for robustness across problem families and evolutionary runs. Evo-B&B shows strong generalization on some benchmarks (e.g independent set and facility location), but the gains are not uniform. LLM4Branch is faster on the medium and hard set-cover instances, while on hard combinatorial auctions Evo-B&B is substantially slower than both LLM4Branch and default SCIP. Moreover, unless I missed something in the appendices, the ablations are reported only on easy and medium set-cover and independent-set instances, leaving it unclear whether behavioral similarity and joint evolution provide similar benefits on facility location, combinatorial auctions, or the hard settings.

W3. As a general comment, the paper in its current format reads more like a technical report with some good ideas and results, but I find it less accessible for the broad machine learning community who might have less background in combinatorial optimization (e.g., examples and illustrations will be very useful).

Questions for authors

Q1. Can the authors compare Evo-B&B with a conventional evolutionary or genetic-programming baseline that uses the same policy representation etc., but replaces LLM generation with standard mutation and crossover operators?

Q2. I am curious how different the resulting islands are at the end of the experiment. On a related note, how is the number of islands chosen?

Q3. What fraction of LLM-generated policies fails interface or safety checking, or fails during SCIP evaluation?

Q4. How does performance evolve as a function of the number of LLM calls and SCIP evaluations? On a related note, can the authors check performance on one or two additional LLMs?

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

This paper proposes Evo-B&B, an LLM-guided evolutionary framework for jointly optimizing branching-variable selection and node selection in mixed-integer linear programming (MILP). The method represents the two solver components as a unified executable policy and optimizes them using end-to-end SCIP solving feedback. The author constructs behavioral features based on fixed branch-and-bound (B&B) decision states, comparing different strategies using candidate objects selected by policies and normalized score distributions. This similarity is used to guide population management and parent selection. The framework also incorporates mechanisms such as adaptive evolutionary operators, inter-island migration, stagnation-triggered resets, and selective optimization of continuous parameters.

Critical strengths

1.This paper focuses on an important issue at the intersection of machine learning and mathematical optimization. Branch operations and node selection interact with each other throughout the entire branch and bound search process. Branches will change the available search nodes, and node selection will affect the subsequent search status.

2.The use of fixed B&B decision probes, top-choice consistency, and normalized score-distribution similarity provides a practical way to characterize policy behavior beyond source-code similarity. The proposed metric is directly connected to the decisions made by the solver.

3.The paper reports promising results on several problem families. In Table 1, Evo-B&B obtains the lowest mean solving time in 6 of the 12 benchmark-scale settings and the highest number of Wins in 8 settings. The results on Indset are particularly encouraging, with improvements over the compared methods across Easy, Medium, and Hard instances.

Critical weaknesses

1.The methodological novelty is not sufficiently established relative to recent work. This is my main concern. Several fundamental components of the proposed framework have already appeared in closely related literature.

First, jointly learning branching and node-selection policies is not entirely new. Du et al. (2025), 《Learning efficient branch-and-bound for solving Mixed Integer Linear Programs》 already investigated these coupled decisions within a unified learning framework.

Second, LLM4Branch (ICML 2026) already combines LLM-generated executable MILP branching programs, continuous parameter optimization, and end-to-end solver feedback. Evo-B&B extends the search target to node selection, but the program-evolution paradigm and structural/numerical decomposition are closely related.

Third, BehaveSim (ICLR 2026), introduced in 《Rethinking Code Similarity for Automated Algorithm Design with LLMs》, has already demonstrated the importance of behavior-based algorithm similarity and explicitly uses behavioral diversity to improve LLM-based automatic algorithm design. Evo-B&B replaces trajectory-based behavior representations with fixed B&B decision probes and combines selection consistency with score-distribution similarity.

Furthermore, TIDE (2026 preprint) already integrates multi-island evolution, UCB-based operator selection, and the separation of structural evolution from continuous parameter tuning. MILP-Evo (2026 preprint) also studies LLM-guided joint evolution of interacting MILP solver components, using end-to-end SCIP feedback and diversity-aware population management. Although MILP-Evo jointly optimizes cut selection and branching rather than branching and node selection, the high-level framework is notably similar.

I acknowledge that the paper cites these relevant lines of work. My concern is the paper needs a more precise technical differentiation and stronger evidence demonstrating that its specific new components yield nontrivial improvements beyond these established ideas. I therefore view the principal novelty as the task-specific joint policy representation and the fixed-state behavioral similarity metric, rather than the overall evolutionary architecture.

2.The abstract motivates behavior-aware evolution as a means of improving search efficiency and reducing redundant evaluations of behaviorally similar policies. However, Section 3.2.1 indicates that a candidate undergoes validity checking and end-to-end SCIP solving evaluation before its behavioral similarity is used for population updating.

Consequently, a newly generated near-duplicate candidate may already have incurred the expensive full solver-evaluation cost before it is rejected. The proposed mechanism could still reduce future redundancy by preventing similar individuals from dominating the population and influencing offspring generation. Nevertheless, this indirect effect is different from avoiding the current candidate's expensive evaluation. The paper does not provide sufficient evidence for this distinction. Table 2 reports the final performance of discovered policies, while Table 4 reports the absolute computational cost of Evo-B&B. Neither directly demonstrates how much evaluation budget is saved by behavior-aware diversity management.

This is important because reducing wasted evolutionary evaluations is a central motivation of the proposed method.

3.The paper claims that Evo-B&B generalizes well to larger-scale MILP instances and exhibits good generalization across different problem scales. However, the results in Table 1 appear to be problem-dependent. In particular, Evo-B&B performs substantially worse than LLM4Branch and Default SCIP on Cauctions-Hard, raising concerns about the robustness of its generalization to larger instances. These results do not invalidate the method, and the strong Indset results remain meaningful. However, they do not support an unqualified conclusion of consistently strong cross-scale generalization.

There is an additional concern regarding the experimental protocol. Section 4.1 states that only Easy instances are used for policy evolution, whereas Medium and Hard are used to evaluate generalization. However, Appendix B.1 states that fixed behavioral probes are constructed from both Easy and Medium instances. The authors should clarify the precise distinction between fitness-training instances, behavior-probe instances, and test instances, including whether the random seeds overlap.

Questions for authors

1.The proposed behavior signatures are constructed from the scores and selected candidates of joint policies on a fixed set of B&B decision probes collected from Default SCIP search trajectories. Can these fixed probes adequately represent the actual B&B search behavior induced by the candidate policies? To what extent can the resulting joint behavior similarity capture meaningful differences in branching and node-selection behaviors during end-to-end SCIP solving? Could the authors provide empirical evidence supporting the representativeness of these fixed probes and clarify the advantages of this design over existing trajectory-based behavioral similarity methods?

2.Regarding the issue I mentioned in the second part of Critical Weakness, I would like to see an evaluation of the search process under a fixed budget, (may) including the number of unique behavioral candidates, redundant candidates, SCIP evaluations, and best-achieved fitness over time.

3.The paper claims that Evo-B&B "generalizes well to larger-scale instances" (Abstract) and demonstrates "good generalization across different problem scales" (Introduction). However, Table 1 shows varying performance across different problem families and instance scales, particularly the substantial performance degradation on Cauctions-Hard compared with the baselines. Could the authors further analyze the reasons for these performance differences and clarify to what extent the experimental results support the claimed generalization ability?

Additionally, Appendix B.1 states that the behavior probes are constructed using instances from both the Easy and Medium scales, while Medium-scale instances are also used to evaluate generalization. Could the authors clarify whether the instances used for behavior probe construction overlap with the evaluation instances, and investigate whether constructing behavior probes using only Easy-scale instances affects generalization performance on Medium- and Hard-scale instances?

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

This paper proposes Evo-B&B, an LLM-guided evolutionary framework that jointly evolves branching and node selection policies for MILP branch-and-bound. Each candidate is an executable Python program with two scoring functions and tunable parameters, embedded into SCIP and evaluated by solving time and node count relative to default SCIP. The key contribution is a behavior-aware diversity mechanism: policies are compared by their decisions on a fixed set of B&B states, combining top-choice agreement with Jensen–Shannon similarity of preference distributions. This similarity drives duplicate filtering, population management, parent selection, and migration in a four-island scheme, with parameter tuning reserved for high-potential policies. Trained on 10 Easy instances per benchmark across four standard problem classes, Evo-B&B achieves the lowest mean solving time in 6 of 12 settings and the most wins in 8, with the strongest gains on Independent Set and Facility Location.

Critical strengths
  • The proposed diversity management strategy appears interesting to me. The use of probes to generate signatures, and the measurement of behavior similarity are quite intuitive.

  • Population management with a utility of maximizing both quality and diversity is well designed.

  • The subsequent optimization and evolution procedures are sound but standard.

  • The experiments are extensive. The empirical performance looks competitive on several benchmarks (e.g., Facilities and Indset).

Critical weaknesses
  • The biggest concern is novelty. Many techniques are directly derived or borrowed from existing literature. For example, multi-island evolution and selective parameter optimization almost directly come from [1].

  • The performance is not convincing, especially on Cauction benchmark. In particular, Evo-B&B even fails to match SCIP, which shed some doubts on the generalizability.

  • The central claim that behavior-aware filtering “reduces redundant evaluations” is not directly supported by any internal statistics. The authors should report how often the τ\tau= 0.98 filter fires, what fraction of candidates are discarded or replaced as near-duplicates, and how this affects population diversity or the downstream evaluation budget over the course of evolution.

[1] TIDE: Tuning-Integrated Dynamic Evolution for LLM-Based Automated Heuristic Design

Questions for authors

N.A.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.