Article ID: | iaor20082961 |
Country: | Germany |
Volume: | 155 |
Issue: | 1 |
Start Page Number: | 143 |
End Page Number: | 166 |
Publication Date: | Nov 2007 |
Journal: | Annals of Operations Research |
Authors: | Demeulemeester Erik, Belin Jeroen |
Keywords: | programming: branch and bound, networks: flow |
In this paper a comparison is made between two decomposition techniques to solve a staff scheduling problem with column generation. In the first approach, decomposition takes place on the staff members, whereas in the second approach decomposition takes place on the activities that have to be performed by the staff members. The resulting master LP is respectively a set partitioning problem and a capacitated multi-commodity flow problem. Both approaches have been implemented in a branch-and-price algorithm. We show a trade-off between modeling power and computation times of both techniques.