Graph-based A* beats basic branch-and-bound on project scheduling
Original title: Two Communities, One Problem: Branch-and-Bound vs. A* for Resource-Constrained Project Scheduling
With extra pruning, A* proves optimality on all 480 RCPSP instances, versus 445 for best-first branch-and-bound.
A paper compares relatively basic branch-and-bound and A* on the Resource-Constrained Project Scheduling Problem, using the same lower bound and best-first node selection. Graph-based A* substantially outperforms the branch-and-bound variants by detecting equivalent states reached through different decision sequences. With additional pruning, A* proves optimality for all 480 benchmark instances, against 445 for best-first branch-and-bound under the same time and memory limits. Depth-first branch-and-bound uses less memory and can still return feasible solutions when search does not finish.
- Experiments cover 480 benchmark RCPSP instances.
- Best-first branch-and-bound proves 445 instances under the same limits.
- Depth-first branch-and-bound uses less memory than the other variants.
- Stronger linear programming relaxations shrink the search space but add overhead.
From the original article
1 min read at arxiv.orgBranch-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.
By Izack Cohen · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.