The Quadratic Assignment Problem: A Note

Results of the Koopmans-Beckmann (K-B) analysis of the quadratic assignment problem [3] have perplexed many location theorists. K-B hold that indivisibilities of plant, in the presence of minimal interaction between spatially separated plants (namely, the shipment of intermediate goods at positive transportation rates), preclude the existence of a system of rents which will sustain an integral assignment, optimal or otherwise [3, p. 69]. Earlier in their paper K-B show that a sustaining price system does exist when the transportation of intermediate products is excluded; however, it is the presence of such interaction that leads to the more interesting quadratic assignment problem and the pessimistic conclusion reported above. The authors first present the quadratic assignment problem in a "permutation search" format, and then construct an equivalent linear programming problem which allows fractional assignments to be optimal without forfeiting any integral (one whole plant to each location) solutions that might exist