Generalized coefficient strengthening cuts for mixed integer programming

doi:10.1007/s10898-017-0562-5

	Generalized coefficient strengthening cuts for mixed integer programming
	Chen, Wei-Kun; Chen, Liang; Yang, Mu-Ming; Dai, Yu-Hong
	2018
发表期刊	JOURNAL OF GLOBAL OPTIMIZATION
ISSN	0925-5001
卷号	70 期号:1 页码:289-306
摘要	Cutting plane methods are an important component in solving the mixed integer programming (MIP). By carefully studying the coefficient strengthening method, which is originally a presolving method, we are able to generalize this method to generate a family of valid inequalities called generalized coefficient strengthening (GCS) inequalities. The invariant property of the GCS inequalities is established under bound substitutions. Furthermore, we develop a separation algorithm for finding the violated GCS inequalities for a general mixed integer set. The separation algorithm is proved to have the polynomial time complexity. Extensive numerical experiments are made on standard MIP test sets, which demonstrate the usefulness of the resulting GCS separator.
关键词	Mixed integer programming Cutting plane method Separation algorithm Coefficient strengthening
DOI	10.1007/s10898-017-0562-5
语种	英语
资助项目	Chinese Natural Science Foundation[11631013] ; Chinese Natural Science Foundation[71331001] ; Chinese Natural Science Foundation[11331012] ; National 973 Program of China[2015CB856002]
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000419940800015
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/29308
专题	计算数学与科学工程计算研究所
通讯作者	Yang, Mu-Ming
作者单位	Chinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Chen, Wei-Kun,Chen, Liang,Yang, Mu-Ming,et al. Generalized coefficient strengthening cuts for mixed integer programming[J]. JOURNAL OF GLOBAL OPTIMIZATION,2018,70(1):289-306.
APA	Chen, Wei-Kun,Chen, Liang,Yang, Mu-Ming,&Dai, Yu-Hong.(2018).Generalized coefficient strengthening cuts for mixed integer programming.JOURNAL OF GLOBAL OPTIMIZATION,70(1),289-306.
MLA	Chen, Wei-Kun,et al."Generalized coefficient strengthening cuts for mixed integer programming".JOURNAL OF GLOBAL OPTIMIZATION 70.1(2018):289-306.