Gilmore-Lawler bound of quadratic assignment problem
Tóm tắt
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.
Tài liệu tham khảo
Anstreicher K M. Recent advances in the solution of quadratic assignment Problems. Mathematical Programming, Ser B, 2003, 97: 24–42
Brüngger A, Marzetta A, Clausen J, et al. Solving large-scale QAP problems in parallel with the search library ZRAM. J Parallel and Distributed Com, 1998, 50: 157–169
Burkard R E. Locations with spatial interactions: The quadratic assignment problem. In: Mirchandani P B, Francis R L, eds. Discrete Location Theory. New York: Wiley, 1991, 387–437
Burkard R E, Çela E, Pardalos P M, et al. The quadratic assignment Problem. In: Du Dingzhu, Pardalos P M, eds. Handbook of Combinatorial Optimization, Vol 3. Dordrecht: Kluwer, 1998, 241–337
Burkard R E, Derigs U. Assignment and Matching Problems: Solution Methods with Fortran Programs. Lecture Notes in Economics and Mathematical Systems, Vol 184. Berlin: Springer, 1980
Çela E. The Quadratic Assignment Problem: Theory and Algorithms. Dordrecht: Kluwer Academic Publishers, 1998
Clausen J, Perregaard M. Solving large quadratic assignment problems in parallel. Computational Optimization and Applications, 1997, 8: 111–127
Gilmore P C. Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM Journal on Applied Mathematics, 1962, 10: 305–313
Hardy G G, Littlewood J E, Pólya G. Inequalities. London and New York: Cambridge University Press, 1952
Koopmans T C, Beckmann M J. Assignment problems and the location of economic activities. Econometrica, 1957, 25: 53–76
Lawler E L. The quadratic assignment problem. Management Science, 1963, 9: 586–599
Li Y, Pardalos P M. Generating quadratic assignment test problems with known optimal permutations. Computational Optimization and Applications, 1992, 1(2): 163–184
Li Y, Pardalos P M, Ramakrishnan K G, et al. Lower bounds for the quadratic assignment problem. Annals of Operations Research, 1994, 50: 387–411
Loiola E M, Abreu N M M, Boaventura-Netto P O, et al. An analytical survey for the quadratic assignment problem. European Journal of Operational Research, 2007, 176: 657–690
Mautor T, Roucairol C A. New exact algorithm for the solution of quadratic assignment problems. Dis App Math, 1994, 55: 281–293
Pardalos P M, Pitsoulis L S, eds. Nonlinear Assignment Problems: Algorithms and Applications. Boston: Kluwer Academic Publishers, 2000
Pardalos P M, Ramarkrishnan K G, Resende M G C, et al. 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
Pardalos P M, Rendl F, Wolkowicz H. The quadratic assignment problem: A survey and recent developments. In: Pardalos P M, Wolkowicz H, eds. Quadratic Assignment and Related Problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol 16. Providence: AMS, 1994, 1–42
Sahni S, Gonzalez T. P-complete approximation problems. Journal of the Association of Computing Machinery, 1976, 23: 555–565
Xia Yong. Improved Gilmore-Lawler bounds for quadratic assignment problems. Chinese Journal of Engineering Mathematics, 2007, 24(3): 401–413
Xia Yong, Yuan Yaxiang. A new linearization method for quadratic assignment problems. Optimization Methods and Software, 2006, 21(5): 803–816