A Scaling Algorithm for Multicommodity Flow Problems

We present a penalty-based algorithm that solves the multicommodity flow problem as a sequence of a finite number of scaling phases. The basis of the algorithm is simple and consists of iteratively detecting and sending flow around negative cost cycles. Two parameters control the algorithm's behavior: the penalty parameter and the scaling parameter. In the ε-scaling phase, where ε is a function of the penalty and scaling parameters, the algorithm determines an ε-optimal solution; a solution in which complementary slackness conditions are satisfied to within ε. We analyze the performance of the algorithm from both the theoretical and practical perspectives. The computational results support the theoretical behavior of the algorithm. They also demonstrate the efficiency of the algorithm for solving problem instances of different structure and size.