Abstract
The purpose of this paper is to present a new primal extreme point algorithm for solving assignment problems which both circumvents and exploits degeneracy. The algorithm is based on the observation that the degeneracy difficulties of the simplex method result from the unnecessary inspection of alternative basis representations of the extreme points. This paper characterizes a subsetQ of all bases that are capable of leading to an optimal solution to the problem if one exists. Using this characterization, an extreme point algorithm is developed which considers only those bases inQ. Computational results disclose that the new algorithm is substantially more efficient than previously developed primal and primal-dual extreme point (“simplex”) methods for assignment problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.S. Barr, “Streamlining primal simplex transportation codes”, Research Rep., Center for Cybernetic Studies, University of Texas, Austin, TX, to appear.
R.S. Barr, F. Glover and D. Klingman, “Enhancements to spanning tree labeling procedures for network optimization”, Rep. 262, Center for Cybernetic Studies, University of Texas, Austin, TX.
R.S. Barr, F. Glover and D. Klingman, “An improved version of the out-of-kilter method and a comparative study of computer codes”,Mathematical Programming 7 (1) (1974) 60–87.
G. Bradley, G. Brown and G. Graves, “A comparison of storage structure for primal network codes”, presented at ORSA/TIMS conference, Chicago, April 1975.
G. Bradley, G. Brown and G. Graves, “Tailoring primal network codes to classes of problems with common structure”, ORSA/TIMS conference, Las Vegas (1975).
W.H. Cunningham, “A network simplex method”, Tech. Rep. No. 207, Dept. of Mathematical Sciences, Johns Hopkins University (1974).
F. Glover and D. Klingman, “Locating stepping-stone paths in distribution problems via the predecessor index method”,Transportation Science 4 (1970) 220–226.
F. Glover, D. Karney and D. Klingman, “Implementation and computational study on start procedures and basis change criteria for a primal network code”,Networks 4 (3) (1974) 191–212.
F. Glover, D. Karney and D. Klingman, “Augmented predecessor index method for location stepping stone paths and assigning dual prices in distribution problems”,Transportation Science 6 (1) (1972) 171–181.
F. Glover, D. Karney, D. Klingman and A. Napier, “A computational study on start procedures, basis change criteria, and solution algorithms for transportation problems”,Management Science 20 (5) (1974) 793–819.
F. Glover and D. Klingman, “Improved labeling of L.P. bases in networks”, Research Report CS 218, Center for Cybernetic Studies, University of Texas, Austin, TX (1974).
F. Glover, D. Klingman and J. Stutz, “Augmented threaded method”,Canadian Journal of Operational Research and Information Processing 12 (3) (1974) 293–298.
R.S. Hatch, “Optimization strategies for large scale assignment and transportation type problems”, ORSA/TIMS conference, San Juan, Puerto Rico (1974).
D. Klingman, A. Napier and J. Stutz, “NETGEN-A program for generating large scale (un)capacitated assignment, transportation, and minimum cost flow network problems”,Management Science 20 (5) (1974) 814–822.
J. Mulvey, “Column weighting factors and other enhancements to the augmented threaded index method for network optimization”, Joint ORSA/TIMS conference, San Juan, Puerto Rico (1974).
V. Srinivasan and G.L. Thompson, “Benefit-cost analysis of coding techniques for the primal transportation algorithm”,Journal of the Association of Computing Machines 20 (1973) 194–213.
V. Srinivasan and G.L. Thompson, “Accelerated algorithms for labeling and relabeling of trees with application for distribution problems”,Journal of the Association of Computing Machines 19 (4) (1972) 712–726.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barr, R.S., Glover, F. & Klingman, D. The alternating basis algorithm for assignment problems. Mathematical Programming 13, 1–13 (1977). https://doi.org/10.1007/BF01584319
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01584319