| Article ID: | iaor20001101 |
| Country: | South Korea |
| Volume: | 23 |
| Issue: | 4 |
| Start Page Number: | 1 |
| End Page Number: | 10 |
| Publication Date: | Dec 1998 |
| Journal: | Journal of the Korean ORMS Society |
| Authors: | Lee Kyung-Sik, Park Sung-Soo, Park Kyung-Chul |
| Keywords: | knapsack problem |
We consider the precedence-constrained knapsack problem, which is a knapsack problem with precedence constraints imposed on the set of variables. Especially, we focus on the case where the precedence constraints can be represented as a bipartite graph, which occurs most frequently in applications. Based on the previous studies for the general case, we specialize the polyhedral results on the related polytope and derive stronger results on the facet-defining properties of the inequalities.