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
All-integer column generation: Basic principles and extensions
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
2014 (English)In: European Journal of Operational Research, ISSN 0377-2217, E-ISSN 1872-6860, Vol. 233, no 3, 529-538 p.Article in journal (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.

Place, publisher, year, edition, pages
Elsevier, 2014. Vol. 233, no 3, 529-538 p.
Keyword [en]
Set partitioning, meta-heuristic, column generation, quasiintegrality, surrogate columns, over-generation, all-integer pivots
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-76091DOI: 10.1016/j.ejor.2013.08.036ISI: 000328180200006Local ID: urn:nbn:se:liu:diva-102966OAI: oai:DiVA.org:liu-76091DiVA: diva2:512199
Note

On the day of the defence date the status of this article was Manuscript with the title All-integer column generation: A meta-heuristic for set partitioning problems.

Available from: 2012-03-26 Created: 2012-03-26 Last updated: 2017-12-07Bibliographically approved
In thesis
1. Contributions within two topics in integer programming: nurse scheduling and column generation
Open this publication in new window or tab >>Contributions within two topics in integer programming: nurse scheduling and column generation
2012 (English)Doctoral thesis, comprehensive summary (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, edition, 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)
Public defence
2012-05-10, Visionen, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Available from: 2012-03-28 Created: 2012-03-26 Last updated: 2013-08-30Bibliographically approved

Open Access in DiVA

fulltext(506 kB)491 downloads
File information
File name FULLTEXT01.pdfFile size 506 kBChecksum SHA-512
bafbdecbd66bdd6acb7b85eac07f519599932f76f0a62e4c6eb2ea7a89ff984fb7b62fc3ad23b1103332300f29e943d66361ad756df51d1bb5b9b4527c8f970a
Type fulltextMimetype application/pdf

Other links

Publisher's full text

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
In the same journal
European Journal of Operational Research
Computational Mathematics

Search outside of DiVA

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

doi
urn-nbn

Altmetric score

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