A distributed asynchronous relaxation algorithm for the assignment problem

Relaxation methods for optimal network flow problems resemble classical coordinate descent, Jacobi, and Gauss-Seidel methods for solving unconstrained non-linear optimization problems or systems of nonlinear equations. In their pure form they modify the dual variables (node prices) one at a time using only local node information while aiming to improve the dual cost. They are particularly well suited for distributed implementation on massively parallel machine. For problems with strictly convex arc costs they can be shown to converge even if relaxation at each node is carried out asynchronously with out-of-date price information from neighboring nodes 1. For problems with linear arc costs relaxation methods have outperformed by a substantial margin the classical primal simplex and primal-dual methods on standard benchmark problems 2, 3. However in these particular methods it is necessary to change sometimes the prices of several nodes as a group in addition to carrying out pure relaxation steps. As a result global node price information is needed occasionally, and distributed implementation becomes somewhat complicated. In this paper we describe a distributed algorithm for solving the classical linear cost assignment problem. It employs exclusively pure relaxation steps whereby the prices of sources and sinks are changed individually on the basis of only local (neighbor) node price information. The algorithm can be implemented in an asynchronous (chaotic) manner, and seems quite efficient for problems with a small arc cost range. It has an interesting interpretation as an auction where economic agents compete for resources by making successively higher bids.