KMS Of Academy of mathematics and systems sciences, CAS
| Generalized coefficient strengthening cuts for mixed integer programming | |
Chen, Wei-Kun; Chen, Liang; Yang, Mu-Ming; Dai, Yu-Hong
| |
| 2018 | |
| Source Publication | JOURNAL OF GLOBAL OPTIMIZATION
 |
| ISSN | 0925-5001 |
| Volume | 70Issue:1Pages:289-306 |
| Abstract | 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. |
| Keyword | Mixed integer programming Cutting plane method Separation algorithm Coefficient strengthening |
| DOI | 10.1007/s10898-017-0562-5 |
| Language | 英语 |
| Funding Project | Chinese Natural Science Foundation[11631013] ; Chinese Natural Science Foundation[71331001] ; Chinese Natural Science Foundation[11331012] ; National 973 Program of China[2015CB856002] |
| WOS Research Area | Operations Research & Management Science ; Mathematics |
| WOS Subject | Operations Research & Management Science ; Mathematics, Applied |
| WOS ID | WOS:000419940800015 |
| Publisher | SPRINGER |
| Citation statistics | |
| Document Type | 期刊论文 |
| Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/29308 |
| Collection | 计算数学与科学工程计算研究所 |
| Corresponding Author | Yang, Mu-Ming |
| Affiliation | Chinese 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. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment