Convergence behavior of decomposition algorithms for linear programs

DOI10.1016/0167-6377(84)90048-8MaRDI QIDQ799585zbMATH OpenOpenAlexFDO

Authors James K. Ho

Publication date 1984

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(84)90048-8

zbMATH Keywords

auxiliary proceduresconvergence behaviorDantzig-Wolfe decomposition algorithmlarge scale systemsnumerical inaccuracy

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Large-scale problems in mathematical programming (90C06)

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.

Recommendations

• Numerical behavior of LP algorithms based upon the decomposition principle
• Using central prices in the decomposition of linear programs
• Revised dantzig-wolfe decomposition for staircase-structured linear programs
• Decomposition in general mathematical programming
• The decomposition principle and algorithms for linear programming

Cites work

• A Structured Linear Programming Model in the Food Industry
• An advanced implementation of the Dantzig—Wolfe decomposition algorithm for linear programming
• Computational aspects of DYNAMICO : a model of trade and development in the world economy
• Computational experience with advanced implementation of decomposition algorithms for linear programming
• Decomposition Principle for Linear Programs
• Experiences in Using a Decomposition Program
• scientific article; zbMATH DE number 3819432 (Why is no real title available?)
• scientific article; zbMATH DE number 3668319 (Why is no real title available?)
• scientific article; zbMATH DE number 3249567 (Why is no real title available?)
• scientific article; zbMATH DE number 3356467 (Why is no real title available?)
• Lösung großer linearer Regionalplanungsprobleme mit der Methode vonDantzig undWolfe
• Nested decomposition for dynamic models
• Numerical behavior of LP algorithms based upon the decomposition principle
• The Decomposition Algorithm for Linear Programs

Cited in

(3)

• Numerical behavior of LP algorithms based upon the decomposition principle
• MSLiP: A computer code for the multistage stochastic linear programming problem
• Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design

This page was built for publication: Convergence behavior of decomposition algorithms for linear programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q799585)