On a fix-and-relax framework for class of project scheduling problems

We consider the following problem: Given a set of projects to be executed along a multi-year time horizon, find a sequencing and scheduling feasible solution that optimizes a merit function. A feasible solution should satisfy availability of storable and non-storable resources with budget carrier and non-carrier periods, and precedence, exclusivity and implication relationships among the projects. This is an NP-hard problem. We present several Fix-and-Relax strategies which partition the set of binary variable into clusters in order to selectively explore the branch-and-bound tree. Computational performance is favorably compared with a state-of-the-art optimization engine over a set of real-life cases.