A new polynomial-time implementation of the out-of-kilter algorithm using Minty’s lemma

It is less well known how to use the out-of-kilter idea to solve the min-cost flow problem because the generic version of the out-of-kilter algorithm runs in exponential time, although it is the sort of algorithm that computers can do easily. Ciupala (2005) presented a scaling out-of-kilter algorithm that runs in polynomial time using the shortest path computation in each phase. In this paper, we present a new polynomial time implementation of out-of-kilter idea. The algorithm uses a scaling method that is different from Ciupala’s scaling method. Each phase of Ciupala’s method needs a shortest path computation, while our algorithm uses Minty’s lemma to transform all the out-of-kilter arcs into in-kilter arcs. When the given network is infeasible, Ciupala’s algorithm does not work, but our algorithm presents some information that helps to repair the infeasible network.