Algorithm 1015: A Fast Scalable Solver for the Dense Linear (Sum) Assignment Problem

We present a new algorithm for solving the dense linear (sum) assignment problem and an efficient, parallel implementation that is based on the successive shortest path algorithm. More specifically, we introduce the well-known epsilon scaling approach used in the Auction algorithm to approximate the dual variables of the successive shortest path algorithm prior to solving the assignment problem to limit the complexity of the path search. This improves the runtime by several orders of magnitude for hard-to-solve real-world problems, making the runtime virtually independent of how hard the assignment is to find. In addition, our approach allows for using accelerators and/or external compute resources to calculate individual rows of the cost matrix. This enables us to solve problems that are larger than what has been reported in the past, including the ability to efficiently solve problems whose cost matrix exceeds the available systems memory. To our knowledge, this is the first implementation that is able to solve problems with more than one trillion arcs in less than 100 hours on a single machine.

Automated summary

The algorithm presented in this study introduces the ε-scaling method to improve the efficiency of solving dense linear assignment problems. It significantly reduces the runtime for solving real-world problems and allows for the use of accelerators and external compute resources for handling larger problem sets. This implementation is capable of solving problems with over one trillion arcs in less than 100 hours on a single machine.