Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
Organizations: Faculty of Engineering, Bar-Ilan University, Max and Anna Webb Street, Ramat Gan 5290002, Israel · Business Administration, especially Procurement and Production, Helmut Schmidt University/University of the Federal Armed Forces Hamburg, Friedrich-Ebert-Damm 245, D-22159 Hamburg, Germany · Management Information Science, University of Siegen, Kohlbettstr. 15, D-57072 Siegen, Germany
Abstract
Branch-and-Bound (B&B) and 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 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 substantially outperforms the B&B variants considered. With additional pruning rules, 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.
Figures & tables
| Aspect | B&B | Search |
|---|---|---|
| Search structure | Tree | Graph |
| Duplicate detection | No | Yes (via Open and Closed lists) |
| Upper bound | Maintained and updated | Not used |
| Lower bound | (same) | (same) |
| Pruning mechanism | Explicit: bound ( ), infeasibility, or a feasible solution | Implicit: best-first + admissibility |
| evaluations per distinct state | Possibly | (with duplicate check before evaluation) |
| Method | Search | LP relaxation | Wall time (s) median [IQR] | Expanded median [IQR] | Generated median [IQR] | Max. frontier median [IQR] | Peak RSS (MiB) median [IQR] |
|---|---|---|---|---|---|---|---|
| A ∗ | – | – | 0.074 [0.026–0.300] | 1,147 [465–3,967] | 2,353 [922–8,076] | 1,111 [463–4,070] | 24.7 [23.8–28.2] |
| B&B | BF | No | 0.111 [0.033–0.560] | 1,330 [472–6,622] | 2,982 [986–13,263] | 1,548 [498–6,493] | 23.8 [23.4–26.0] |
| BF | Weak | 6.831 [2.742–28.366] | 1,147 [430–4,742] | 2,526 [887–11,158] | 1,315 [477–5,418] | 53.7 [49.7–62.0] | |
| BF | Strong | 8.963 [2.413–79.996] | 69 [0–951] | 207 [1–2,445] | 81 [1–672] | 270.8 [231.4–312.8] | |
| DF | No | 0.433 [0.118–2.215] | 6,042 [1,985–29,354] | 7,476 [2,262–40,583] | 63 [51–76] | 22.9 [22.7–23.0] | |
| DF | Weak | 11.570 [4.554–59.114] | 5,295 [1,748–19,337] | 6,741 [1,905–31,502] | 64 [51–79] | 52.4 [49.0–60.1] |
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
| Best-first B&B | Depth-first B&B | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| A ∗ | No LP | Weak LP | Strong LP | No LP | Weak LP | Strong LP | |||
| 0.25 | 0.25 | 1.5 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 0.25 | 0.25 | 1.8 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
| 0.25 | 0.50 | 1.5 | 0 | 1 | 9 | 9 | 1 | 8 | 9 |
| 0.25 | 0.50 | 1.8 | 0 | 0 | 5 | 9 | 0 | 3 | 7 |
| 0.25 | 0.50 | 2.1 | 0 | 0 | 4 | 6 | 0 | 4 | 6 |
Branch and Bound
Branch and bound is an exact search method that uses bounds to prune subproblems and certify optimal solutions.
See all 33 papers