TY - JOUR

T1 - Lifting valid inequalities for the precedence constrained knapsack problem

AU - Van De Leensel, R. L.M.J.

AU - Van Hoesel, C. P.M.

AU - Van De Klundert, J. J.

PY - 1999

Y1 - 1999

N2 - This paper considers the precedence constrained knapsack problem. More specifically, we are interested in classes of valid inequalities which are facet-defining for the precedence constrained knapsack polytope. We study the complexity of obtaining these facets using the standard sequential lifting procedure. 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 polynomial time, by using a supermodular function, and for which the values of the lifting coefficients have a combinatorial interpretation. For the remaining lifting coefficients it is shown that this optimization problem is strongly NP-hard. The same lifting procedure can be applied to (l,k)-configurations, although in this case, the same combinatorial interpretation no longer applies. We also consider K-covers, to which the same procedure need not apply in general. We show that 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. Computational experiments indicate that these facets significantly strengthen the LP-relaxation.

AB - This paper considers the precedence constrained knapsack problem. More specifically, we are interested in classes of valid inequalities which are facet-defining for the precedence constrained knapsack polytope. We study the complexity of obtaining these facets using the standard sequential lifting procedure. 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 polynomial time, by using a supermodular function, and for which the values of the lifting coefficients have a combinatorial interpretation. For the remaining lifting coefficients it is shown that this optimization problem is strongly NP-hard. The same lifting procedure can be applied to (l,k)-configurations, although in this case, the same combinatorial interpretation no longer applies. We also consider K-covers, to which the same procedure need not apply in general. We show that 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. Computational experiments indicate that these facets significantly strengthen the LP-relaxation.

UR - http://www.scopus.com/inward/record.url?scp=0345502054&partnerID=8YFLogxK

U2 - 10.1007/s101070050084

DO - 10.1007/s101070050084

M3 - Article

AN - SCOPUS:0345502054

SN - 0025-5610

VL - 86

SP - 161

EP - 185

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -