The colored knapsack problem: structural properties and exact algorithms

IRIS Research product catalog (Sapienza University of Rome)

Abstract

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.

Authors 3

1. Fabio Ciccarelli

   Sapienza University of Rome

   Affiliation as printed

   Department of Computer Control and Management Engineering Antonio Ruberti Sapienza University of Rome Rome Italy

2. Alexander Helber Aachen Chair of Operations Research

   RWTH Aachen University

   Affiliation as printed

   Chair of Operations Research RWTH Aachen University Aachen Germany

3. Erik Mühmer Aachen Chair of Operations Research

   RWTH Aachen University

   Affiliation as printed

   Chair of Operations Research RWTH Aachen University Aachen Germany