Machine Learning and Constraint Programming for Efficient Healthcare Scheduling

Solving combinatorial optimization problems involves satisfying hard constraints while optimizing one or more objectives. Although exact methods always return the optimal solution(s), they are usually associated with an exponential time complexity. Alternatively, approximate methods optimize the computations by trading the solution(s)’ quality in exchange for improved execution time. In this paper, we tackle the Nurse Scheduling Problem (NSP). Solving the NSP involves assigning weekly shifts to nurses in a way that satisfies workload coverage constraints while optimizing both nurses’ preferences and hospital costs. In this context, we introduce implicit and explicit approaches to solve the NSP. In the implicit approach, we employ machine learning methods through historical data (assuming that they are optimal) to learn patterns and simulate new scheduling solutions given the constraints and objectives incorporated in the data. To measure the effectiveness of our implicit approach in capturing the underlying constraints and objectives, we use the Frobenius norm, a metric that calculates the mean error between historical data and the obtained solutions. To make up for the lack of visibility of constraints and objectives in the implicit approach, we propose two alternative explicit methods. In the first one, we model the NSP from ground constraints and objectives using the Constraint Satisfaction Problem (CSP) formalism. The latter is consequently solved using Stochastic Local Search and Branch and Bound augmented with variable/value ordering heuristics and constraint propagation. The second explicit method uses a data-driven approach to acquire constraints and objectives in the form of a CSP.