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

Direct link
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.

Keyword [en]
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)oai:DiVA.org:liu-15287 (OAI)
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
In thesis
1. Methods and Applications in Integer Programming
Open this publication in new window or tab >>Methods and Applications in Integer Programming : All-Integer Column Generation and Nurse Scheduling
2008 (English)Licentiatavhandling, sammanläggning (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.

Linköping: Linköping University Electronic Press, 2008. 16 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1383
Keyword
integer programming, column generation, set partitioning problems, quasi-integrality, nurse scheduling
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-15143 (URN)978-91-7393-760-3 (ISBN)
Presentation
2008-11-21, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from2008-11-05 Created:2008-10-30 Last updated:2013-08-30Bibliographically approved
2. Contributions within two topics in integer programming
Open this publication in new window or tab >>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.

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)
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

Open Access in DiVA

fulltext(203 kB)292 downloads
File information
File name FULLTEXT01.pdfFile size 203 kBChecksum SHA-512
aa089f211e16514bb4c7abf788fc74c9812a4d8de251986cdf54583d2202419f9a0791414cbb523f7d196232a3bfa3d82795a16a8878f59aaece21a9c3dd3497
Typ fulltextMimetype application/pdf

Other links

Publisher's fulltexthttp://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-15143

Search in DiVA

By author/editor
Rönnberg, ElinaLarsson, Torbjörn
By organisation
Department of MathematicsThe Institute of Technology
In the same journal
European Journal of Operational Research
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Totalt: 292 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

Citations

Web of Science®:

Altmetric score

Totalt: 1138 hits
ReferencesLink to record
Permanent link

Direct link