Name
Abstract | ||
|---|---|---|
We study the knapsack problem with conflict graph (KPCG), an extension of the 0-1 knapsack problem, in which a conflict graph describing incompatibilities between items is given. The goal of the KPCG is to select the maximum profit set of compatible items while satisfying the knapsack capacity constraint. We present a new branch-and-bound approach to derive optimal solutions to the KPCG in short computing times. Extensive computational experiments are reported showing that, for instances with graph density of 10% and larger, the proposed method outperforms a state-of-the-art approach and mixed-integer programming formulations tackled through a general purpose solver. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1287/ijoc.2016.0742 | INFORMS JOURNAL ON COMPUTING |
Keywords | Field | DocType |
knapsack problem, maximum weight stable set problem, branch and bound, combinatorial optimization, computational experiments | Discrete mathematics,Mathematical optimization,Branch and bound,Change-making problem,Generalized assignment problem,Continuous knapsack problem,Combinatorial optimization,Cutting stock problem,Knapsack problem,Mathematics,Dense graph | Journal |
Volume | Issue | ISSN |
29 | 3 | 1091-9856 |
Citations | PageRank | References |
3 | 0.42 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Bettinelli | 1 | 19 | 3.43 |
| Valentina Cacchiani | 2 | 292 | 24.01 |
| Enrico Malaguti | 3 | 312 | 21.69 |