The quadratic assignment problem (QAP) is a well-known problem and this is a problem whereby a set of facilities are allocated to a set of locations in such a way that the cost is a function of the distance and flow between the facilities. In this problem the costs are associated with a facility being placed at a certain location. The objective is to minimize the assignment of each facility to a location as given Munapo (2012) and Koopmans & Beckmann (1957). There are three main categories of methods for solving the quadratic assignment problem. These categories are heuristics, bounding techniques and exact algorithms.
These are algorithms that quickly give near optimal solutions to the quadratic assignment problem that are given in Drezner (20008) and Yang et al. (2008). There are five main classes of heuristics for the quadratic assignment problem and these are:
Construction methods
Limited enumeration methods
Improvement methods
Simulated annealing techniques
Genetic algorithms
For a formulated quadratic assignment problem a lower bound can be calculated. There are several types of bounds that can be calculated for a quadratic assignment problem as given in Adams & Johnson (1994) and Ramakrishnan (2002). These are:
Gilmore-Lawler bounds
Eigenvalue related bounds
Bounds based on reformulations
Lower bounds are important in two main ways. Besides being used to approximate optimal solutions they can be used within the context of heuristics or exact methods.
There are for main classes of methods for solving the quadratic assignment problem exactly as given in Cela (1998) and Nagarajan and Sviridenko (2009). These are:
Dynamic programming
Cutting plane techniques
Branch and bound procedures
Hybrids of the last two
Research on these four methods has shown that the hybrids are most successful for solving instances of the quadratic assignment problem.