A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem

Abstract

The branch-and-bound (B&B) procedure is one of the most widely used techniques to get optimal solutions for the resource-constrained project scheduling problem (RCPSP). Recently, various components from the literature have been assembled by Coelho and Vanhoucke (2018) into a unified search algorithm using the best performing lower bounds, branching schemes, search strategies, and dominance rules. However, due to the high computational time, this procedure is only suitable to solve small to medium-sized problems. Moreover, despite its relatively good performance, not much is known about which components perform best, and how these components should be combined into a procedure to maximize chances to solve the problem. This paper introduces a structured prediction approach to rank various combinations of components (configurations) of the integrated B&B procedure. More specifically, two regression methods are used to map project indicators to a full ranking of configurations. The objective is to provide preference information about the quality of different configurations to obtain the best possible solution. Using such models, the ranking of all configurations can be predicted, and these predictions are then used to get the best possible solution for a new project with known network and resource values. A computational experiment is conducted to verify the performance of this novel approach. Furthermore, the models are tested for 48 different configurations, and their robustness is investigated on datasets with different numbers of activities. The results show that the two models are very competitive, and both can generate significantly better results than any single-best configuration.