liu.seSearch for publications in DiVA
ReferencesLink to record
Permanent link

Direct link
Contributions within two topics in integer programming : nurse scheduling and column generation
2012 (English)Doktorsavhandling, sammanläggning (Other academic)
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.

Place, publisher, year, pages
Linköping University Electronic Press, 2012. 39 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1421
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-76092 (URN)978-91-7519-975-7 (ISBN)oai:DiVA.org:liu-76092 (OAI)
Public defence
2012-05-10, Visionen, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from2012-03-28 Created:2012-03-26 Last updated:2013-08-30Bibliographically approved
List of papers
1. Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study
Open this publication in new window or tab >>Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study
2010 (English)In: HEALTH CARE MANAGEMENT SCIENCE, ISSN 1386-9620, Vol. 13, no 1, 35-53Artikel i tidskrift (Refereed) Published
Abstract [en]

Hospital wards need to be staffed by nurses round the clock, resulting in irregular working hours for many nurses. Over the years, the nurses influence on the scheduling has been increased in order to improve their working conditions. In Sweden it is common to apply a kind of self-scheduling where each nurse individually proposes a schedule, and then the final schedule is determined through informal negotiations between the nurses. This kind of self-scheduling is very time-consuming and does often lead to conflicts. We present a pilot study which aims at determining if it is possible to create an optimisation tool that automatically delivers a usable schedule based on the schedules proposed by the nurses. The study is performed at a typical Swedish nursing ward, for which we have developed a mathematical model and delivered schedules. The results of this study are very promising and suggest continued work along these lines.

Springer Science Business Media, 2010
Keyword
Nurse scheduling, Nurse rostering, Self-scheduling, Preference scheduling, Operations research, Integer linear programming
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-59720 (URN)10.1007/s10729-009-9107-x (DOI)000281585200004 (ISI)
Note
The original publication is available at www.springerlink.com: Elina Rönnberg and Torbjörn Larsson, Automating the self-scheduling process of nurses in Swedish healthcare: a pilot study, 2010, HEALTH CARE MANAGEMENT SCIENCE, (13), 1, 35-53. http://dx.doi.org/10.1007/s10729-009-9107-x Copyright: Springer Science Business Media http://www.springerlink.com/ Available from2010-09-24 Created:2010-09-24 Last updated:2013-08-30
2. Automatic scheduling of nurses
Open this publication in new window or tab >>Automatic scheduling of nurses : What does it take in practice?
2013 (English)In: Systems Analysis Tools for Better Healthcare Delivery / [ed] P. Pardalos, P. Georgiev and P. Papajorgji, New York, NY: Springer Science+Business Media B.V., 2013, 151-178Kapitel i bok, del av antologi (Refereed)
Abstract [en]

Many hospital wards need to be staffed by nurses around the clock every day of the year, and because of that, many nurses have to work irregular hours and according to schedules that have a great impact on their personal lives. Today most schedules are made by hand or with limited computer support, and this is both difficult and very time consuming. A common consequence of making the schedules by hand is that the outcome is neither favourable for the nurses nor satisfactory for the running of the ward.

The nurse scheduling problem is well suited for addressing with operations research methods, but a challenge for automated scheduling of nurses is the ability to adapt the scheduling to the specific conditions on each ward. The intention of this paper is to provide a piece of practical experience that can help bridge the gap between advanced method development and the use of automatic nurse scheduling in practice. Our approach is to take on the real life scheduling problem with all its details, and to use a straightforward meta-heuristic in order to deliver automatically generated schedules. The contribution of the paper is based on the result of two case studies, which will provide insights into examples of real world nurse scheduling, including evaluation and feedback from the wards.

New York, NY: Springer Science+Business Media B.V., 2013
Series
Springer Optimization and Its Applications, ISSN 1931-6828 ; 74
Keyword
nurse scheduling, nurse rostering, self-scheduling, preference scheduling, operations research, integer linear programming
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-76079 (URN)10.1007/978-1-4614-5094-8_8 (DOI)978-1-4614-5093-1 (print) (ISBN)978-1-4614-5094-8 (online) (ISBN)
Available from2012-03-26 Created:2012-03-26 Last updated:2014-04-25Bibliographically approved
3. Column generation using non-optimal dual solutions: Optimality conditions and over-generation
Open this publication in new window or tab >>Column generation using non-optimal dual solutions: Optimality conditions and over-generation
(English)Manuskript (preprint) (Other academic)
Abstract [en]

Column generation is a linear programming method that, when combined with appropriate integer programming techniques, has been successfully used for solving huge integer programs. The use of a dual solution to the restricted master problem is essential when new columns are derived by solving a subproblem. Even if the problem to be solved is an integer programming one, this dual solution is usually optimal with respect to the linear programming relaxation of either the original problem or of a restriction thereof formed further down a branch-and-price-tree.

