Refine
Document Type
- Article (2)
Language
- English (2)
Has Fulltext
- yes (2)
Keywords
- Software (1)
- Theoretical Computer Science (1)
In this paper, we describe an algorithm for the personalized nurse scheduling problem. We focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition. One specificity of this version is that most constraints are soft, meaning that they can be violated at the price of a penalty. We model the problem as an integer program (IP) that we solve using a branch-and-price procedure. This model is, to the best of our knowledge, comparable to no other from the literature, since each column of the IP corresponds to a rotation, i.e., a sequence of consecutive worked days for a nurse. In contrast, classical models involve individual nurse schedules over the complete horizon. We tackle instances involving up to 120 nurses and 4 shifts over an 8-weeks horizon by embedding the branch-and-price in a large-neighborhood-search framework. Initial solutions of the large-neighborhood search are found by a rolling-horizon algorithm well-suited to the rotation model.
KidneyExchange.jl: a Julia package for solving the kidney exchange problem with branch-and-price
(2024)
The kidney exchange problem (KEP) is an increasingly important healthcare man-
agement problem in most European and North American countries which consists of
matching incompatible patient-donor pairs in a centralized system. Despite the signif-
icant progress in the exact solution of KEP instances in recent years, larger instances
still pose a challenge especially when non-directed donors are taken into account. In
this article, we present a branch-and-price algorithm for the exact solution of KEP
in the presence of non-directed donors. This algorithm is based on a disaggregated
cycle and chains formulation where subproblems are managed through graph copies.
We additionally present a branch-and-price algorithm based on the position-indexed
chain-edge formulation as well as two compact formulations. We formalize and ana-
lyze the complexity of the resulting pricing problems and identify the conditions under
which they can be solved using polynomial-time algorithms. We propose several algo-
rithmic improvements for the branch-and-price algorithms as well as for the solution
of pricing problems. We extensively test all of our implementations using a bench-
mark made up of different types of instances. Our numerical results show that the
proposed algorithm can be significantly faster compared to the state-of-the-art. All
models and algorithms presented in the paper are gathered in an open-access Julia
package, KidneyExchange.jl.
