A New Alternating Basis Algorithm for Semi-Assignment Networks.

摘要

During the early 1970's, highly efficient special purpose computer codes were developed for solving capacitated transshipment problems based on primal extreme point algorithms. Computational comparisons disclosed that these codes were substantially superior to the best non-extreme point codes both in terms of computer time and memory requirements on all types of network problems. More recently, non-extreme point codes have been developed that are highly specialized for specific types of uncapacitated bipartite problems--notably assignment and semi-assignment problems. Comparisons of these problem specific codes with the earlier general purpose codes have raised the question of whether non-extreme point methods may not be superior to primal extreme point methods in application to these special network problem types. Consequently, the purpose of this paper is twofold: (i) to develop a new primal extreme point algorithm which is specifically designed to take advantage of the bipartite and boolean flow structures of assignment and semi-assignment problems, and (ii) to conduct an unbiased comparison of the alternative algorithmic approaches for solving assignment and semi-assignment problems.