- 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?