On the complexity of sequentially lifting cover inequalities for the knapsack polytope

2018/11/25 by Wei-Kun Chen, Yu-Hong Dai, Chen, Wei-Kun +1
Mathematics · #90C11 #90C27 #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:90C11 #msc:90C27

paper · pdf · doi:10.48550/arxiv.1811.10010

13 pages

arxiv created 2019/03/09 · arxiv updated 2019/03/12

Abstract

The well-known sequentially lifted cover inequality is widely employed in solving mixed integer programs. However, it is still an open question whether a sequentially lifted cover inequality can be computed in polynomial time for a given minimal cover (Gu, Nemhauser, and Savelsbergh, INFORMS J. Comput., 26: 117--123, 1999). We show that this problem is NP-hard, thus giving a negative answer to the question.

Related

• Computational Aspects of Lifted Cover Inequalities for Knapsacks with Few Different Weights
• On the Complexity of Separating Cutting Planes for the Knapsack Polytope
• Understanding Set Cover: Sub-exponential Time Approximations and Lift-and-Project Methods
• On bounded pitch inequalities for the min-knapsack polytope
• Simpler derivation of bounded pitch inequalities for set covering, and minimum knapsack sets