A bundle type dual-ascent approach to linear multicommodity min-cost flow problems

We present a Cost Decomposition approach for the linear Multicommodity Min- Cost Flow problem, where the mutual capacity constraints are dualized and t he resulting Lagrangean Dual Is solved with a dual-ascent algorithm belongi ng to the class of Bundle methods. Although decomposition approaches to bla ck-structured Linear Programs have been reported not to be competitive with general-purpose software, our extensive computational comparison shows tha t, when carefully implemented, a decomposition algorithm can outperform sev eral other approaches, especially on problems where the number of commoditi es is "large" with respect to the size of the graph. Our specialized Bundle algorithm is characterized by a new heuristic for the trust region paramet er handling, and embeds a specialized Quadratic Program solver that allows the efficient implementation of strategies for reducing the number of activ e Lagrangean variables. We also exploit the structural properties of the si ngle-commodity Min-Cost Flow subproblems to reduce the overall computationa l cost. The proposed approach can be easily extended to handle variants of the problem.