liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Methods and Applications in Integer Programming: All-Integer Column Generation and Nurse Scheduling
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
2008 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

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.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1383
Keyword [en]
integer programming, column generation, set partitioning problems, quasi-integrality, nurse scheduling
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-15143ISBN: 978-91-7393-760-3 (print)OAI: oai:DiVA.org:liu-15143DiVA: diva2:113882
Presentation
2008-11-21, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2008-11-05 Created: 2008-10-30 Last updated: 2013-08-30Bibliographically approved
List of papers
1. 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, E-ISSN 1872-6860, Vol. 192, no 1, 333-342 p.Article in journal (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.

Place, publisher, year, edition, pages
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 from: 2008-10-29 Created: 2008-10-29 Last updated: 2017-12-14Bibliographically approved
2. An All-Integer Column Generation Methodology for Set Partitioning Problems
Open this publication in new window or tab >>An All-Integer Column Generation Methodology for Set Partitioning Problems
2008 (English)Report (Other academic)
Abstract [en]

The set partitioning polytope has the quasi-integrality propertythat enables the use of simplex pivot based methods for finding animproved integer solution, which thereby is associated with a linearprogramming basis and a corresponding dual solution. Presented in thispaper is a framework for an all-integer column generation methodologyfor set partitioning problems that utilises the quasi-integralityproperty of the feasible polytope.In the presented methodology, each successively found solution to arestricted master problem is feasible, integer and associated with acorresponding dual solution, which is then used in the columngeneration step. The column generation problem is tailored to producecolumns that maintain integrality when pivoted into the basis.Furthermore, criteria for verifying optimality are presented.

Publisher
23 p.
Series
Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960
Keyword
integer programming, column generation, quasi-integrality, surrogate columns, over-generation
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-15256 (URN)
Available from: 2008-10-28 Created: 2008-10-27 Last updated: 2013-08-30Bibliographically approved
3. 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
2008 (English)Report (Other academic)
Abstract [en]

Hospital wards need to be staffed by nurses round the clock, resultingin irregular working hours for many nurses. Over the years, thenurses' influence on the scheduling have been increased in order toimprove their working conditions. In Sweden it is common to apply a kindof self-scheduling where each nurse individually proposes a schedule,and then the final schedule is determined through informalnegotiations between the nurses. This kind of self-scheduling is verytime-consuming and does often lead to conflicts.We present a pilot study which aims at determining if it is possibleto create an optimisation tool that automatically delivers a usableschedule based on the schedules proposed by the nurses. The study isperformed at a typical Swedish nursing ward, for which we havedeveloped a mathematical model and delivered schedules. The results ofthis study are very promising.

Publisher
29 p.
Series
LiTH-MAT-R, ISSN 0348-2960 ; 2008:8
Keyword
nurse scheduling, integer linear programming
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-57562 (URN)
Available from: 2008-10-28 Created: 2008-10-27 Last updated: 2013-08-30Bibliographically approved

Open Access in DiVA

fulltext(236 kB)3858 downloads
File information
File name FULLTEXT02.pdfFile size 236 kBChecksum SHA-512
0721fbf1fcda28938c5072c7648b1411022ca56d815f06cdc336dbe4bc1f4a51cd4c9c05d69cf1950218dd71e34377b7eaa07f96f05fd18209f4e9813f2bb521
Type fulltextMimetype application/pdf
cover(141 kB)72 downloads
File information
File name COVER01.pdfFile size 141 kBChecksum SHA-512
467d3cc251216b259892ef02216be46ffcf62421dd913e041320667baa94bb930adc2ad34516cd84770fbb9d96e01eb5b4e4e9dd5d55db360f96c941baa46e63
Type coverMimetype application/pdf

Authority records BETA

Rönnberg, Elina

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 3858 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2024 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf