To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

A generic column generati… - University of Gothenburg, Sweden Till startsida
To content Read more about how we use cookies on

A generic column generation principle: derivation and convergence analysis

Journal article
Authors Torbjörn Larsson
Athanasios Migdalas
Michael Patriksson
Published in Operational Research: An International Journal
Volume 15
Issue 2
Pages 163-198
ISSN 1109-2858
Publication year 2015
Published at Department of Mathematical Sciences, Mathematics
Pages 163-198
Language en
Keywords Convex programming; Variational inequality problems; Saddle-point problems; Column generation; Simplicial decomposition; Dantzig-Wolfe decomposition; Sequential linear programming
Subject categories Numerical analysis, Optimization, systems theory


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 (SLP) 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.

Page Manager: Webmaster|Last update: 9/11/2012

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?