Lifting valid inequalities for the precedence constrained knapsack problem

This paper considers the precedence constrained knapsack problem. More spec ifically, we are interested in classes of valid inequalities which are face t-defining for the precedence constrained knapsack polytope. We study the c omplexity of obtaining these facets using the standard sequential lifting p rocedure. Applying this procedure requires solving a combinatorial problem. For valid inequalities arising from minimal induced covers, we identify a class of lifting coefficients for which this problem can be solved in polyn omial time, by using a supermodular function, and for which the values of t he lifting coefficients have a combinatorial interpretation. For the remain ing lifting coefficients it is shown that this optimization problem is stro ngly NP-hard. The same lifting procedure can be applied to (l,k)-configurat ions. although in this case, the same combinatorial interpretation no longe r applies. We also consider K-covers, to which the same procedure need not apply in general. We show mar facets of the polytope can still be generated using a similar lifting technique. For tree knapsack problems, we observe that all lifting coefficients can be obtained in polynomial time. Computati onal experiments indicate that these facets significantly strengthen the LP -relaxation.