This paper addresses the problem of determining all optimal integer solutions of a linear integer network flow problem, which we call the all optimal integer flow (AOF) problem. We derive an O(F (m + n) + mn + M ) time algorithm to determine all F many optimal integer flows in a directed network with n nodes and m arcs, where M is the best time needed to find one minimum cost flow. We remark that stopping Hamacher's well-known method for the determination of the K best integer flows at the first sub-optimal flow results in an algorithm with a running time of O(F m(n log n + m) + M ) for solving the AOF problem. Our improvement is essentially made possible by replacing the shortest path sub-problem with a more efficient way to determine a so called proper zero cost cycle using a modified depth-first search technique. As a byproduct, our analysis yields an enhanced algorithm to determine the K best integer flows that runs in O(Kn3 + M ). Besides, we give lower and upper bounds for the number of all optimal integer and feasible integer solutions. Our bounds are based on the fact that any optimal solution can be obtained by an initial optimal tree solution plus a conical combination of incidence vectors of all induced cycles with bounded coefficients.
翻译：本文涉及确定线性整网流问题所有最佳整数解决方案的问题,我们称之为所有最佳整数流问题。我们用O(F(nlog n+m)+m +M)时间算法来确定有n节点和 m Arcs 的定向网络中所有F(m)+n+m+M)最佳整数流。M是找到一个最低成本流的最佳时间。我们指出,在第一个次最佳流中,阻止哈马赫确定K最佳整数流的著名方法的结果是,一种运行时间为O(F(nlog n+m)+M)的算法,用于解决AOO(F(nlog n+m)+m +M)的问题。我们之所以能够作出改进,基本上是通过以更有效的方法取代最短路径次整数的次整数,从而确定所谓的适当零费用循环,使用经修改的深度第一搜索技术。作为副产品,我们的分析产生一种更先进的算法,用以确定在O(K3+M)中运行的K最佳整数流。此外,我们对所有最佳整数的最佳整数和最可行的整数的混合的混合解决办法都具有约束性。
相关内容
微信扫码咨询专知VIP会员