Minimum-Cost Multicommodity Flow

Pierre Chardaire and Abdel Lisser

ABSTRACT

We present a number of specializations of simplex and interior-point-based techniques for the solution of minimum-cost multicommodity flow models. These specializations exploit price-directive decomposition, resource-directive decomposition, and partitioning of linear systems. They are illustrated by considering a nonoriented minimum-cost multicommodity flow model of interest to telecommunication network design.