Pseudo-Polynomial Formulations for the Bin Packing Problem with Minimum Color Fragmentation

We study the bin packing problem with minimum color fragmentation (BPPMCF), an extension of the well-known bin packing problem (BPP) in which a given set of weighted colored items has to be packed into a set of identical capacitated bins. Differently from the BPP, in this problem, the number of available bins is fixed and the objective is to minimize the total number of times that colors appear in the bins. After reviewing the integer linear programming models proposed in the literature, we show that one of these models, a flow formulation, shares several features with existing BPP flow formulations. We then exploit these ideas to develop three new flow formulations for the BPPMCF and demonstrate their effectiveness on a set of benchmark instances. We also outline theoretical and empirical dominance relations between the studied flow models. Finally, we empirically show how the number of color fragmentations varies when the number of available bins changes.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete.

Funding: This work was supported by the Dutch Ministry of Education and the Air Force Office of Scientific Research [Grant FA8655-25-1-7013].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0972) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.0972). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.