A Dual Framework for Lower Bounds of the Quadratic Assignment Problem Based on Linearization |
| |
| Authors: | S. E. Karisch E. Çela J. Clausen T. Espersen |
| |
| Affiliation: | (1) Carmen Systems AB, Odinsgatan 9, S-411 03 Gothenburg, Sweden , SE;(2) Technical University Graz, Department of Mathematics, Steyrergasse 30, A-8010 Graz, Austria , AT;(3) Department of Computer Science, University of Copenhagen, Universitetsparken 1, DK-2100 Copenhagen, Denmark , DK;(4) Boarding Data A/S, Naverland 1C, DK-2600 Glostrup, Denmark , DK |
| |
| Abstract: | A dual framework allowing the comparison of various bounds for the quadratic assignment problem (QAP) based on linearization, e.g. the bounds of Adams and Johnson, Carraresi and Malucelli, and Hahn and Grant, is presented. We discuss the differences of these bounds and propose a new and more general bounding procedure based on the dual of the linearization of Adams and Johnson. The new procedure has been applied to problems of dimension up to , and the computational results indicate that the new bound competes well with existing linearization bounds and yields a good trade off between computation time and bound quality. Received: February 5, 1999; revised August 24, 1999 |
| |
| Keywords: | AMS Subject Classifications:90C27 90B80 90C11. |
| 本文献已被 SpringerLink 等数据库收录！ |
|
