arXiv cs.AI· Jiayu Chen, Chentong Chen, Yuhan Liu, Ye Fan, Jianyong Sun, Jialong Shi·· 12 小时前AI 评分23
Evo-B&B：LLM 引导的分支与节点选择策略联合进化框架，用于 MILP 求解
Evo-B&B: Behavior-Aware LLM-Guided Joint Evolution of Branching and Node Selection Policies for MILP
AI 导读
Evo-B&B 是一个由 LLM 引导的进化框架，利用 SCIP 端到端求解反馈，联合进化可执行的分支与节点选择策略，而非分别优化这两项决策。它引入行为感知的多岛进化机制，在固定 B&B 决策状态集上度量策略相似度以保持种群多样性、减少冗余评估。在四个标准 MILP benchmark 上，Evo-B&B 取得有竞争力的求解表现，并能泛化到更大规模实例。
正文 · 原文
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.
| Subjects: | Artificial Intelligence (cs.AI) |
| MSC classes: | 90C11, 90C27, 68T20 |
| ACM classes: | I.2.8; G.1.6 |
| Cite as: | arXiv:2610.22861 [cs.AI] |
| (or arXiv:2610.22861v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.22861 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Jiayu Chen [view email]
[v1]
Fri, 16 Oct 2026 03:07:04 UTC (1,959 KB)
来源：arXiv cs.AI · arxiv.org