Template-type: ReDif-Paper 1.0
Author-Name: Leensel,R.L.M.J.,van de
Author-Name: Hoesel,C.P.M.,van de
Author-Name: Klundert,J.J.,van de
Author-workplace-name: METEOR
Title: Lifting valid inequalities for the precedence constrained knapsack problem
Abstract: 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 (1,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. 
Keywords: mathematical applications; 
Series: Research Memoranda
Creation-Date: 1997
Number: 012
File-URL: http://edocs.ub.unimaas.nl/loader/file.asp?id=459
File-Format: application/pdf
File-Size: 325642
Handle: RePEc:unm:umamet:1997012