Relaxations and exact solution of the variable sized bin packing problem

We address a generalization of the classical one-dimensional bin packing problem with unequal bin sizes and costs. We investigate lower bounds for this problem as well as exact algorithms. The main contribution of this paper is to show that embedding a tight network flow-based lower bound, dominance...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2011-03, Vol.48 (2), p.345-368
Main Authors: Haouari, Mohamed, Serairi, Mehdi
Format: Article
Language:English
Subjects:
Algorithms
Branch & bound algorithms
Computation
Convex and Discrete Geometry
Costs
Dominance
Exact solutions
Graphs
Integer programming
Leasing
Lower bounds
Management Science
Mathematical analysis
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Packing problem
Statistics
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We address a generalization of the classical one-dimensional bin packing problem with unequal bin sizes and costs. We investigate lower bounds for this problem as well as exact algorithms. The main contribution of this paper is to show that embedding a tight network flow-based lower bound, dominance rules, as well as an effective knapsack-based heuristic in a branch-and-bound algorithm yields very good performance. In addition, we show that the particular case with all weight items larger than a third the largest bin capacity can be restated and solved in polynomial-time as a maximum-weight matching problem in a nonbipartite graph. We report the results of extensive computational experiments that provide evidence that large randomly generated instances are optimally solved within moderate CPU times.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-009-9276-z