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):

Report Date:

1974-08-05

Pagination or Media Count:

34.0

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 tauj the summation from j 1 to n the summation from k 1 to n f sub jk d sub tauj tauk 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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE