Solving multicommodity flow problems by an approximation scheme

Abstract

We study an approximation scheme to solve minimum cost multicommodity flow problems to a relative accuracy of epsilon is an element of (0, 1]. The proposed scheme, which we shall call Algorithm A, is a bisection-based procedure, so it maintains an interval that contains the optimal value. At each iteration, Algorithm A defines a block angular sharing problem that is solved to a relative accuracy of O(epsilon). The computed solution defines the current approximation to an optimal solution and it is used by Algorithm A to throw away half of the current interval. It is shown that when Algorithm A no longer shrinks the current interval, the current solution solves the minimum cost multicommodity flow problem to the given accuracy epsilon. To compute approximate solutions to the sharing problems that Algorithm A defines, we propose using Algorithm L from [J. Villavicencio and M. D. Grigoriadis, Approximate Lagrangian decomposition with a modified Karmarkar logarithmic potential, in Network Optimization, Lecture Notes in Econom. and Math. Systems 450, Springer, Berlin, 1997, pp. 471-485], but we replace its fixed small step size by one computed using inexact line searches. This modi. cation allows large steps in Algorithm L. We show that the coordination complexities of Algorithm L and Algorithm L with inexact line searches are the same if these algorithms are applied to the block angular sharing problems defined by Algorithm A. This result is also true for block angular sharing problems with convex blocks and with coupling constraints given by nonnegative linear functions.