• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2013, Volume: 6, Issue: 4, Pages: 1-10

Original Article

A New Reformulation and an Exact Algorithm for the Quadratic Assignment Problem


In this paper, we consider the quadratic assignment problem (QAP), one of the hardest NP-hard combinatorial optimization problems. We first present a new reformulation of the problem. Then a Lexisearch Algorithm (LSA) is developed for obtaining exact optimal solution to the problem. Finally, a comparative study has been carried out to show the efficiency of the algorithm against an existing algorithm for some medium sized instances from the quadratic assignment problem library, QAPLIB. The comparative study shows the efficiency of the proposed LSA based on the reformulation.
Keywords: Quadratic Assignment Problem, NP-hard, Reformulation, Exact Algorithm, Lexisearch, Alphabet Table, Bound. 


Subscribe now for latest articles and news.