Prépublication · 2026
Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
Izack Cohen, Dominik Kress et al. — Monde
Source : arXiv
Résumé
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…