The colored knapsack problem: structural properties and exact algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917270893101056 |
|---|---|
| author | Ciccarelli, Fabio Helber, Alexander Mühmer, Erik |
| author_facet | Ciccarelli, Fabio Helber, Alexander Mühmer, Erik |
| contents | We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly NP-hard and propose two exact dynamic programming algorithms with time complexities of $\mathcal{O}(bn^4)$ and $\mathcal{O}(b^2n^3)$, respectively. To enhance practical performance, we derive various dominance and fathoming rules for both approaches. From a theoretical perspective, we analyze the linear programming relaxation of the natural CKP formulation, proving that an optimal solution exists with at most two fractional items. We also show that the relaxation can be solved in $\mathcal{O}(n)$ time, matching the complexity of the classical KP. Finally, we establish a comprehensive benchmark of CKP instances, derived from the Colored Bin Packing Problem. Extensive computational experiments demonstrate that the proposed dynamic programming algorithms significantly outperform state-of-the-art MIP solvers on most of these instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12214 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The colored knapsack problem: structural properties and exact algorithms Ciccarelli, Fabio Helber, Alexander Mühmer, Erik Optimization and Control We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly NP-hard and propose two exact dynamic programming algorithms with time complexities of $\mathcal{O}(bn^4)$ and $\mathcal{O}(b^2n^3)$, respectively. To enhance practical performance, we derive various dominance and fathoming rules for both approaches. From a theoretical perspective, we analyze the linear programming relaxation of the natural CKP formulation, proving that an optimal solution exists with at most two fractional items. We also show that the relaxation can be solved in $\mathcal{O}(n)$ time, matching the complexity of the classical KP. Finally, we establish a comprehensive benchmark of CKP instances, derived from the Colored Bin Packing Problem. Extensive computational experiments demonstrate that the proposed dynamic programming algorithms significantly outperform state-of-the-art MIP solvers on most of these instances. |
| title | The colored knapsack problem: structural properties and exact algorithms |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.12214 |