Models and Algorithms for the Bin-Packing Problem with Minimum Color Fragmentation

Saharnaz Mehrani (), Carlos Cardonha () and David Bergman ()
Additional contact information
Saharnaz Mehrani: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06269
Carlos Cardonha: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06269
David Bergman: Department of Operations and Information Management, University of Connecticut, Storrs, Connecticut 06269

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 1070-1085

Abstract: In the bin-packing problem with minimum color fragmentation (BPPMCF), we are given a fixed number of bins and a collection of items, each associated with a size and a color, and the goal is to avoid color fragmentation by packing items with the same color within as few bins as possible. This problem emerges in areas as diverse as surgical scheduling and group event seating. We present several optimization models for the BPPMCF, including baseline integer programming formulations, alternative integer programming formulations based on two recursive decomposition strategies that utilize decision diagrams, and a branch-and-price algorithm. Using the results from an extensive computational evaluation on synthetic instances, we train a decision tree model that predicts which algorithm should be chosen to solve a given instance of the problem based on a collection of derived features. Our insights are validated through experiments on the aforementioned applications on real-world data. Summary of Contribution: In this paper, we investigate a colored variant of the bin-packing problem. We present and evaluate several exact mixed-integer programming formulations to solve the problem, including models that explore recursive decomposition strategies based on decision diagrams and a set partitioning model that we solve using branch and price. Our results show that the computational performance of the algorithms depends on features of the input data, such as the average number of items per bin. Our algorithms and featured applications suggest that the problem is of practical relevance and that instances of reasonable size can be solved efficiently.

Keywords: bin packing; integer programming; branch and price; decision diagrams (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1120 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:34:y:2022:i:2:p:1070-1085

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().