A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

0.00 Avg rating0 Votes
Article ID: iaor20106138
Volume: 179
Issue: 1
Start Page Number: 221
End Page Number: 241
Publication Date: Sep 2010
Journal: Annals of Operations Research
Authors: , ,
Keywords: packing, branch and price
Abstract:

In this paper we consider a variation of the bin packing problem in which bins of different types have different costs and capacities. Furthermore, each bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size bin packing problem.

Reviews

Required fields are marked *. Your email address will not be published.