It is known that facets and valid inequalities for the knapsack polytope P can be obtained by lifting a simple inequality derived from each minimal cover. The paper studies the computational complexity of such lifting. In particular, it shows that the task of computing a lifted facet can be accomplished in O(ns) where s•n is the cardinality of the minimal cover. Also, for a lifted inequality with integer coefficients, the paper shows that the dual tasks of recognizing whether the inequality is valid for P or is a facet of P can be done within the same time bound.
