Question

Discuss use of quadratic assignment model adding new machines to existing facility.

Answer 1

The quadratic assignment problem (QAP) in location Theory is the problem oflocating facilities the cost of placing a facility depends on the distances from otherfacilities and also the interaction with other facilities. QAP was introduced byKoopmans and Beckman in 1957 who were trying to model a facilities locationproblem.It is possible to formulate some classic problems of combinatorial optimization,such as the traveling salesman, maximum clique and graph partitioning prob-lems as a QAP. The QAP belongs to the class of NP-complete problems andis considered one of the most difficult combinatorial optimization problems. Ex-act solution strategies for the QAP have been unsuccessful for large problem(approximately N25).In Fig. 6.1 the QAP search trends and tendencies in about 50 years is shown(Hahn et al. 2007). Figure 6.1 shows the distribution of QAP publications with re-spect to the categories: applications, theory and algorithms.Figure 6.2 distributes the number of articles by 5-year periods since 1957, foreach period, the work is also classified according to the same categories of Fig. 6.1.Figure 6.2 shows that an explosion of interest in theory and algorithm developmentoccurred in the period from 1992 to the present.Figure 6.3 shows a steady increase in interest in the QAP in recent years.Figure 6.4, which covers the recent years, shows that the interest in algorithmscontinues to be very strong, with a cyclical trend in theoretical developments. Ap-plications continue to be of interest, but to a lesser extent. It is noteworthy that thereis recently a growing interest in applications to communication link design and tothe optimization of communications networks.As a first example for introducing the problem we describe the problem of as-signing facilities to locations in an office. Let have four facilities that each facility isdesignated to exactly one location and vice-versa. Our problem is to find a minimumcost allocation of facilities into locations taking the costs as the sum of all possi-ble distance-flow products