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

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.