The colored knapsack problem: structural properties and exact algorithms

Abstract 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.

Authors

Institutions

Publication Details

Journal
International Transactions in Operational Research
Published
2026-11-17
DOI
https://doi.org/10.1111/itor.70302
Citations
1
Primary Topic
Optimization and Packing Problems
Type
article
Field-Weighted Citation Impact
1.73
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

The colored knapsack problem: structural properties and exact algorithms

Erik Mühmer, Fabio Ciccarelli, Alexander Helber
1 citations
International Transactions in Operational Research
Optimization and Packing Problems
1.73
article

The colored knapsack problem: structural properties and exact algorithms

Erik Mühmer, Fabio Ciccarelli, Alexander Helber
article en
1 citations

Abstract

Abstract 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.

International Transactions in Operational Research
Sapienza University of Rome (IT), RWTH Aachen University (DE)
Openalex Percentile: Top 22%
Optimization and Packing Problems
1.73
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon