Lifting for the integer knapsack cover polyhedron

doi:10.1007/s10898-022-01252-x

CSpace

	Lifting for the integer knapsack cover polyhedron
	Chen, Wei-Kun 1; Chen, Liang 2,3; Dai, Yu-Hong 2,3
	2022-12-07
发表期刊	JOURNAL OF GLOBAL OPTIMIZATION
ISSN	0925-5001
页码	45
摘要	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.
关键词	Integer programming Cutting plane Sequential lifting MIR inequality Separation algorithm
DOI	10.1007/s10898-022-01252-x
收录类别	SCI
语种	英语
资助项目	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
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000894742000001
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/60556
专题	中国科学院数学与系统科学研究院
通讯作者	Dai, Yu-Hong
作者单位	1.Beijing Inst Technol, Sch Math & Stat, Beijing Key Lab MCAACI, Beijing, Peoples R China 2.Chinese Acad Sci, Acad Math & Syst Sci, LSEC, ICMSEC, Beijing, Peoples R China 3.Univ Chinese Acad Sci, Sch Math Sci, 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.