Acceleration of Lagrangian Column-Generation Algorithms by Penalty Function Methods

Abstract

A Lagrangian column-generation procedure is developed which retains the original problem functions for column generation but uses transformed penalty functions in the Lagrangian optimization. The class of penalty functions considered maintains the original order of differentiability and often enhances the optimization operation. Convergence is proven for convex problems and limited computational experience cited where the new procedure converges two to four times faster than the standard method. Certain modifications of these techniques to attack nonconvex problems are also presented.