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 polynomia...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.展开更多
基金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.
