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
A generic column generation principle: derivation and convergence analysis
Linköping University, Department of Mathematics, Optimization . Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0003-2094-7376
Luleå University of Technology, Sweden.
Chalmers, Sweden.
2015 (English)In: Operational Research, ISSN 1109-2858, E-ISSN 1866-1505, Vol. 15, no 2, 163-198 p.Article in journal (Refereed) Published
Abstract [en]

Given a non-empty, compact and convex set, and an a priori defined condition which each element either satisfies or not, we want to find an element belonging to the former category. This is a fundamental problem of mathematical programming which encompasses nonlinear programs, variational inequalities, and saddle-point problems. We present a conceptual column generation scheme, which alternates between solving a restriction of the original problem and a column generation phase which is used to augment the restricted problems. We establish the general applicability of the conceptual method, as well as to the three problem classes mentioned. We also establish a version of the conceptual method in which the restricted and column generation problems are allowed to be solved approximately, and of a version allowing for the dropping of columns. We show that some solution methods (e.g., Dantzig-Wolfe decomposition and simplicial decomposition) are special instances, and present new convergent column generation methods in nonlinear programming, such as a sequential linear programming type method. Along the way, we also relate our quite general scheme in nonlinear programming presented in this paper with several other classic, and more recent, iterative methods in nonlinear optimization.

Place, publisher, year, edition, pages
Springer Verlag (Germany) , 2015. Vol. 15, no 2, 163-198 p.
Keyword [en]
Convex programming; Variational inequality problems; Saddle-point problems; Column generation; Simplicial decomposition; Dantzig-Wolfe decomposition; Sequential linear programming
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-120161DOI: 10.1007/s12351-015-0171-3ISI: 000356353900001OAI: oai:DiVA.org:liu-120161DiVA: diva2:841508
Available from: 2015-07-13 Created: 2015-07-13 Last updated: 2017-12-04

Open Access in DiVA

fulltext(408 kB)93 downloads
File information
File name FULLTEXT01.pdfFile size 408 kBChecksum SHA-512
b9673095c1d038aafffeeef383234e25c20b6010c6b5f71de39cdb961f1e0f5124461b8df77d9eb24195901c2cb07fa044dd9831a2a9d47deb3d62e9a09c61ca
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Larsson, Torbjörn

Search in DiVA

By author/editor
Larsson, Torbjörn
By organisation
Optimization Faculty of Science & Engineering
In the same journal
Operational Research
Mathematics

Search outside of DiVA

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