Accession Number : AD0783689

Title :   An Eigenvector Structure for a Facilities Location Problem and a Related Algorithm.

Descriptive Note : Technical rept.,

Corporate Author : GEORGE WASHINGTON UNIV WASHINGTON D C DEPT OF STATISTICS

Personal Author(s) : Ireland,C. Terrence

Report Date : 05 AUG 1974

Pagination or Media Count : 34

Abstract : The special case of the quadratic assignment problem, find a permutation tau of (1,2,...,n) which minimizes the summation from j = 1 to n of c sub (j tau(j)) + (the summation from j = 1) to n)) (the summation from k = 1 to n) (f sub jk) d sub (tau(j) tau(k)) is reformulated in terms of an eigenvector structure derived from the matrices D and F. A related suboptimal algorithm is developed and compared with present algorithms using matrices of size 5, 6, 7, 8, 12, 15, 20, and 30. The new algorithm is most efficient in early iterations, suggesting its usefulness in determining a good starting permutation for other algorithms. Evaluation of any suboptimal algorithm for this problem is considered and a regression line developed to fit least cost for the matrices tried. The relationship between this problem and the Traveling Salesman problem is noted. (Author)

Descriptors :   *Facilities, *Position(Location), Eigenvectors, Permutations, Computations, Algorithms, Mathematical models

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE