Solving the quadratic assignment problem by neural networks

Abstract

The Quadratic Assignment Problem (QAP) was introduced by Koopmans and Beckmann in 1957 as a mathematical model for the location of a set of indivisible economical activities. This problem consists of allocating a set of facilities to a set of locations, taking into account the costs of the distance and flow between facilities, and the cost of the facility’s installation in a certain location. Therefore, the problem is to assign all the facilities to the locations with the objective of minimizing the total cost. The QAP is NP-hard and one of the fundamental combinatorial optimization problems in the area of facility location. This problem has been solved by many different techniques; but no exact algorithm is known for solving large-sized instances of the QAP in reasonable computational time. In this work, neural networks are proposed for solving large-sized instances of the QAP. Preliminary results show that neural networks are capable to provide good solutions in a low computational time.