Technical Note—Computational Experience with Normed and Nonnormed Column-Generation Procedures in Nonlinear Programming

Abstract

Nemhauser and Widhelm have suggested a normed variant of the Dantzig-Wolfe convex programming algorithm. The normalization explicitly occurs in the multiplier-space. There the interior point used to generate the next cut is one that maximizes the minimum slack from the present cuts to that point. Nemhauser and Widhelm suggested this normalization for two reasons. First, since the corresponding cut at worst includes the generating point, choosing that point “centered” in some geometric sense should result in a generally efficient reduction in the feasible search region. Second, cuts not active in defining the present feasibility region can affect the choice of the interior-point if norming is not applied. This note demonstrates how primal feasible points can be generated at each iteration and cites limited computational results indicating that the normed procedure is generally more efficient than the original algorithm from the standpoint of both the number of iterations and computational time.