Benchmark instances and experimental results for the Colored Knapsack Problem (ColKP)

This record contains the complete benchmark of instances for the Colored Knapsack Problem (ColKP) and the raw experimental results of the paper The colored knapsack problem: structural properties and exact algorithms by Fabio Ciccarelli, Alexander Helber, and Erik Mühmer. In the ColKP, $n$ items with a profit, a weight and one of $m$ colors are given together with a knapsack capacity $b$. The task is to select a maximum-profit subset of items that respects the capacity and can be ordered such that no two consecutive items share a color — which is possible exactly if no color contributes more items than all other colors together, plus one. The ColKP arises as the pricing problem of the Colored Bin Packing Problem (CBPP) and, to the best of our knowledge, had not been studied before and no benchmark existed for it. Contents instances.zip — holding ColKP instances, in two families: CBPP-derived (CBPP/, JSON, gzip-compressed): every pricing subproblem arising in the root node of a column-generation run for a CBPP instance. All instances of one run share items, weights, colors and capacity and differ only in the profits, which are the (scaled) dual values of the master problem. Two families of CBPP instances of Borges, Schouery and Miyazawa (2024) were converted: files with uniformly distributed colors (new_uniform/) and files with Zipf-distributed colors (random_zipf/). Synthetic (ColKP/, CSV, gzip-compressed): instances generated directly for the ColKP with an adaptation of the classical knapsack generator of Pisinger (1999). results.zip — JSON files with one entry per run and algorithm, for the two exact dynamic programs $\text{DP}_1$ and $\text{DP}_2$ of the paper and for the natural ILP formulation solved with CPLEX 22.1.0 and SCIP 10.0.0. Each entry gives the objective value, the running time, optimality information and, for the MIP solvers, the selected items. All runs were single-threaded. Trivial instances An instance whose optimal knapsack solution already satisfies the color constraints is called trivial. Both families contain such instances. They are excluded from the results reported in the paper. In the synthetic family they are marked by an asterisk before the instance name, while in the CBPP-derived family they are not marked but are flagged by the solvers in the result files. Documentation Each archive contains a top-level README.md describing its layout and file formats. Software The solvers, the instance generator, the CBPP-to-ColKP converter and the evaluation scripts are available at https://github.com/FabioCiccarelli/ColKP under the Apache License 2.0.