A deterministic annealing algorithm for the minimum concave cost network flow problem

✍ Scribed by Chuangyin Dang; Yabin Sun; Yuping Wang; Yang Yang

• Publisher: Elsevier Science
• Year: 2011
• Tongue: English
• Weight: 292 KB
• Volume: 24
• Category: Article
• ISSN: 0893-6080
• DOI: 10.1016/j.neunet.2011.03.018

✦ Synopsis

The existing algorithms for the minimum concave cost network flow problems mainly focus on the singlesource 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.