NETWORK OPTIMIZATION WITH PIECEWISE LINEAR CONVEX COSTS

Abstract

The problem of finding the minimum cost multi-commodity flow in an undirected and completenetwork is studied when the link costs are piecewise linear and convex. The arc-path model and overflowmodel are presented to formulate the problem. The results suggest that the new overflow model outperformsthe classical arc-path model for this problem. The classical revised simplex, Frank and Wolf and a heuristicmethod are compared for the problem.