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 个。
正文 · AI 翻译
摘要：分支定界（Branch-and-Bound，B&B）和 $A^*$ 分别是源自运筹学和人工智能的常用精确搜索方法。尽管这两种方法共享基本的搜索原理，但它们探索搜索空间的方式不同，可能导致计算性能存在显著差异。我们以资源受限项目调度问题（RCPSP）作为示例问题场景来研究这些差异。我们首先建立混合整数线性规划、状态-动作和时间Petri网表示之间的关系。由于 B&B 和 $A^*$ 支持大量算法增强，我们聚焦于相对基础的实现。这使我们能够考察这些方法之间的根本差异，而不是比较最先进求解器的性能。通过使用相同的下界和最佳优先节点选择，我们分离出搜索机制的影响，特别是识别通过不同调度决策序列到达的等价状态。在 480 个基准 RCPSP 实例上的实验表明，基于图的 $A^*$ 显著优于所考虑的 B&B 变体。在附加剪枝规则下，$A^*$ 在全部 480 个实例上证明了最优性，而在相同时间和内存限制下，最佳优先 B&B 为 445 个。深度优先 B&B 使用更少内存，并且即使搜索未在时间限制内完成也能找到可行解。更强的线性规划松弛可缩小搜索空间，但会引入相当大的计算开销。我们的发现凸显了重复状态检测的重要性，并阐明了这些搜索方法之间的计算权衡。这些见解可帮助研究人员选择合适的方法，并识别将一种方法的有效机制纳入另一种方法的机会。
| 学科： | 优化与控制（math.OC）；人工智能（cs.AI） |
| 引用为： | arXiv:2611.14426 [math.OC] |
| （或 arXiv:2611.14426v1 [math.OC] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2611.14426 由 DataCite 颁发的 arXiv DOI（待注册） |
提交历史
来自：Shimrit Shtern [查看电子邮件]
[v1]
2026年11月10日星期二 18:03:17 UTC（363 KB）
来源：arXiv cs.AI · arxiv.org