Convergence behavior of decomposition algorithms for linear programs
type: Item
instance of: scholarly article
title: Convergence behavior of decomposition algorithms for linear programs
zbMATH Open document ID: 0547.90067
DOI: 10.1016/0167-6377(84)90048-8
author: James K. Ho
published in: Operations Research Letters
publication date: 1984-01-01T00:00:00Z
review text: The Dantzig-Wolfe decomposition algorithm has rapid initial convergence but a rather slow one in the optimality approaching stage. It has been observed by the author's experience with problems from diverse applications that most problems actually converge after a very reasonable number of cycles to within rather tight tolerances. Those that do not tend to become such a behavior asymptotic. To date, problems that became asymptotic would be terminated at some point with the assumption that the algorithm will eventually converge if allowed to continue. It is argued that this may not be the case and that nonconvergence may be caused by numerical inaccuracy. It is shown that numerical inaccuracy and combinatorial complexity may tend to confound each other, to the extent that most observed ''long tails'' could indeed be all noise. Two auxiliary procedures for the decomposition algorithm to mitigate such difficulties are proposed.
Mathematics Subject Classification ID: 90C06
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3873077
zbMATH Keywords: convergence behavior
zbMATH Keywords: large scale systems
zbMATH Keywords: Dantzig-Wolfe decomposition algorithm
zbMATH Keywords: numerical inaccuracy
zbMATH Keywords: auxiliary procedures
MaRDI profile type: Publication
full work available at URL: 0167-6377(84)90048-8
OpenAlex ID: W2153050393
cites work: Experiences in Using a Decomposition Program
cites work: Q5538308
cites work: Decomposition Principle for Linear Programs
cites work: The Decomposition Algorithm for Linear Programs
cites work: Q3666564
cites work: Q3865834
cites work: An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming
cites work: Computational experience with advanced implementation of decomposition algorithms for linear programming
cites work: Computational aspects of DYNAMICO : a model of trade and development in the world economy
cites work: Nested decomposition for dynamic models
cites work: Q5630824
cites work: Numerical behavior of LP algorithms based upon the decomposition principle
cites work: Lösung großer linearer Regionalplanungsprobleme mit der Methode vonDantzig undWolfe
cites work: A Structured Linear Programming Model in the Food Industry
description: scientific article; zbMATH DE number 3873077