具有流量为零或介于上下界之间的二态组合约束最小费用流问题的算法

An algorithm for minimum cost flows satisfying binary feasible zone combinatorial constraint

对于各弧流量为零或者流量介于非零上下界之间的二态组合约束最小费用流问题,一般在穷举各种状态组合的基础上结合普通最小费用流算法求解 ,其复杂性为普通最小费用流问题复杂性的 2 |A| 倍 (式中 ,指数 |A|为弧的数目 ) .提出了一种新的算法 ,以具有相应上下界容量约束最小费用流问题的最优解为初值 ,构建残量网络 ,消除负费用圈 ,最后得到最优解 .该算法总的复杂性仅为普通最小费用流问题复杂性的

A special minimum cost flosw (MCF)problem,in which flow of each arc is zero or between nonzero minimum flow and maximun capacity,is often solved by enumerating whole combination of binary feasible zone of all arcs coupled with an algorithm for ordinary MCF.A simple algorithm is presented which finds the solution by reducing negative cost cycle within the residual network based on the optimal solution of binary-flow network problem.The complexity of the algorithm is much lower than that of other algorithms for MCF under binary feasible zone combinatorial constraint.