International Journal of Scientific & Technology Research

Home About Us Scope Editorial Board Contact Us

IJSTR >> Volume 4 - Issue 11, November 2015 Edition

International Journal of Scientific & Technology Research  
International Journal of Scientific & Technology Research

Website: http://www.ijstr.org

ISSN 2277-8616

Developing A Combined Strategy For Solving Quadratic Assignment Problem

[Full Text]



Faiz Ahyaningsih, Opim Salim Sitompul



Index Terms: Combination Methods, Combinatorial Optimization Problem, Quadratic Assigment Problem, Random Point Strategy.



Abstract: The quadratic assigment problem (QAP) is one of the most interesting and most challenging combinatorial optimization problems in existence. In this paper we propose a random point strategy to get a starting point, and then we use a combination methods to get ‘optimal’ solution. As a computational experience we’ve solved QAP 30 x 30 adopted from Nugent and backboard wiring problem 42  42, adopted from Skorin-Kapov.



[1] Sahni, S. and T. Gonzales, “ P – Complete Aproximation Problems”, Journal of the Association of Computing Machinery 23, 555-565, 1976. (Journal)

[2] Koopmann, T. C. and M. Beckmann, “Assignment Problem and the Location of Economic Activities, Econometric 25, 53-76, 1957. (Journal)

[3] Steinberg, L., “The Backboard Wiring Problem, A Placement Algorithm”, SIAM Review 3, 37-50, 1961. (Journal)

[4] Dickey, J. W. and J. W. Hopkins, , “ Campus Building Arrangement Using TOPAZ”, Transportation Research 6: 59-68, 1972. (Journal)

[5] A.N.Elshafei, “Hospital Lay-Out as a Quadratic Assignment Problem “, Operational Research Quaterly, 28 : pp. 167-179, 1977. (Journal)

[6] Bisaillon, S., J. F.Cordeau,G. Laporte, F. Pasin, “A Large Neighbourhood Search Heuristic for the Aircraft and Passenger Recovery Problem”, 4OR-Q J Oper Res 9:139–157, 2011. (Journal)

[7] Ribeiro, G. M., Geraldo R. M., Luiz A.N. L.,“a Lagrangean Decomposition for the Maximum Independent Set Problem Applied to Map Labeling”, Oper Res Int J 11:229–243, 2011. (Journal)

[8] Chiarandini, M., Luca D. G., Stefano G., Andrea S., “The Balanced Academic Curriculum Problem Revisited”, J Heuristics 18:119–148, 2012. (Journal)

[9] Burkard, R. E. and K. H. Stratmann, “Numerical Investigation on Quadratic Assignment Problem, Naval Res, 1978. (Journal)

[10] D.T.Connoly, “An Improved Annealing Scheme for the QAP”, European Journal of Operational Research 46 : pp. 93-100, 1990. (Journal)

[11] J.Skorin-Kapov, “Tabu Search Applied to the Quadratic Assignment Problem”, ORSA Journal on Computing 2: 33-45, 1990. (Journal)

[12] E.D.Taillard, “Robust Tabu Search for the Quadratic Assignment Problem “, Parallel Computing 17: pp. 443-455, 1991. (Journal)

[13] R.Battiti and G.Tecchiolli, “The Reactive Tabu Search “, ORSA Journal on Computing 6: 126-140, 1994a. (Journal)

[14] R.Battiti and G.Tecchiolli, “Simulated Annealing and Tabu Search in the Long Run: a comparison on QAP Tasks “, Computers and Mathematics with Applications, 28: 1-8, 1994b. (Journal)

[15] T. James, C. Rego, and F. Glover, “ Multi-Start Tabu Search and Diversification for the Quadratic Assignment Problem”, Technical Report, Virginia Tech, Blacksburg, VA, 2007. (Journal)

[16] L.Sondergeld and S.Vob, “A Star-Shaped Diversification Approach in Tabu Search “, in: “Meta-heuristics: Theory and Applications”, I.H.Osman and J.P.Kelly (eds.), Kluwer academic Publishers: 489-502, 1996. (Book)

[17] Misevicius, A., “A Modified Tabu Search Algorithm for the Quadratic Assignment Problem”, Information Technology and Control, 27, 12–20, 2003. (Journal)

[18] Misevicius, A., “A Tabu Search Algorithm for the Quadratic Assignment Problem”, Computational Optimization and Applications , 30 : 95-111, 2005. (Journal)

[19] Y.Li, P.M.Pardalos, and M.G.C.Resende, “A Randomized Adaptive Search Procedure for The Quadratic Assignment Problem”, in “Quadratic Assignment and Related Problems”, P.Pardalos and H. Wolcowicz (eds.), DIMACS series in Discrete mathematics and Theoritical Computer Science, 16: 237-261, 1994. (Journal)

[20] D.E. Tate and A.E.Smith, “A Genetic Approach to the Quadratic Assignment Problem “, Computers and Operations Research 1: pp. 855-865, 1995. (Journal)

[21] V.-D, Cung, T.Mautor, P.Michelon, and A. Tavares, “A Scatter Search Based Approach for the Quadratic Assignment Problem”, proceedings of the IEEE International Conference on Evolutionary Computation and Evolutionary Programming (ICEC’97),Indianapolis: 165-170, 1997. (Conference proceedings)

[22] L.M.Gambardella, E.D.Taillard and M.Dorigo, “Ant Colonies for the Quadratic Assignment Problem “, Journal of the Operational Society 50: 167-176, 1999. (Journal)

[23] C.Fleurent and J.Ferland, “Genetic Hybrids for the Quadratic Assignment Problem “, DIMACS Series in Math. Theoritical Computer Science 16, pp. 190-206, 1994. (Journal)

[24] Ahuja R.K., J.B.Orlin, and A.Tiwari, “ A Descent Genetic Algorithm for the Quadratic Assignment Problem”, Computers and Operations Research, 27: pp. 917-934, 2000. (Journal)

[25] Z. Drezner, “A New Genetic algorithm for the Quadratic Assignment Problem “, INFORMS Journal on Computing, 2002a. (Journal)

[26] Z. Drezner, “Robust Heuristic Algorithm for the Quadratic assignment Problem “, EJOR, 2002b. (Journal)

[27] Drezner, Z.,”Finding a Cluster of Point and The Grey Pattern Quadratic Assignment Problem”, OR Spectrum 28: 417-436, 2006. (Journal)

[28] Ahyaningsih, F., “ Menyelesaikan Quadratic Assignment Problem Dengan Metode Heuristik Kelayakan”, Math Department University of North Sumatera Indonesia,2006. ( Thesis )

[29] F. Rendl and R. Sotirov, “Bounds for the Quadratic Assignment Problem Using the Bundle Method”, Math program (B), 109:505-524, 2007. (Journal)

[30] C. Papamanthou, K. Paparrizos, N. Samaras, and K. Stergiou, “Worst Case Examples of an Exterior Point Algorithm for the Assignment Problem”, Discret Optimization, 5:605-614, 2008. (Journal)

[31] A.Misevicius and D.Rubliauskas, “Testing of Hybrid Genetic Algorithms for Structured Quadratic Assignment Problems”, Informatica 20, pp. 255-272, 2009. (Journal)

[32] G. G. Zabudskii and A. Yu. Lagzdin, “Polynomial Algorithms for Solving the Quadratic Assignment Problem on Networks”, Computational Mathematics and Mathematical Physics, Vol. 50, No. 11, pp. 1948–1955, 2010. (Journal)

[33] Ahmed ZH, “A Data-guided Lexisearch Algorithm for the Quadratic Assignment Problem”, Indian Journal of Science and Technology, Vol 7(4), (2014): 480-490. (Journal)

[34] C.E.Nugent, T.E.Vollman and J.Ruml, “ an Experimental Comparison of Techniques for the Assignment of Facilities to Locations “, Operations research, vol. 16, pp. 150-173, 1968. (Journal)