Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15minutes. In two of the three instances, the optimal solution is found within this time frame.