Convergence behavior of decomposition algorithms for linear programs (Q799585)

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.