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
Column generation using non-optimal dual solutions: Optimality conditions and over-generation
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
(English)Manuscript (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 [en]
Binary program, column generation, optimality conditions, overgeneration
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-76090OAI: oai:DiVA.org:liu-76090DiVA: diva2:512198
Available from: 2012-03-26 Created: 2012-03-26 Last updated: 2013-08-30Bibliographically 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

No 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
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

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