Assignment and Matching Problems: Solution Methods with FORTRAN-Programs

Assignment and matching problems belang to those cornbinatorial opti- mization problems which are weIl understood in theory and have many applications in practice. Since a research group qf the Mathematical Institute in Cologne has worked in this field for several years, we feIt that a publication of the developed procedures and algorithms would be useful, both for further research and academic tu': tion as weIl as for applications in practice.
This book covers linear assignment problems wi th SUfi and bottleneck objective functions, cardinality matching problems, perfect matching problems with SUffi and bottleneck objective functions, the Chinese postman problem and optimal as weIl as heuristic algorithms for the quadratic assignment problem. Every problem will be first described in short and then a FORTRAN-routine is given for it, which is docu- mented in detail and illustrated by test exarnples.
Many helped us through the years to develop efficient codes for the above rnentioned problems. Our special thanks go to T. Bönniger and G. Katzakidis who helped us in compiling the final vers ions and by performing extensive computational tests of the computer programs.
The development of these computer codes would not have been possible without the excellent facilities of the Computer Center of the Uni- versity of Cologne. All programs were thoroughly tested on the CDC CYBER 76 installation of this computer center. Independent test runs were perfarmed on the IBM 4331 installation in the Institut for Ökonometrie and Operations Research, University of Bonn. We are very indepted to Prof. B. Korte and Dr. Grätschei, Bann, for their assist- ance in having these test runs perforrned. Further we thank Prof. Th. Meis, Köln, for the permission to use his sorting routine SSORT as a subroutine in our programs