Simplicial Decomposition Algorithms with Nonlinear Column Generation

Torbjörn Larsson, Michael Patriksson, and Clas Rydergren

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

ABSTRACT:

The simplicial decomposition method for linearly constrained nonlinear
programs has been proven to be efficient for certain classes of structured
large-scale problems.  This method alternates between a multi-dimensional
search over a restriction of the feasible set and an augmentation of the
restriction through the solution of a linear column generation problem.
The quality of the columns generated may however be very poor, 
since the first-order approximation of the objective function is used
globally. 

As a means for improving the quality of the columns in a simplicial 
decomposition method, we consider using {\em nonlinear\/} 
(e.g., second-order) approximations of 
the objective function in the augmentation phase.  This modification
leads to the generation of non-extreme point columns.
The new method is applied to two nonlinear network flow models: the traffic
assignment problem and the stochastic transportation problem.  Numerical 
experiments indicate that significant time and storage savings can be gained
from the proposed modification. 
These observations are particularly interesting due to the fact that
similar nonlinearities may be incorporated in 
any column generation scheme.