A Bundle type Dual-ascent Approach to Linear Multi-Commodity Min Cost Flow Problems

We present a cost decomposition approach to Linear Multicommodity Min Cost Flow problems, based on dualizing the mutual capacity constraints: the resulting Lagrangean Dual is solved by means of a new, specialized Bundle type-dual ascent algorithm. Although decomposition approaches are generally believed not to be competitive, even for the solution of large-scale network structured problems, we present evidence based on extensive computational comparisons that a careful implementation of a decomposition algorithm can outperform several other approaches, especially on problems where the number of commodities is "large" w.r.t. the size of the graph. Our specialized Bundle algorithm is characterised by a new heuristic for the trust region parameter handling, and embeds a custom, fast Quadratic Programming solver that permits the implementation of a Lagrangean variables generation strategy. The Lagrangean Relaxation solver is capable of exploiting the structural properties of the single-commodity Min Cost Flow subproblems to avoid using a "generic" MCF solver whenever it is possible. The proposed approach can be easily extended to handle extra constraints or variants such as the Nonsimultaneous Multicommodity problem. In our computational experience, we also studied the impact on the relative efficiencies of the different approaches tested of some characteristics, such as the number of commodities w.r.t. the total size of the problem.