Accession Number : ADA564202


Title :   Scalable Effective Approaches for Quadratic Assignment Problems Based on Conic Optimization and Applications


Descriptive Note : Final rept. 1 Jan 2009-30 Nov 2011


Corporate Author : ILLINOIS UNIV AT URBANA-CHAMPAIGN DEPT OF INDUSTRIAL AND ENTERPRISE SYSTEMS ENGINEERING


Personal Author(s) : Peng, Jiming ; Mittelmann, Hans


Full Text : http://www.dtic.mil/get-tr-doc/pdf?AD=ADA564202


Report Date : 09 Feb 2012


Pagination or Media Count : 12


Abstract : This project deals with quadratic assignment problems (QAP) that arise from a broad range of applications such as target tracking, resource allocation and communications. The main endeavor of the project is to explore the structure of the associated data matrix of the underlying problem, combining with various matrix splitting schemes, to derive strong and yet cheap to compute convex optimization relaxations. The new relaxation can be further used to obtain a good approximation to the original problem or help the development of exact algorithms. The efficacy of the proposed approaches has been demonstrated via both theoretical and numerical comparisons with other existing approaches in the literature, and the techniques developed through the project have been successfully applied to large scale QAPs from communications and information processing.


Descriptors :   *ALGORITHMS , *QUADRATIC EQUATIONS , COMMUNICATION AND RADIO SYSTEMS , CONVEX BODIES , DATA BASES , INFORMATION PROCESSING , NUMERICAL ANALYSIS , OPTIMIZATION , PARALLEL PROCESSING , RELAXATION , TARGET DETECTION , TRACKING


Subject Categories : Numerical Mathematics


Distribution Statement : APPROVED FOR PUBLIC RELEASE