The Quadratic Assignment Problem - Location Science - page 331

1. Office assignment. There are n planned offices, and n employees or special
equipment to be assigned to them. There are several possible interpretations for
the interaction weights c ij (Drezner 1975 , 1980 ).
(a) The interaction between any two employees (c ij ) and the physical distance
between any two offices (d ij ) are known. The problem is to assign
employees to offices such that those who interact extensively are as close
as possible to one another. The objective is to find the best assignment of
employees to offices so that the sum of the products of the interactions and
the distances is minimized.
(b) The weight c ij is the probability that a customer of this complex needs to
visit both offices i and j in the same visit to complete the service. The
objective in this case is to minimize the total distance an average customer
needs to walk between offices.
(c) In a hospital setting (e.g., Elshafei 1977 and Hahn and Krarup 2001 )
the offices represent different types of specific purpose rooms and the
interaction is the probability that a patient needs the service of two different
rooms.
2. Planning a complex of buildings. For example, Dickey and Hopkins ( 1972 )
explore campus building arrangement; Drezner ( 1980 ) explores the building
arrangement of a military base. Most pairs of buildings have a positive
interaction. Some pairs of buildings may have zero interaction whereas others
may have a negative interaction (such as in planning a military base, top secret
intelligence offices should be as far as possible from the cafeteria or other
frequently visited offices).
3. The wiring problem of an electronic board or the construction of a computer
chip was suggested by Steinberg ( 1961 ). The total wiring distance between
components that send signals to one another has to be minimized.
4. Planning a keyboard of 26 letters was suggested by Burkard and Offermann
( 1977 ). The interaction c ij is the probability of typing letter i following or
preceding letter j. The distances between the letter-keys on the keyboard are
to be considered. Different languages may suggest different key configurations
even for the same letters.
5. The problem of finding the tightest cluster was suggested by Drezner ( 2006 ).
Consider n objects (such as points in the plane or nodes of a network) with
a given distance between every pair of points. We wish to find a cluster of m
points which minimizes the total distance between all pairs of points in the
cluster. This cluster can be interpreted as the “tightest” cluster of m points. We
define the interaction matrix f c ij g as c ij D 1 for i;j m and c ij D 0 otherwise.
Every permutation of the points defines the selected group as the first m points
of the permutation and the value of the objective function is the sum of all the
distances among the selected group members. For this problem there are mŠ
equivalent optimal permutations.