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

作　　者：Wei-Kun Chen Yu-Hong Dai 

机构地区：[1]School of Mathematics and Statistics,Beijing Institute of Technology,Beijing,100081,China [2]LSEC,ICMSEC,Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing,100190,China [3]School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing,100049,China

出　　处：《Science China Mathematics》2021年第1期211-220,共10页中国科学：数学（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.11631013 and 11331012);the National Basic Research Program of China(Grant No.2015CB856002);the Major Project to Promote Development of Big Data from National Development and Reform Commission(Grant No.2016-999999-65-01-000696-01)。

摘　　要：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 et al.(1999)).We show that this problem is N P-hard,thus giving a negative answer to the question.

关 键 词：integer programming sequentially lifted cover inequality COMPLEXITY lifting problem 

分 类 号：O221.4[理学—运筹学与控制论]