Solving quadratic assignment problems with rectangular distances and integer programming
✍ Scribed by Robert F. Love; Jsun Y. Wong
- Publisher
- John Wiley and Sons
- Year
- 1976
- Tongue
- English
- Weight
- 304 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
The problem considered involves the assignment of n facilities to n specified locations. Each facility has a given nonnegative flow from each of the other facilities. The objective is to minimize the sum of transportation costs.
Assume these n locations are given as points on a two‐dimensional plane and transportation costs are proportional to weighted rectangular distances. Then the problem is formulated as a binary mixed integer program. The number of integer variables (all binary) involved equals the number of facilities squared. Without increasing the number of integer variables, the formulation is extended to include “site costs” Computational results of the formulation are presented.