The Alternating Basis Algorithm for Assignment Problems.
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1977
- Accession Number
- ADA035919
Entities
People
- Darwin Dee Klingman
- Fred W. Glover
- Richard S. Barr
Organizations
- University of Texas at Austin