ON NETWORK FLOW PROBLEMS WITH CONVEX COST

Abstract

Minimum cost flow (MCF) problem is a typical example of network flow problems, for which an additional constraint of cost is added to each flow. Conventional MCF problems consider the cost constraints as linear functions of flow. In this paper, we extend the MCF problem to cover cost functions as strictly convex and differentiable, and refer to the problem as convex cost flow problem. To address this problem, we derive the optimality conditions for minimising convex and differentiable cost functions, and devise an algorithm based on the primal-dual algorithm commonly used in linear programming. The proposed algorithm minimises the total cost of flow by incrementing the network flow along augmenting paths of minimum cost. Simulation results are provided to demonstrate the efficacy of the proposed algorithm.