A Generic Column Generation Scheme

Torbjörn Larsson, Athanasios Migdalas, and Michael Patriksson

Division of Optimization 
Department of Mathematics 
Linköping Institute of Technology
S-581 83 Linköping 
Sweden

ABSTRACT:

Given a non-empty, compact and convex set, and an a priori defined condition 
which each and one of the elements of the set either satisfies or not, we 
consider the problem of finding an element belonging to the former category. 
This is a generic and fundamental problem of mathematical programming which 
encompasses as special cases problem classes such as nonlinear programs, 
variational inequalities, and saddle point problems. 
For its solution, we present a conceptual column generation scheme, which 
alternates between the solution of restrictions of the original problem and 
an auxiliary problem which is used to augment the restricted problems. 
This scheme extends the class of simplicial decomposition method to a large 
problem class and generalizes it in the respect that its linear programming 
subproblem is replaced by the quite general auxiliary problem. 
We give a basic convergence result and establish the applicability of the 
conceptual scheme to the three problem classes mentioned.
We also prove convergence of a truncated version of the scheme, in which the  
restricted and auxiliary problems are allowed to be solved approximately.
As an illustration of the generality of the conceptual column generation 
scheme, it is used to show that the Dantzig--Wolfe decomposition method for 
linear programming can be viewed as a an application of a simplicial 
decomposition approach to the primal-dual saddle point formulation of 
a linear program.

KEY WORDS: Linear Programming, Nonlinear Programming, Variational Inequality 
Problems, Saddle Point Problems, Column Generation, Frank--Wolfe Method, 
Simplicial Decomposition, Dantzig--Wolfe decomposition