EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

The colored knapsack problem: structural properties and exact algorithms

Fabio Ciccarelli, Alexander Helber, Erik Mühmer

International Transactions in Operational Research · 17.11.2026

DOI: 10.1111/itor.70302 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Transactions in Operational Research, online erschienen am 17.11.2026. Verfasst von Fabio Ciccarelli und 2 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the colored knapsack problem (ColKP), a generalization of the classical knapsack problem in which items are partitioned into color classes and selected items must be orderable with no two consecutive items sharing a color. We prove weak NP‐hardness and develop two exact dynamic programming algorithms, running in and time, where is the knapsack capacity. We strengthen both algorithms with dominance and fathoming rules. We further show that the linear‐programming relaxation of the ColKP natural formulation admits an optimum with at most two fractional items and can be solved in time. Computational experiments on instances derived from the colored bin packing problem and on synthetic ColKP instances show that the algorithms perform particularly well on the former, while a general‐purpose solver is preferable for synthetic instances with large capacities.

Zitieren

APA

Ciccarelli, F., Helber, A., & Mühmer, E. (2026). The colored knapsack problem: structural properties and exact algorithms. International Transactions in Operational Research. https://doi.org/10.1111/itor.70302

Vancouver

Ciccarelli F, Helber A, Mühmer E. The colored knapsack problem: structural properties and exact algorithms. International Transactions in Operational Research. 2026. doi:10.1111/itor.70302

BibTeX
@article{Ciccarelli2026,
  author = {Ciccarelli, Fabio and Helber, Alexander and Mühmer, Erik},
  title = {The colored knapsack problem: structural properties and exact algorithms},
  journal = {International Transactions in Operational Research},
  year = {2026},
  doi = {10.1111/itor.70302}
}
Kostenlos starten →