Name
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. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1007/s101070050084 | Math. Program. |
Keywords | Field | DocType |
Mathematics Subject Classification (1991): 90C10 | Mathematical optimization,Continuous knapsack problem,Combinatorial optimization,Polytope,Knapsack problem,Time complexity,Optimization problem,Mathematics,Supermodular function,Constrained optimization | Journal |
Volume | Issue | ISSN |
86 | 1 | 0025-5610 |
Citations | PageRank | References |
14 | 1.27 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. L. M. J. van de Leensel | 1 | 14 | 1.27 |
| C. P. M. Van Hoesel | 2 | 93 | 8.07 |
| J. J. van de Klundert | 3 | 14 | 1.27 |