Lifting valid inequalities for the precedence constrained knapsack problem |
| |
Authors: | RLMJ van de Leensel CPM van Hoesel JJ van de Klundert |
| |
Institution: | (1) Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands, e-mail: r.vandeleensel@ke.unimaas.nl, NL;(2) Department of Quantitative Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands, NL |
| |
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.
Received July 10, 1997 / Revised version received January 9, 1999? Published online May 12, 1999 |
| |
Keywords: | Mathematics Subject Classification (1991): 90C10 |
本文献已被 SpringerLink 等数据库收录! |
|