Joint evolution improves branch and node choices in solving integer programs
Evo-B&B: Behavior-Aware LLM-Guided Joint Evolution of Branching and Node Selection Policies for MILP
Artificial Intelligence
Summary
Branch-and-bound is a method used to solve complex math puzzles called mixed-integer linear programs, but it depends on two tricky choices: where to split (branching) and which spot to explore next (node selection). The team developed Evo-B&B, a system that evolves both choices at once using feedback from solving attempts and learns which decision-making methods behave differently to keep variety. Their tests showed this joint approach can solve problems competitively and even handle bigger problems than it trained on. They also confirmed that evolving both decisions together and tracking behavior helps the learning process.
What this means in practice
- •For operations research teams: Improve efficiency of solving complex optimization problems by jointly optimizing branching and node selection decisions.
- •For logistics planners: Use enhanced branch-and-bound methods to tackle large-scale scheduling and routing problems more effectively.
Authors
Jiayu Chen, Chentong Chen, Yuhan Liu, Ye Fan, Jianyong Sun, Jialong Shi
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.