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 pseudo-polynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.

References

1. Anstreicher K M Recentadvances in the solution of quadratic assignment ProblemsMathematical Programming, Ser B 2003 972442
2. Brüngger A Marzetta A Clausen J et al.Solving large-scale QAP problems in parallel withthe search library ZRAMJ Parallel and DistributedCom 1998 50157169. doi:10.1006/jpdc.1998.1434
3. Burkard R E Locationswith spatial interactions: The quadratic assignment problemIn: Mirchandani P BFrancis R LDiscrete Location TheoryNew YorkWiley 1991 387437
4. Burkard R E Çela E Pardalos P M et al.The quadratic assignment ProblemIn: Du DingzhuPardalos P MHandbook of Combinatorial Optimization, Vol 3DordrechtKluwer 1998 241337
5. Burkard R E Derigs U Assignment and Matching Problems:Solution Methods with Fortran Programs. Lecture Notes in Economicsand Mathematical Systems, Vol 184BerlinSpringer 1980
6. Çela E TheQuadratic Assignment Problem: Theory and Algorithms Dordrecht Kluwer Academic Publishers 1998
7. Clausen J Perregaard M Solving large quadratic assignmentproblems in parallelComputational Optimizationand Applications 1997 8111127. doi:10.1023/A:1008696503659
8. Gilmore P C Optimaland suboptimal algorithms for the quadratic assignment problemSIAM Journal on Applied Mathematics 1962 10305313. doi:10.1137/0110022
9. Hardy G G Littlewood J E Pólya G InequalitiesLondon and NewYorkCambridge University Press 1952
10. Koopmans T C Beckmann M J Assignment problems and thelocation of economic activitiesEconometrica 1957 255376. doi:10.2307/1907742
11. Lawler E L Thequadratic assignment problemManagementScience 1963 9586599
12. Li Y Pardalos P M Generating quadratic assignmenttest problems with known optimal permutationsComputational Optimization and Applications 1992 1(2)163184
13. Li Y Pardalos P M Ramakrishnan K G et al.Lower bounds for the quadratic assignment problemAnnals of Operations Research 1994 50387411. doi:10.1007/BF02085649
14. Loiola E M Abreu N M M Boaventura-Netto P O et al.An analytical survey for the quadraticassignment problemEuropean Journal of OperationalResearch 2007 176657690
15. Mautor T Roucairol C A New exact algorithm for thesolution of quadratic assignment problemsDis App Math 1994 55281293. doi:10.1016/0166‐218X(94)90014‐0
16. Pardalos P MPitsoulis L SNonlinear Assignment Problems:Algorithms and ApplicationsBostonKluwer Academic Publishers 2000
17. Pardalos P M Ramarkrishnan K G Resende M G C et al.Implementation of a variance reduction-based lowerbound in a branch-and-bound algorithm for the quadratic assignmentproblemSIAM J Optim 1997 7280294. doi:10.1137/S1052623494273393
18. Pardalos P M Rendl F Wolkowicz H The quadratic assignment problem: A survey and recent developmentsIn: Pardalos P MWolkowiczHQuadratic Assignment and Related Problems. DIMACSSeries in Discrete Mathematics and Theoretical Computer Science, Vol16 ProvidenceAMS 1994 142
19. Sahni S Gonzalez T P-complete approximation problemsJournal of the Association of Computing Machinery 1976 23555565
20. Xia Yong Improved Gilmore-Lawler bounds for quadratic assignment problemsChinese Journal of Engineering Mathematics 2007 24(3)401413
21. Xia Yong Yuan Yaxiang A new linearization methodfor quadratic assignment problemsOptimizationMethods and Software 2006 21(5)803816. doi:10.1080/10556780500273077