Generalized coefficient strengthening cuts for mixed integer programming

doi:10.1007/s10898-017-0562-5

CORC > 数学与系统科学研究院 > 中国科学院数学与系统科学研究院 > 计算数学与科学工程计算研究所

	Generalized coefficient strengthening cuts for mixed integer programming
	Chen, Wei-Kun; Chen, Liang; Yang, Mu-Ming; Dai, Yu-Hong
刊名	JOURNAL OF GLOBAL OPTIMIZATION
	2018
卷号	70 期号:1 页码:289-306
关键词	Mixed integer programming Cutting plane method Separation algorithm Coefficient strengthening
ISSN号	0925-5001
DOI	10.1007/s10898-017-0562-5
英文摘要	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.
资助项目	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
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000419940800015
内容类型	期刊论文
源URL	[http://ir.amss.ac.cn/handle/2S8OKBNM/29307]
专题	计算数学与科学工程计算研究所
通讯作者	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.