A scaling out-of-kilter algorithm for minimum cost flow in networks with positive lower bounds

Abstract

The out-of-kilter algorithm is one of the basic algorithms that solve the minimum cost flow problem. Its drawback is that it can improve the objective function at each iteration by a small value. Consequently, it runs in pseudo-polynomial time. In [?], we described a scaling out-of-kilter algorithm for minimum cost flow in networks without positive lower bounds that runs in polynomial time. There are several practical problems (see [?]) that can be reduced to the minimum cost flow problem in a network with positive lower bounds. That is the first reason for which, in this paper, we focus on the transformations that must be made to the scaling out-of-kilter algorithm in order to apply it in networks with positive lower bounds. The second reason for writing this paper is the versatility of the scaling out-of-kilter algorithm. Unlike most network flow algorithms (maximum flow algorithms, minimum cost flow algorithms etc.), for applying the scaling out-of-kilter algorithm in a network with positive lower bounds, we do not need to establish a feasible flow and to determine an equivalent network without positive lower bounds.