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

Zakir Hussain Ahmed

doi:10.17485/ijst/2013/v6i4.12

Article

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

VIEWS 783
PDF 696

Abstract
Full-Text HTML
Full-Text PDF
How to Cite

Indian Journal of Science and Technology

DOI: 10.17485/ijst/2013/v6i4.12

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

Original Article

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

Zakir Hussain Ahmed

Department of Computer Science, Al Imam Mohammad Ibn Saud Islamic University (IMSIU), P.O. E-mail: [email protected]

This work is licensed under a Creative Commons Attribution 4.0 International License.

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.
Keywords: Quadratic Assignment Problem, NP-hard, Reformulation, Exact Algorithm, Lexisearch, Alphabet Table, Bound.