A new linearization method for quadratic assignment problems
文献类型：期刊论文
| 作者 | Xia, Y; Yuan, YX
|
| 刊名 | OPTIMIZATION METHODS & SOFTWARE
 |
| 出版日期 | 2006-10-01 |
| 卷号 | 21期号:5页码:805-818 |
| 关键词 | quadratic assignment problem linearization mixed integer linear program lower bound cutting plane |
| ISSN号 | 1055-6788 |
| DOI | 10.1080/10556780500273077 |
| 英文摘要 | The quadratic assignment problem (QAP) is one of the great challenges in combinatorial optimization. Linearization for QAP is to transform the quadratic objective function into a linear one. Numerous QAP linearizations have been proposed, most of which yield mixed integer linear programs. Kauffmann and Broeckxs linearization (KBL) is the current smallest one in terms of the number of variables and constraints. In this article, we give a new linearization, which has the same size as KBL. Our linearization is more efficient in terms of the tightness of the continuous relaxation. Furthermore, the continuous relaxation of our linearization leads to an improvement to the Gilmore-Lawler bound. We also give a corresponding cutting plane heuristic method for QAP and demonstrate its superiority by numerical results. |
| WOS研究方向 | Computer Science ; Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000238565300009 |
| 出版者 | TAYLOR & FRANCIS LTD |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/3260]  |
| 专题 | 计算数学与科学工程计算研究所 |
| 通讯作者 | Xia, Y |
| 作者单位 | Chinese Acad Sci, Acad math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci Engn Comp, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Xia, Y,Yuan, YX. A new linearization method for quadratic assignment problems[J]. OPTIMIZATION METHODS & SOFTWARE,2006,21(5):805-818. |
| APA | Xia, Y,&Yuan, YX.(2006).A new linearization method for quadratic assignment problems.OPTIMIZATION METHODS & SOFTWARE,21(5),805-818. |
| MLA | Xia, Y,et al."A new linearization method for quadratic assignment problems".OPTIMIZATION METHODS & SOFTWARE 21.5(2006):805-818. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。