
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