arXiv cs.AI· Izack Cohen, Dominik Kress, Lara Nehrke, Erwin Pesch, Shimrit Shtern·· 10 小时前AI 评分22
两个社区，同一个问题：资源受限项目调度中 Branch-and-Bound 与 A* 的对比
Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
AI 导读
研究以资源受限项目调度问题（RCPSP）为场景，对比了来自运筹学的 Branch-and-Bound（B&B）与来自 AI 的 A* 两种精确搜索方法。在 480 个基准实例上，基于图的 A* 显著优于所考察的 B&B 变体，配合额外剪枝规则后 A* 对全部 480 个实例证明最优，而最佳优先 B&B 在相同时间和内存限制下为 445 个。
正文 · 原文
Abstract: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.
| Subjects: | Optimization and Control (math.OC); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.14426 [math.OC] |
| (or arXiv:2611.14426v1 [math.OC] for this version) | |
| https://doi.org/10.48550/arXiv.2611.14426 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Shimrit Shtern [view email]
[v1]
Tue, 10 Nov 2026 18:03:17 UTC (363 KB)
来源：arXiv cs.AI · arxiv.org