Finding minimum-cost circulations by successive approximation. (English) Zbl 0727.90024

The authors propose new algorithms for solving minimum cost circulation problems by cost scaling procedures and the iterative improvement of pseudoflows. Let the given circulation network be a symmetric digraph \(G=(V,E)\) with antisymmetric cost function \(c(v,w)=-c(w,v)\). A pseudoflow f: \(E\to {\mathbb{R}}\) fulfills capacity constraints f(v,w)\(\leq u(v,w)\) and antisymmetric flow constraints \(f(v,w)=-f(w,v)\). The pseudoflow is \(\epsilon\)-optimal with respect to a price function p: \(V\to {\mathbb{R}}\), iff \(c(v,w)+p(v)-p(w)\geq -\epsilon\) for all arcs (v,w) with \(f(v,w)<u(v,w).\)
Starting from \(\epsilon =\max c(v,w)=C\), \(p\equiv 0\) and f being an arbitrary circulation a refinement procedure returns a pseudoflow which is optimal for \(\epsilon\) /2. It is shown that the pseudoflow is a minimum cost circulation as soon as \(\epsilon <.\)
The authors describe two implementations of the refinement procedure, one by push and relabel operations, the other using blocking flows in an auxiliary network.
The investigations result in strongly polynomial minimum cost procedures with complexity O(nm log(n\({}^ 2/m)\min (\log nC\), m log n)). Further comments of the paper concern the use of advanced data structures like dynamic trees, parallel implementations and practical improvements.
Reviewer: R.E.Burkard (Graz)


90B10 Deterministic network models in operations research
90C60 Abstract computational complexity for mathematical programming problems
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI