arXiv 论文对比 Branch-and-Bound 与 A* 求解资源受限项目调度问题
Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
运筹学和 AI 两个圈子各用一套搜索方法，这篇论文把 B&B 和 A* 放在同一条件下跑 480 个调度实例，A* 靠重复状态检测全部证明最优，B&B 只做到 445 个。做排程或规划求解的人能从中直接判断该选哪种方法、能借鉴什么机制。
一篇 arXiv 论文以资源受限项目调度问题（RCPSP）为实验场景，系统对比了运筹学传统中的 Branch-and-Bound（B&B）与人工智能传统中的 A* 两种精确搜索方法。作者建立了混合整数线性规划、状态-动作与时间 Petri 网表示之间的对应关系，并在使用相同下界与 best-first 节点选择策略的基础实现上做实验，以隔离搜索机制本身的差异。
实验覆盖 480 个 RCPSP 基准实例：在相同时间与内存限制下，加入额外剪枝规则的图搜索 A* 证明了全部 480 个实例的最优性，而 best-first B&B 只证明了 445 个。差异的关键在于 A* 能识别经由不同调度决策序列到达的等价状态（重复状态检测），而 B&B 缺乏这一机制。Depth-first B&B 虽然内存占用更低，且能在限时内未完成搜索时仍找到可行解；更强的线性规划松弛可缩小搜索空间但引入可观计算开销。
论文指出这并非比较 state-of-the-art 求解器的性能，而是澄清两类搜索方法的计算权衡。对做调度、规划类问题的研究者和工程师，结论提示重复状态检测可能是把 A* 机制移植进 B&B 框架的改进方向。
Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
Branch-and-Bound (B&B) and $A^*$ are popular exact search methods originating from Operations Research and Artificial Intelligence, respectively. Although the two methods share fundamental search principles, their different ways of exploring the search space can lead to substantially different computational performance. We investigate these differences using the Resource-Constrained Project Scheduling Problem (RCPSP) as an exemplary problem setting. We first establish the relationships between mixed-integer linear programming, state-action, and timed Petri-net representations. Since B&B and $A^*$ admit numerous algorithmic enhancements, we focus on relatively basic implementations. This allows us to examine the fundamental differences between the methods rather than compare the performance of state-of-the-art solvers. By using the same lower bound and best-first node selection, we isolate the effects of the search mechanisms, particularly the identification of equivalent states reached through different scheduling decision sequences. Experiments on 480 benchmark RCPSP instances show that graph-based $A^*$ substantially outperforms the B&B variants considered. With additional pruning rules, $A^*$ proves optimality for all 480 instances, compared with 445 for best-first B&B under the same time and memory limits. Depth-first B&B uses less memory and can find feasible solutions even when the search does not finish within the time limit. Stronger linear programming relaxations reduce the search space but introduce considerable computational overhead. Our findings highlight the importance of duplicate-state detection and clarify the computational trade-offs between the search approaches. These insights can help researchers select an appropriate method and identify opportunities to incorporate effective mechanisms from one approach into the other.
This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include A*, Branch-and-Bound, RCPSP, 运筹优化.
Source attribution: curated from arXiv cs.AI (@Izack Cohen, Dominik Kress, Lara Nehrke, Erwin Pesch, Shimrit Shtern).