Minimum-Cost Multicommodity Network Flows

Abstract

The minimum-cost multicommodity network flow problem is formulated in both node-arc and arc-chain form, leading to very large linear programs. The special structure of these programs is utilized in algorithms for their solution.