Gilmore-Lawler bound of quadratic assignment problem

Abstract

The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.

Keywords

Quadratic assignment problem (QAP) / Gilmore-Lawler bound, computational complexity / NP-hard

References

[1] Anstreicher K. M. Recent advances in the solution of quadratic assignment Problems. Mathematical Programming, Ser B, 2003, 97: 24-42.

[2] Brüngger A., Marzetta A., Clausen J. Solving large-scale QAP problems in parallel with the search library ZRAM. J Parallel and Distributed Com, 1998, 50: 157-169.

[3] Burkard R. E. Mirchandani P. B., Francis R. L. Locations with spatial interactions: The quadratic assignment problem. Discrete Location Theory, 1991, New York: Wiley, 387-437.

[4] Burkard R. E., Çela E., Pardalos P. M. Du D., Pardalos P. M. The quadratic assignment Problem. Handbook of Combinatorial Optimization, 1998, Dordrecht: Kluwer, 241-337.

[5] Burkard R. E., Derigs U. Assignment and Matching Problems: Solution Methods with Fortran Programs. Lecture Notes in Economics and Mathematical Systems, 1980, Berlin: Springer.

[6] Çela E. The Quadratic Assignment Problem: Theory and Algorithms, 1998, Dordrecht: Kluwer Academic Publishers.

[7] Clausen J., Perregaard M. Solving large quadratic assignment problems in parallel. Computational Optimization and Applications, 1997, 8: 111-127.

[8] Gilmore P. C. Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM Journal on Applied Mathematics, 1962, 10: 305-313.

[9] Hardy G. G., Littlewood J. E., Pólya G. Inequalities, 1952, London and New York: Cambridge University Press.

[10] Koopmans T. C., Beckmann M. J. Assignment problems and the location of economic activities. Econometrica, 1957, 25: 53-76.

[11] Lawler E. L. The quadratic assignment problem. Management Science, 1963, 9: 586-599.

[12] Li Y., Pardalos P. M. Generating quadratic assignment test problems with known optimal permutations. Computational Optimization and Applications, 1992, 1(2): 163-184.

[13] Li Y., Pardalos P. M., Ramakrishnan K. G. Lower bounds for the quadratic assignment problem. Annals of Operations Research, 1994, 50: 387-411.

[14] Loiola E. M., Abreu N. M. M., Boaventura-Netto P. O. An analytical survey for the quadratic assignment problem. European Journal of Operational Research, 2007, 176: 657-690.

[15] Mautor T., Roucairol C. A. New exact algorithm for the solution of quadratic assignment problems. Dis App Math, 1994, 55: 281-293.

[16] Pardalos P. M., Pitsoulis L. S. Nonlinear Assignment Problems: Algorithms and Applications, 2000, Boston: Kluwer Academic Publishers.

[17] Pardalos P. M., Ramarkrishnan K. G., Resende M. G. C. Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem. SIAM J Optim, 1997, 7: 280-294.

[18] Pardalos P. M., Rendl F., Wolkowicz H. Pardalos P. M., Wolkowicz H. The quadratic assignment problem: A survey and recent developments. Quadratic Assignment and Related Problems, 1994, Providence: AMS, 1-42.

[19] Sahni S., Gonzalez T. P-complete approximation problems. Journal of the Association of Computing Machinery, 1976, 23: 555-565.

[20] Xia Y. Improved Gilmore-Lawler bounds for quadratic assignment problems. Chinese Journal of Engineering Mathematics, 2007, 24(3): 401-413.

[21] Xia Y., Yuan Y. A new linearization method for quadratic assignment problems. Optimization Methods and Software, 2006, 21(5): 803-816.