The Alternating Basis Algorithm for Assignment Problems.

摘要

The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems. The new algorithm both circumvents and exploits degeneracy. Degeneracy difficulties of the standard primal simplex methods result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subset Q of all bases that are capable of leading to an optimal solution to the problem if one exists. The new algorithm is based on a special set of transition rules that make it possible to examine only bases in Q. The graph structure of Q imparts a number of computational advantages to the algorithm. A preliminary computer implementation, without refinement or investigation of alternative choice rules, is more efficient and uses less computer memory than the currently best implementations of out-of-kilter, primal-dual, and primal extreme point methods for assignment problems.