A New Reformulation and an Exact Algorithm for the Quadratic Assignment Problem
|
| Title | A New Reformulation and an Exact Algorithm for the Quadratic Assignment Problem |
| Authors | |
| Abstract | 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. |
| Publisher | Indian Society for Education and Environment (ISEE) |
| Date | 2013-04-01 |
| Source | Indian Journal of Science and Technology Volume 6, Issue 4, April 2013 |