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

摘要

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