-

 

 

 




Optimization Online





 

Exactly solving packing problems with fragmentation

Marco Casazza(marco.casazza***at***unimi.it)
Alberto Ceselli(alberto.ceselli***at***unimi.it)

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 arising while including 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.

Keywords: in Packing, Item Fragmentation, Mathematical Programming, Branch-and-Price

Category 1: Combinatorial Optimization (Other )

Category 2: Integer Programming (Other )

Category 3: Applications -- Science and Engineering (Other )

Citation:

Download: [PDF]

Entry Submitted: 04/13/2015
Entry Accepted: 04/13/2015
Entry Last Modified: 04/13/2015

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society