CSpace  > 计算数学与科学工程计算研究所
Generalized coefficient strengthening cuts for mixed integer programming
Chen, Wei-Kun; Chen, Liang; Yang, Mu-Ming; Dai, Yu-Hong
AbstractCutting 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.
KeywordMixed integer programming Cutting plane method Separation algorithm Coefficient strengthening
Funding ProjectChinese Natural Science Foundation[11631013] ; Chinese Natural Science Foundation[71331001] ; Chinese Natural Science Foundation[11331012] ; National 973 Program of China[2015CB856002]
WOS Research AreaOperations Research & Management Science ; Mathematics
WOS SubjectOperations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000419940800015
Citation statistics
Document Type期刊论文
Corresponding AuthorYang, Mu-Ming
AffiliationChinese Acad Sci, Acad Math & Syst Sci, Inst Computat Math & Sci Engn Comp, State Key Lab Sci & Engn Comp, Beijing 100190, Peoples R China
Recommended Citation
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.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Chen, Wei-Kun]'s Articles
[Chen, Liang]'s Articles
[Yang, Mu-Ming]'s Articles
Baidu academic
Similar articles in Baidu academic
[Chen, Wei-Kun]'s Articles
[Chen, Liang]'s Articles
[Yang, Mu-Ming]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Chen, Wei-Kun]'s Articles
[Chen, Liang]'s Articles
[Yang, Mu-Ming]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.