Indian Journal of Science and Technology
Year: 2014, Volume: 7, Issue: 4, Pages: 480-490
Zakir Hussain Ahmed*
Department of Computer Science, AlImam Mohammad Ibn Saud Islamic University (IMSIU), P.O. Box No. 5701, Riyadh-11432, Kingdom of Saudi Arabia;
Corresponding author email: [email protected]
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
Subscribe now for latest articles and news.