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

摘要

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.