Gilmore-Lawler bound of quadratic assignment
problem

doi:10.1007/s11464-008-0010-4

Front. Math. China

2008, Vol. 3

Issue (1) : 109-118 https://doi.org/10.1007/s11464-008-0010-4

Gilmore-Lawler bound of quadratic assignment problem

XIA Yong

Department of Applied Mathematics; Key Laboratory of Mathematics, Informatics and Behavioral Semantics of the Ministry of Education of China, Beihang University;

Download: PDF(124 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Issue Date: 05 March 2008

Cite this article:

XIA Yong. Gilmore-Lawler bound of quadratic assignment problem[J]. Front. Math. China, 2008, 3(1): 109-118.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-008-0010-4
https://academic.hep.com.cn/fmc/EN/Y2008/V3/I1/109

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

Viewed

Full text

Abstract

Cited

Shared

Discussed