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
An All-Integer Column Generation Methodology for Set Partitioning Problems
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0003-2094-7376
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.

Place, publisher, year, edition, pages
2008. , 23 p.
Series
Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960
Keyword [en]
integer programming, column generation, quasi-integrality, surrogate columns, over-generation
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-15256OAI: oai:DiVA.org:liu-15254DiVA: diva2:113790
Available from: 2008-10-28 Created: 2008-10-27 Last updated: 2013-08-30Bibliographically approved
In thesis
1. Methods and Applications in Integer Programming: All-Integer Column Generation and Nurse Scheduling
Open this publication in new window or tab >>Methods and Applications in Integer Programming: All-Integer Column Generation and Nurse Scheduling
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
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 from: 2008-11-05 Created: 2008-10-30 Last updated: 2013-08-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Link to Licentiate Thesis

Authority records BETA

Rönnberg, ElinaLarsson, Torbjörn

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 406 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