On the K best integer network flows

摘要

We address the problem of finding the K best integer solutions of a linear integer network flow problem. We design an O(f(n,m,L,U)+KmS(n,m,L)) time and 0(K+m) memory space algorithm to determine the K best integer solutions, in a directed network with n nodes, m arcs, maximum absolute value cost L, and an upper bound U on arc capacities and node supplies. f(n,m,L,U) is the best time needed to solve the minimum cost flow problem in a directed network and S(n,m,L) is the best time to solve the single-source shortest path problem in a network with non-negative lengths. The introduced algorithm efficiently determines a "proper minimal cycle" by taking advantage of the relationship between the best solutions. This way, we improve the theoretical as well as practical memory space bounds of the well-known method due to Hamacher. Our computational experiments confirm this result.