This paper addresses the situation that arises when columns of a binary problem are generated using any dual solution, and we derive optimality conditions for determining when the master problem has been augmented with enough columns to contain an integer optimal solution to the complete master problem.

We discuss the concept of over-generation of columns, which means to augment the restricted master problem with a set of columns, to ensure progress of the algorithm and also to make sure that the columns of the restricted master problem eventually comply with the optimality conditions. To illustrate the over-generation strategy, we compare our results with special cases that are already known from the literature, and we make some new suggestions.

Keyword
Binary program, column generation, optimality conditions, overgeneration
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-76090 (URN)
Available from2012-03-26 Created:2012-03-26 Last updated:2013-08-30Bibliographically approved
4. Column Generation in the Integral Simplex Method
Open this publication in new window or tab >>Column Generation in the Integral Simplex Method
2009 (English)In: European Journal of Operational Research, ISSN 0377-2217, Vol. 192, no 1, 333-342Artikel i tidskrift (Refereed) Published
Abstract [en]

The integral simplex method for set partitioning problems allows onlypivots-on-one to be made, which results in a primal all-integer method. Inthis technical note we outline how to tailor the column generationprinciple to this method. Because of the restriction topivots-on-one, only local optimality can be guaranteed, and to ensureglobal optimality we consider the use of implicit enumeration.

Elsevier, 2009
Keyword
integer programming, set partitioning, column generation, quasi-integrality
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-15287 (URN)10.1016/j.ejor.2007.09.037 (DOI)
Note
Original publication: Elina Rönnberg and Torbjörn Larsson, Column Generation in the Integral Simplex Method, 2009, European Journal of Operational Research, (192), 1, 333-342. http://dx.doi.org/10.1016/j.ejor.2007.09.037. Copyright: Elsevier B.V., http://www.elsevier.com/Available from2008-10-29 Created:2008-10-29 Last updated:2013-08-30Bibliographically approved
5. All-integer column generation: Basic principles and extensions
Open this publication in new window or tab >>All-integer column generation: Basic principles and extensions
2014 (English)In: European Journal of Operational Research, ISSN 0377-2217, Vol. 233, no 3, 529-538Artikel i tidskrift (Refereed) Published
Abstract [en]

Column generation is a linear programming method in which a dual solution of the master problem is essential when deriving new columns by solving a subproblem. When combined with appropriate integer programming techniques, column generation has successfully been used for solving huge integer programs. In many applications where column generation is used, the master problem is of a set partitioning type.

The set partitioning polytope has the quasi-integrality property, which enables the use of simplex pivot based methods for finding improved integer solutions where each integer solution is associated with a linear programming basis a corresponding dual solution. By combining these kinds of simplex pivots with column generation, one obtains a method where each successively found solution to a restricted master problem is feasible, integer, and associated with a dual solution to be used in the column generation step. The column generation subproblem can either be of a regular type, or it can be tailored to produce columns that maintain integrality when pivoted into the basis.

In this paper, a framework for this kind of column generation, which we here name all-integer column generation for set partitioning problems, is presented. The strategies proposed are primarily of a meta-heuristic nature, but with the proper settings, optimal or near-optimal solutions can be obtained.

Elsevier, 2014
Keyword
Set partitioning, meta-heuristic, column generation, quasiintegrality, surrogate columns, over-generation, all-integer pivots
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-76091 (URN)10.1016/j.ejor.2013.08.036 (DOI)000328180200006 (ISI)urn:nbn:se:liu:diva-102966 (Local ID)urn:nbn:se:liu:diva-102966 (Archive number)urn:nbn:se:liu:diva-102966 (OAI)
Note
<p>On the day of the defence date the status of this article was <em>Manuscript </em>with the title <em>All-integer column generation: A meta-heuristic for set partitioning problems</em>.</p>Available from2012-03-26 Created:2012-03-26 Last updated:2014-02-19Bibliographically approved

Open Access in DiVA

fulltext(289 kB)512 downloads
File information
File name FULLTEXT01.pdfFile size 289 kBChecksum SHA-512
0002c0ac14c39ba2488b709d2ee6f0e603911dec8218d00e975b6dc42406f39a18b1a3eeb6f304049ecf397d66e5c16465d20eaeff227ec2803089bba9e6df3e
Typ fulltextMimetype application/pdf
cover(148 kB)53 downloads
File information
File name COVER01.pdfFile size 148 kBChecksum SHA-512
e1b8a8e67d1ed0d5d38554320af5c0223b316e4f11cc381107adba0a77a4a52f539b2e1f64975953adcf10607eba91269f8b3191d2b364e4e11f9c48cbbb06d8
Typ coverMimetype application/pdf

Search in DiVA

By author/editor
Rönnberg, Elina
By organisation
Optimization The Institute of Technology
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Totalt: 512 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available
Totalt: 803 hits
ReferencesLink to record
Permanent link

Direct link