基于非多余矩阵分离的二次指派问题SDP近似算法与应用

项目名称： 基于非多余矩阵分离的二次指派问题SDP近似算法与应用

项目编号： No.11371324

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 罗和治

作者单位： 浙江工业大学

项目金额： 62万元

中文摘要： 二次指派问题是最具挑战性的离散优化问题之一，一般而言，求解n≥30的问题就变得很困难了。这类问题在设施选址、芯片设计、图像分析与处理和通讯等领域有广泛的应用，是近年来国际最优化的一个研究热点，锥优化特别是半定规划和二阶锥规划的发展为二次指派问题研究提供了新的方法和工具。本项目旨在利用锥优化松弛技术和矩阵分解方法研究二次指派问题及其一类重要的推广问题--非凸二次约束二次规划，特别是基于近年来发展的SDP松弛技术，研究大型二次指派问题的近似算法和实现。我们将研究二次指派问题的基于非多余矩阵分解紧SDP松弛算法，并研究其在分子生物学图像分析与处理中的应用；研究广义二次指派问题的基于矩阵分解SDP松弛；研究非凸二次约束二次规划的基于非多余矩阵分解紧SOCP松弛，并研究它基于精确罚方法的非线性SDP松弛及求其解的二分搜索算法；研究线性约束0-1二次规划的基于矩阵分解紧SDP和SOCP松弛和近似算法。

中文关键词： 二次指派问题；SDP松弛；非多余矩阵分解；非凸二次约束二次规划；0-1二次规划

英文摘要： Quadratic Assignment Problems (QAPs) are known to be among the most challenging discrete optimization problems. In general, solving a QAP with n≥30 becomes very difficult. QAPs have a wide range of applications in many important areas such as facility loc

英文关键词： Quadratic assignment problems；SDP relaxations；Non-redundant matrix decomposition；nonconvex quadratically constrained quadratic prog；0-1 quadratic programming