中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 数学与系统科学研究院
  3. 中国科学院数学与系统科学研究院
  4. 应用数学研究所
A proximal DC approach for quadratic assignment problem

文献类型：期刊论文

作者Jiang, Zhuoxuan1; Zhao, Xinyuan1; Ding, Chao2
刊名COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
出版日期2021-01-02
页码27
关键词Quadratic assignment problem Doubly nonnegative programming Augmented Lagrangian method Rank constraint
ISSN号0926-6003
DOI10.1007/s10589-020-00252-5
英文摘要In this paper, we show that the quadratic assignment problem (QAP) can be reformulated to an equivalent rank constrained doubly nonnegative (DNN) problem. Under the framework of the difference of convex functions (DC) approach, a semi-proximal DC algorithm is proposed for solving the relaxation of the rank constrained DNN problem whose subproblems can be solved by the semi-proximal augmented Lagrangian method. We show that the generated sequence converges to a stationary point of the corresponding DC problem, which is feasible to the rank constrained DNN problem under some suitable assumptions. Moreover, numerical experiments demonstrate that for most QAP instances, the proposed approach can find the global optimal solutions efficiently, and for others, the proposed algorithm is able to provide good feasible solutions in a reasonable time.
资助项目National Natural Science Foundation of China[11671387] ; National Natural Science Foundation of China[11531014] ; National Natural Science Foundation of China[11688101] ; General Program of Science and Technology of Beijing Municipal Education Commission[KM201810005004] ; Beijing Natural Science Foundation[Z190002]
WOS研究方向Operations Research & Management Science ; Mathematics
语种英语
WOS记录号WOS:000604160400004
出版者SPRINGER
源URL[http://ir.amss.ac.cn/handle/2S8OKBNM/57946]  
专题应用数学研究所
通讯作者Ding, Chao
作者单位1.Beijing Univ Technol, Coll Appl Sci, Beijing, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Jiang, Zhuoxuan,Zhao, Xinyuan,Ding, Chao. A proximal DC approach for quadratic assignment problem[J]. COMPUTATIONAL OPTIMIZATION AND APPLICATIONS,2021:27.
APA Jiang, Zhuoxuan,Zhao, Xinyuan,&Ding, Chao.(2021).A proximal DC approach for quadratic assignment problem.COMPUTATIONAL OPTIMIZATION AND APPLICATIONS,27.
MLA Jiang, Zhuoxuan,et al."A proximal DC approach for quadratic assignment problem".COMPUTATIONAL OPTIMIZATION AND APPLICATIONS (2021):27.

入库方式： OAI收割

来源：数学与系统科学研究院

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。