Groupe d’études et de recherche en analyse des décisions


A strongly polynomial Contraction-Expansion algorithm for network flow problems

, et

This paper addresses the resolution of the capacitated minimum cost flow problem on a network containing \(n\) nodes and \(m\) arcs. Verifying necessary and sufficient optimality conditions can be done on the residual network although it can be quite time consuming as testified by the minimum mean cycle-canceling algorithm. We introduce a contracted network which exploits these conditions on a much smaller network. Since the construction of this contracted network is very flexible, we study its properties depending on the construction choice. A generic contraction algorithm is then produced around the contracted network. Interestingly enough, it turns out it encapsulates both the minimum mean cycle-canceling and primal network simplex algorithms. By guiding the resolution using a particular expansion scheme, we are able to recuperate theoretical results from the minimum mean cycle-canceling algorithm. As such, we obtain a strongly polynomial Contraction-Expansion algorithm which runs in \(O(m^3n^2)\) time. The algorithmic choices stick to very practical observations of the minimum mean cycle-canceling algorithm's resolution behavior yet are not exploited by latter, namely that of phases and jumps on the optimality parameter. The resolution time is ultimately significantly reduced, even more so as the size of the instance increases.

, 28 pages