Department of Manufacturing Engineering & Engineering Management, City University of Hong Kong, Hong Kong, China.
Neural Netw. 2011 Sep;24(7):699-708. doi: 10.1016/j.neunet.2011.03.018. Epub 2011 Mar 26.
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.
现有的最小凹成本网络流问题算法主要集中在单源问题上。为了以相同的方式处理单源和多源问题，特别是密集弧问题，本文提出了一种确定性退火算法。该算法源于拉格朗日和霍普菲尔德型障碍函数的应用。它由两个主要步骤组成：一个是通过使用全局收敛迭代过程更新拉格朗日乘子来找到可行的下降方向，这是本文的主要贡献，另一个是在可行的下降方向上生成一个点，如果步长在 0 和 1 之间，则该点始终自动满足变量的上下限约束。该算法适用于单源和多源容量问题，对于密集弧问题尤其有效和高效。对 48 个测试问题的数值结果表明，该算法是有效和高效的。
