Methods for Large Optimal Assignment problems with sparse connections

Question

I have an assignment problem involving about 2 million workers and 2 million jobs. Thus the cost matrix has 4x10^12 elements. A standard approach would be the Hungarian algorithm (Munkres Algorithm), but a simple application in my case is not feasible because the memory required is prohibitive. (Although it works great for smaller subsets of the problem I would actually like to solve.)

However, for my problem the cost matrix is sparse. There is a strip of nonzero elements running diagonally down the matrix as indicated in this sketch: (EDIT: this is actually a profit matrix. Off of the diagonal strip the costs for pairing are infinite)

I would like to find the optimal assignment of works to jobs (sum of costs is mininum). Are there any standard approaches to deal with such a problem which is too large to fit into my computer's memory all at once? I figure there must be specialized approaches for problems in operations management or cybernetics. Any help is greatly appreciated. Thanks

Answer 1

For solving the assignment problem it is not necessary to store the matrix explicitly, although the Hungarian algorithm for simplicity is often presented in this form. Jonker & Volgenant, for example, present an implementation the performs well on sparse matrices.

Answer 2

If mathematical optimality is not required, the go to would be metaheuristics.

These are classes of algorithms that can find the optimum solution, but there is no mathematical guarantee. Generally speaking, they do find the optimum for small datasets and near optimum for larger datasets.