A branch-price-and-cut algorithm for multi-mode resource leveling

• We present a new model and algorithm for a RCPSP with availability constraints.
• We propose a non-trivial, non-obvious Dantzig–Wolfe reformulation.
• We translate standard precedence inequalities into our new formulation.
• Our model gives significantly tighter lower bounds
• We increase the size of instances that can be solved to optimality to 50 jobs.

We propose a new mixed integer programming formulation and solution algorithm for a multi-mode resource-constrained project scheduling problem with availability constraints (calendars) and the objective to minimize the resource availability cost. Our model exploits the problem structure and has an exponential number of variables, which necessitates a column generation approach. The linear programming relaxation is strengthened by adding valid inequalities that need to be carefully separated in order to show the desired effect. Integer optimal solutions are obtained by an exact state-of-the-art branch-price-and-cut algorithm.Classical time-indexed mixed integer programming formulations for similar problems quite often fail already on instances with only 30 jobs, depending on the network complexity and the total freedom of arranging jobs. A reason is the typically very weak linear programming relaxation. Our model can be interpreted as a non-trivial Dantzig–Wolfe reformulation of a time-indexed formulation. In particular, for larger instances our reformulation gives significantly tighter dual bounds, enabling us to optimally solve instances with 50 multi-mode jobs. This outperforms the classical formulation by far.