First-order Linear Programming in a Column Generation Based Heuristic Approach to the Nurse Rostering Problem

Strandmark, Petter, Qu, Yi and Curtois, Timothy (2020) First-order Linear Programming in a Column Generation Based Heuristic Approach to the Nurse Rostering Problem. Computers & Operations Research. p. 104945. ISSN 0305-0548 (In Press)

[img] Text
1-s2.0-S0305054820300629-main.pdf - Accepted Version
Restricted to Repository staff only until 1 October 2021.
Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0.

Download (3MB) | Request a copy
Official URL: https://doi.org/10.1016/j.cor.2020.104945

Abstract

A heuristic method based on column generation is presented for the nurse rostering problem. The method differs significantly from an exact column generation approach or a branch and price algorithm because it performs an incomplete search which quickly produces good solutions but does not provide valid lower bounds. It is effective on large instances for which it has produced best known solutions on benchmark data instances. Several innovations were required to produce solutions for the largest instances within acceptable computation times. These include using a fast first-order linear programming solver based on the work of Chambolle and Pock to approximately solve the restricted master problem. A low-accuracy but fast, first-order linear programming method is shown to be an effective option for this master problem. The pricing problem is modelled as a resource constrained shortest path problem with a two-phase dynamic programming method. The model requires only two resources. This enables it to be solved efficiently. A commercial integer programming solver is also tested on the instances. The commercial solver was unable to produce solutions on the largest instances whereas the heuristic method was able to. It is also compared against the state-of-the-art, previously published methods on these instances. Analysis of the branching strategy developed is presented to provide further insights. All the source code for the algorithms presented has been made available on-line for reproducibility of results and to assist other researchers.

Item Type: Article
Uncontrolled Keywords: First-order linear programming, Heuristic, Column Generation, Nurse Rostering
Subjects: G900 Others in Mathematical and Computing Sciences
N900 Others in Business and Administrative studies
Department: Faculties > Business and Law > Newcastle Business School
Depositing User: Elena Carlaw
Date Deposited: 31 Mar 2020 15:29
Last Modified: 31 Mar 2020 15:30
URI: http://nrl.northumbria.ac.uk/id/eprint/42639

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics