Exactly solving packing problems with fragmentation. (November 2016)

• Record Type: Journal Article
• Authors: Casazza, Marco; Ceselli, Alberto
• Is Part Of: Computers & operations research. Volume 75(2016)
• Page Start: 202
• Page End: 213
• Publication Date: 2016-11
• Subjects: Bin packing -- Item fragmentation -- Mathematical programming -- Branch-and-price; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.06.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In packing problems with fragmentation a set of items of known weight is given, together with a set of bins of limited capacity; the task is to find an assignment of items to bins such that the sum of items assigned to the same bin does not exceed its capacity. As a distinctive feature, items can be split at a price, and fractionally assigned to different bins. Arising in diverse application fields, packing with fragmentation has been investigated in the literature from both theoretical, modeling, approximation and exact optimization points of view. We improve the theoretical understanding of the problem and we introduce new models by exploiting only its combinatorial nature. We design new exact solution algorithms and heuristics based on these models. We consider also variants from the literature with different objective functions and the option of handling weight overhead after splitting. We present experimental results on both datasets from the literature and new, more challenging, ones. These show that our algorithms are both flexible and effective, outperforming by orders of magnitude previous approaches from the literature for all the variants considered. By using our algorithms we could also assess the impact of explicitly handling split overhead, in terms of both solutions quality and computing effort. Abstract : Highlights: We consider bin packing problems in which items can be split at a price. We consider bin and fragmentation minimization, size preserving and increasing. We introduce new theoretical results, models and algorithms. We introduce new, more challenging, datasets. Our algorithms outperform previous approaches by orders of magnitude.