A new linearization method for quadratic assignment problems

doi:10.1080/10556780500273077

	A new linearization method for quadratic assignment problems
	Xia, Y; Yuan, YX
	2006-10-01
发表期刊	OPTIMIZATION METHODS & SOFTWARE
ISSN	1055-6788
卷号	21 期号:5 页码:805-818
摘要	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.
关键词	quadratic assignment problem linearization mixed integer linear program lower bound cutting plane
DOI	10.1080/10556780500273077
语种	英语
WOS研究方向	Computer Science ; Operations Research & Management Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000238565300009
出版者	TAYLOR & FRANCIS LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/3261
专题	计算数学与科学工程计算研究所
通讯作者	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.