Interior methods for nonlinear minimum cost network flow problems

In this paper the authors propose practical algorithms for solving the nonlinear minimum cost network flow problem which has many fields of application such as production-distribution systems, pipe network systems, and communication systems. Here they assume that the problem is defined on an open subset of the affine subspace corresponding to the flow conservation equations. This assumption offers great flexibility in choosing a basis to represent feasible solutions, and the conventional capacitated network flow problems can be put into this framework by exploiting an interior penalty function technique. The algorithms proposed in this paper belong to the class of feasible descent methods which successively generate search directions based on the idea of Newton method. The authors give some practical strategies of determining search directions which approximate solutions of Newton equations. They also discuss ways of maintaining a desirable basis which makes those strategies effective. The authors examined the efficiency of the algorithms by means of some computational experiments. The proposed algorithms could practically solve a problem with more than 500 nodes and 1500 arcs, which is quite large as a nonlinear optimization problem.