Scattered branch and bound – an adaptive search strategy applied to resource-constrained project scheduling

In this paper, a new and general strategy for efficiently controlling the solution process of branch and bound procedures is proposed. It relies on the observation that, due to exploring the solution space rigidly, conventional branch and bound procedures may obtain good solutions as well as dominance information required for fathoming rather late during the solution process. This disadvantage may be overcome by scattering the search process. After decomposing the solution space in disjunctive regions which can be examined independently the search process is controlled by diversification and intensification. Diversifying the search by intelligently ‘jumping’ from region to region allows for collecting information on the structure of the solution space and, in particular, on regions the early examination of which is promising. Whenever such a region is identified, the search is intensified by comprehensively exploring this region in order to find improved solutions or to gather information being useful for fathoming purposes. To examine the effectiveness of scattered branch and bound, the latter is integrated in a procedure for solving the generalized resource-constrained project scheduling problem. Comprehensive computational results underline the success of scattered branch and bound in improving the solution process.