SOLVING NONLINEAR MULTICOMMODITY FLOW PROBLEMS BY THE ANALYTIC CENTERCUTTING PLANE METHOD

The paper deals with nonlinear multicommodity flow problems with conve x costs. A decomposition method is proposed to solve them. The approac h applies a potential reduction algorithm to solve the master problem approximately and a column generation technique to define a sequence o f primal linear programming problems. Each subproblem consists of find ing a minimum cost flow between an origin and a destination node in an uncapacited network, It is thus formulated as a shortest path problem and solved with Dijkstra's d-heap algorithm. An implementation is des cribed that takes full advantage of the supersparsity of the network i n the linear algebra operations. Computational results show the effici ency of this approach on well-known nondifferentiable problems and als o large scale randomly generated problems (up to 1000 arcs and 5000 co mmodities).