title: A deterministic annealing algorithm for the minimum concave cost network flow problem.
abstract: The existing algorithms for the minimum concave cost network flow problems mainly focus on the single-source problems. To handle both the single-source and the multiple-source problem in the same way, especially the problems with dense arcs, a deterministic annealing algorithm is proposed in this paper. The algorithm is derived from an application of the Lagrange and Hopfield-type barrier function. It consists of two major steps: one is to find a feasible descent direction by updating Lagrange multipliers with a globally convergent iterative procedure, which forms the major contribution of this paper, and the other is to generate a point in the feasible descent direction, which always automatically satisfies lower and upper bound constraints on variables provided that the step size is a number between zero and one. The algorithm is applicable to both the single-source and the multiple-source capacitated problem and is especially effective and efficient for the problems with dense arcs. Numerical results on 48 test problems show that the algorithm is effective and efficient.
authors.affiliation: Department of Manufacturing Engineering & Engineering Management, City University of Hong Kong, Hong Kong, China. mecdang@cityu.edu.hk
authors.forename: Chuangyin
authors.initials: C
authors.lastname: Dang
authors.forename: Yabin
authors.initials: Y
authors.lastname: Sun
authors.forename: Yuping
authors.initials: Y
authors.lastname: Wang
authors.forename: Yang
authors.initials: Y
authors.lastname: Yang
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D016571:Neural Networks, Computer