A Decomposition Procedure for the Quadratic Assignment Problem,

reportActive / Technical Report | Accession Number: AD0751215 | Need Help?

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

Author(s):
Heider, Charles H.
Author Organization(s):
CENTER FOR NAVAL ANALYSES ARLINGTON VA
Pagination:
0030

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
CNA-Professional Paper-100
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
(*COMBINATORIAL ANALYSIS, PROBLEM SOLVING), (*CIRCUIT INTERCONNECTIONS, MATHEMATICAL MODELS), MATRICES(MATHEMATICS), MAPPING(TRANSFORMATIONS), ALGORITHMS, SEARCH THEORY, GRAPHICS
Field(s)/Group(s):
Electrical and Electronic Equipment, Operations Research
Keyword(s):
*NETWORK SYNTHESIS, *QUADRATIC ASSIGNMENT PROBLEM, GRAPHS, DECOMPOSITION METHOD
Report Date:
1972 Nov 01