# 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.