A Shortest Augmenting Path Algorithm for the Semi-Assignment Problem

Publisher Website
Google Scholar
Abstract
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 arc 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 our algorithm are fastest for the semi-assignment problems that we tested. Our 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 we have seen; and the memory requirements are relatively small.

This publication has 0 references indexed in Scilit: