Methods and Applications in Integer Programming: All-Integer Column Generation and Nurse Scheduling
2008 (English)Licentiate thesis, comprehensive summary (Other academic)
Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.
Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.
The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2008. , 16 p.
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1383
integer programming, column generation, set partitioning problems, quasi-integrality, nurse scheduling
IdentifiersURN: urn:nbn:se:liu:diva-15143ISBN: 978-91-7393-760-3OAI: oai:DiVA.org:liu-15143DiVA: diva2:113882
2008-11-21, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Altenstedt, Fredrik, Doktor
Larsson, Torbjörn, Professor
List of papers