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

Anders Høeg Dohn, Andrew Mason

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    JournalEuropean Journal of Operational Research
    Volume230
    Issue number1
    Pages (from-to)157-169
    ISSN0377-2217
    DOIs
    Publication statusPublished - 2013

    Keywords

    • OR in manpower planning
    • Generic programming
    • Branch-and-price
    • Scheduling
    • Staff rostering

    Fingerprint

    Dive into the research topics of 'Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation'. Together they form a unique fingerprint.

    Cite this