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

Richard P. O'Neill and William B. Widhelm
Additional contact information
Richard P. O'Neill: Louisiana State University, Baton Rouge, Louisiana
William B. Widhelm: University of Maryland, College Park, Maryland

Operations Research, 1975, vol. 23, issue 2, 372-382

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.

Date: 1975
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.23.2.372 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:23:y:1975:i:2:p:372-382

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().