Accession Number : AD0751215

Title :   A Decomposition Procedure for the Quadratic Assignment Problem,

Corporate Author : CENTER FOR NAVAL ANALYSES ARLINGTON VA

Personal Author(s) : Heider,Charles H.

Report Date : NOV 1972

Pagination or Media Count : 30

Abstract : The Quadratic Assignment Problem is one of many combinatorial optimization problems encountered in operations research where the relationship between the computational running time of the available algorithm and problem size is an increasing polynomial. The paper presents a decomposition procedure for reducing the running time of large QAPs. The procedure incorporates the N-step, 2-variable search algorithm. Running time reductions as well as improved solution values are demonstrated for the Steinberg test problem. (Author)

Descriptors :   (*COMBINATORIAL ANALYSIS, PROBLEM SOLVING), (*CIRCUIT INTERCONNECTIONS, MATHEMATICAL MODELS), MATRICES(MATHEMATICS), MAPPING(TRANSFORMATIONS), ALGORITHMS, SEARCH THEORY, GRAPHICS

Subject Categories : Electrical and Electronic Equipment
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE