Lifting for the integer knapsack cover polyhedron

doi:10.1007/s10898-022-01252-x

	Lifting for the integer knapsack cover polyhedron
	Chen, Wei-Kun 2; Chen, Liang 1,3; Dai, Yu-Hong 1,3
刊名	JOURNAL OF GLOBAL OPTIMIZATION
	2022-12-07
页码	45
关键词	Integer programming Cutting plane Sequential lifting MIR inequality Separation algorithm
ISSN号	0925-5001
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.