LiU Electronic Press
Download:
File size:
289 kb
Format:
application/pdf
Author:
Rönnberg, Elina (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Title:
Contributions within two topics in integer programming: nurse scheduling and column generation
Department:
Linköping University, Department of Mathematics, Optimization
Linköping University, The Institute of Technology
Publication type:
Doctoral thesis, comprehensive summary (Other academic)
Language:
English
Publisher: Linköping University Electronic Press
Pages:
39
Series:
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524; 1421
Year of publ.:
2012
URI:
urn:nbn:se:liu:diva-76092
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-76092
ISBN:
978-91-7519-975-7
Subject category:
Computational Mathematics
Abstract(en) :

Integer programming can be used to provide solutions to complex decision and planning problems occurring in a wide variety of situations. The application of integer programming to solve real world problems requires a modelling phase in which the problem at hand is translated into a mathematical description of the problem, and a solution phase that aims at developing methods for producing solutions to the mathematical formulation of the problem.

The first two papers of this thesis have their focus on the modelling phase, and the application of integer programming for solving nurse scheduling problems. Common to both papers is that the research has been conducted in collaboration with health care representatives, and that the models presented can be used for providing schedules that can be used by nurses. In the latter paper, a meta-heuristic approach is suggested for providing the schedules.

The last three papers address method development and specifically the design of column generation methods. The first of these papers presents optimality conditions that are useful in methods where columns are generated using dual solutions that are not necessarily optimal with respect to a linear programming relaxation, and the usefulness of these conditions are illustrated by examples from the literature.

Many applications of column generation yield master problems of a set partitioning type, and the fourth and fifth paper present methodologies for solving such problems. The characteristics of these methodologies  are that all solutions derived are feasible and integral, where the preservation of integrality is a major distinction from other column generation methods presented in the literature.

Public defence:
2012-05-10, Visionen, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Degree:
Doctor of Philosophy (PhD)
Supervisor:
Larsson, Torbjörn, Professor (Linköping University, Department of Mathematics, Optimization ) (Linköping University, The Institute of Technology)
Opponent:
Lübbecke, Marco, Professor (RWTH Aachen University)
Available from:
2012-03-28
Created:
2012-03-26
Last updated:
2013-08-30
Statistics:
778 hits
FILE INFORMATION
File size:
289 kb
Mimetype:
application/pdf
Type:
fulltext
Statistics:
502 hits
File size:
148 kb
Mimetype:
application/pdf
Type:
cover
Statistics:
52 hits