Indian Journal of Science and Technology

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