Total views : 895

A Data-guided Lexisearch Algorithm for the Quadratic Assignment Problem

Affiliations

  • Department of Computer Science, AlImam Mohammad Ibn Saud Islamic University (IMSIU), P.O. Box No. 5701, Riyadh-11432, Saudi Arabia

Abstract


This paper considers the well-known Quadratic Assignment Problem (QAP) for the study. It is NP-hard combinatorial optimizations that can be defined as follows. There is n facilities and n locations. A distance is specified for each pair of locations, and a flow is specifiedfor each pair of facilities. The objective of problem is to allocate all facilities to different locations such that the sum of the flows multiplied by the corresponding distances is minimized. We develop a data-guided lexisearch algorithm based on an existing reformulation to find exact solution to the problem. For this we first modify alphabet table according to the number of zeros in the rows of the surplus matrix, thus, renaming rows (facilities), and then we apply lexisearch algorithm. It is shown that before applying lexisearch algorithm, this minor preprocessing of the data improves computational time significantly. Finally, we present a comparative study between data-guided lexisearch algorithm and two existing algorithms on some QAPLIB instances of various sizes. The computational study shows the effectiveness of our proposed data-guided lexisearch algorithm.

Keywords

Alphabet Table, Bound, Data-guided Lexisearch, Quadratic Assignment Problem, Surplus Matrix

Full Text:

 |  (PDF views: 385)

References


  • Koopmans TC, Beckmann MJ. Assignment problems and the location of economic activities. Econometrica.1957; 25(1):53–76.
  • Sahni S, Gonzales T. P-complete approximation problems. Journal of the Association for Computing Machinery. 1976; 23:555–65.
  • Steinberg L. The backboard wiring problem: a placement algorithm. SIAM Rev. 1961; 3(1):37–50.
  • Geoffrion AM, Graves GW. Scheduling parallel production lines with changeover costs: practical applications of a quadratic assignment/LP approach. Operations Research. 1976 Jul–Aug; 24(4):595–610.
  • Pollatschek MA, Gershoni N, Radday YT. Optimization of the typewriter keyboard by simulation. Angewandte Informatik. 1976; 17:438–9.
  • Elshafei AN. Hospital layout as a quadratic assignment problem. Operations Research Quarterly. 1977; 28(1):167–79.
  • Krarup J, Pruzan PM. Computer-aided layout design. Math Program Stud. 1978; 9:75–94.
  • Heffley DR. Decomposition of the Koopmans–Beckmann problem. Reg Sci Urban Econ. 1980; 10(4):571–80.
  • Hubert LJ. Assignment methods in combinatorial data analysis. Statistics: Textbooks and Monographs Series. New York: Marcel Dekker, Inc. 1987. Book 73.
  • Bos J. A quadratic assignment problem solved by simulated annealing. Journal of Environmental Management. 1993; 37(2):127–45.
  • Forsberg JH, Delaney RM, Zhao Q, Harakas G, Chandran R. Analyzing lanthanide-included shifts in the NMR spectra of lanthanide (III) complexes derived from 1,4,7,10-tetrakis (N,N-diethylacetamido)-1,4,7,10-tetraazacyclododecane. Inorganic Chemistry. 1994; 34:3705–15.
  • Brusco MJ, Stahl S. Using quadratic assignment methods to generate initial permutations for least-squares unidimensional scaling of symmetric proximity matrices. J Classif. 2000; 17(2):197–223.
  • Duman E, Ilhan O. The quadratic assignment problem in the context of the printed circuit board assembly process. Comput Oper Res. 2007; 34:163–79.
  • Hahn P, Grant T, Hall N. A branch-and-bound algorithm for the quadratic assignment problem based on Hungarian method. Eur J Oper Res. 1998; 108:629–40.
  • Erdoğan G, Tansel, B. A branch-and-cut algorithm for the quadratic assignment problems based on linearizations. Comput Oper Res. 2007; 34(4):1085–106.
  • Das S. Routing and Allied Combinatorial Programming Problems: A Lexicographic Search Approach [Ph.D. Thesis]. Assam, India: Dibrugarh University; 1976.
  • Ahmed ZH. i.exeA lexisearch algorithm for the bottleneck traveling salesman problem. Int J Comput Sci Secur. 2010a; 3(6):569–77.
  • Ahmed ZH. i.exeA data-guided lexisearch algorithm for the asymmetric traveling salesman problem. Mathematical Problems in Engineering. 2011a; 2011(2011). doi:10.1155/2011/750968.
  • Ahmed ZH. i.exeA data-guided lexisearch algorithm for the bottleneck travelling salesman problem. International Journal of Operational Research. 2011b; 12(1):20–33.
  • Ahmed ZH.i.exe An exact algorithm for the clustered travelling salesman problem. OPSEARCH. 2013a Jun; 50(2):215–28.
  • Ahmed ZH. A new reformulation and an exact algorithm for the quadratic assignment problem. Indian Journal of Science and Technology. 2013b; 6(4):4368–77.
  • Nyberg A, Westerlund T. A new exact discrete linear reformulation of the quadratic assignment problem. Eur J Oper Res. 2012; 220:314–19.
  • Burkard RE, Karisch SE, Rendl F. QAPLIB - a quadratic assignment problem library. J Global Optim. 1997; 10(4):391–403.
  • Gilmore PC. Optimal and suboptimal algorithms for the quadratic assignment problem. SIAM J Appl Math; 1962; 10:305–13.
  • Lawler EL. The quadratic assignment problem. Manag Sci. 1963; 19:586–90.
  • Burkard RE, Derigs U. Assignment and matching problems: solutions methods with Fortran programs. Lect Notes Econ Math Syst. 1980; 184.
  • Pardalos P, Crouse J. A parallel algorithm for the quadratic assignment problem. Supercomputing ‘89. Proceedings of the 1989 ACM/IEEE Conference on Supercomputing; 1989 Nov 12–17; Reno, NV, United States. p. 351–60.
  • Pardalos PM, Ramakrishnan KG, Resende MGC, Li Y. Implementation of a variance reduction-based lower bound in a branch-and-bound algorithm for the quadratic assignment problem. SIAM J Optim. 1997; 7(1):280–94.
  • Brixius NW, Anstreicher KM. Solving quadratic assignment problems using convex quadratic programming relaxations. Optim Meth Software. 2001; 16(1–4):49–68.
  • Hahn PM, Hightower WL, Johnson TA, Guignard-Spielberg M, Roucairol C. Tree elaboration strategies in branch and bound algorithms for solving the quadratic assignment problem. Yugoslavian Journal of Operational Research. 2001; 11(1):41–60.
  • Christofides N, Benavent E. An exact algorithm for the quadratic assignment problem. Oper Res. 1989; 37(5):760–68.
  • Urban TL. Solution procedures for the dynamic facility layout problem. Ann Oper Res. 1998. 76:323–42.
  • Adams WP, Johnson TA. Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 1994; 16:43–75.
  • Adams WP, Guignard M, Hahn PM, Hightower WL. A level-2 reformulation–linearization technique bound for the quadratic assignment

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.