A shortest augmenting path algorithm for the semi-assignment problem

The objective of this study is to develop a shortest augmenting path algorithm for solving the semi-assignment problem and conduct an extensive computational comparison with the best alternative approaches. The algorithm maintains dual feasibility and complementary slackness and works toward satisfying primal feasibility. Effective heuristics are used to achieve an excellent advanced start, and convergence is assured via the use of the shortest augmenting path procedure using reduced costs for arc lengths. Unlike other algorithms, such as the primal simplex or the auction algorithm, each iteration during the final phase of the procedure (also known as the end-game) achieves one additional assignment. The software implementations of the present algorithm are fastest for the semi-assignment problems that the authors tested. The dense code is also faster than the best software for assignment problems. In addition, the algorithm has the best polynomial worst-case running time bound that the authors have seen; and the memory requirements are relatively small.