Lifting for the integer knapsack cover polyhedron
文献类型：期刊论文
| 作者 | Chen, Wei-Kun2; Chen, Liang1,3; Dai, Yu-Hong1,3 |
| 刊名 | JOURNAL OF GLOBAL OPTIMIZATION
 |
| 出版日期 | 2022-12-07 |
| 页码 | 45 |
| ISSN号 | 0925-5001 |
| 关键词 | Integer programming Cutting plane Sequential lifting MIR inequality Separation algorithm |
| DOI | 10.1007/s10898-022-01252-x |
| 英文摘要 | We consider the integer knapsack cover polyhedron which is the convex hull of the set consisting of n -dimensional nonnegative integer vectors that satisfy one linear constraint. We study the sequentially lifted (SL) inequality, derived by the sequential lifting from a seed inequality containing a single variable, and provide bounds on the lifting coefficients, which is useful in solving the separation problem of the SL inequalities. The proposed SL inequality is shown to dominate the well-known mixed integer rounding (MIR) inequality under certain conditions. We show that the problem of computing the coefficients for an SL inequality is NP-hard but can be solved by a pseudo-polynomial time algorithm. As a by-product of analysis, we provide new conditions to guarantee the MIR inequality to be facet-defining for the considered polyhedron and prove that in general, the problem of deciding whether an MIR inequality defines a facet is NP-complete. Finally, we perform numerical experiments to evaluate the performance and impact of using the proposed SL inequalities as cutting planes in solving mixed integer linear programming problems. Numerical results demonstrate that the proposed SL cuts are much more effective than the MIR cuts in terms of strengthening the problem formulation and improving the solution efficiency. Moreover, when applied to solve random and real application problems, the proposed SL cuts demonstrate the benefit in the solution time. |
| 资助项目 | Chinese NSF[12101048] ; Chinese NSF[12021001] ; Chinese NSF[11991021] ; Chinese NSF[11991020] ; Chinese NSF[11971372] ; Beijing Institute of Technology Research Fund Program for Young Scholars ; National Key R&D Program of China[2021YFA1000300] ; National Key R&D Program of China[2021YFA1000301] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDA27000000] |
| WOS研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| 出版者 | SPRINGER |
| WOS记录号 | WOS:000894742000001 |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/60555]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Dai, Yu-Hong |
| 作者单位 | 1.Univ Chinese Acad Sci, Sch Math Sci, Beijing, Peoples R China 2.Beijing Inst Technol, Sch Math & Stat, Beijing Key Lab MCAACI, Beijing, Peoples R China 3.Chinese Acad Sci, Acad Math & Syst Sci, LSEC, ICMSEC, Beijing, Peoples R China |
| 推荐引用方式 GB/T 7714 | Chen, Wei-Kun,Chen, Liang,Dai, Yu-Hong. Lifting for the integer knapsack cover polyhedron[J]. JOURNAL OF GLOBAL OPTIMIZATION,2022:45. |
| APA | Chen, Wei-Kun,Chen, Liang,&Dai, Yu-Hong.(2022).Lifting for the integer knapsack cover polyhedron.JOURNAL OF GLOBAL OPTIMIZATION,45. |
| MLA | Chen, Wei-Kun,et al."Lifting for the integer knapsack cover polyhedron".JOURNAL OF GLOBAL OPTIMIZATION (2022):45. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。