Learning to Reduce State-Expanded Networks for Multi-activity Shift Scheduling

For personnel scheduling problems, mixed-integer linear programming formulations based on state-expanded networks in which nodes correspond to rule-related states often have very strong LP relaxations. A challenge of these formulations is that they typically give rise to large model instances. If one is willing to trade in optimality for computation time, a way to reduce the size of the model instances is to heuristically remove unpromising nodes and arcs from the state-expanded networks. In this paper, we propose to employ machine learning models for guiding the reduction of state-expanded networks for multi-activity shift scheduling problems. More specifically, we train a model that predicts the flow through a node from its state attributes, and based on this prediction, we decide whether to keep a node or not. In experiments with a well-known set of multi-activity shift scheduling instances, we show that our approach substantially reduces both the size of the model instances and their solution times while still obtaining optimal solutions for the vast majority of the instances. The results indicate that our approach is competitive with a state-of-the art Lagrangian-relaxation-based matheuristic for multi-activity shift scheduling problems.

Automated summary

This paper proposes a method to reduce the size of state-expanded networks for multi-activity shift scheduling problems using machine learning models, which substantially reduces the size of model instances and solution times while still obtaining optimal solutions for most instances. The results show that this approach is competitive with a state-of-the-art matheuristic for multi-activity shift scheduling problems.