A Computational Study of Lower Bounds for the Two Dimensional Bin Packing Problem

We survey lower bounds for the variant of the two-dimensional bin packing problem where items cannot be rotated. We prove that the dominance relation claimed by Carlier et al. [Carlier, J., F. Clautiaux and A. Moukrim, New reduction procedures and lower bounds for the two-dimensional bin packing pro...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in discrete mathematics 2010-08, Vol.36, p.891-897
Main Authors: Serairi, Mehdi, Haouari, Mohamed
Format: Article
Language:English
Subjects:
Bin packing problem
Dual feasible function
Lower bounds
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 survey lower bounds for the variant of the two-dimensional bin packing problem where items cannot be rotated. We prove that the dominance relation claimed by Carlier et al. [Carlier, J., F. Clautiaux and A. Moukrim, New reduction procedures and lower bounds for the two-dimensional bin packing problem with fixed orientation, Computers and Operations Research 34 (2007), pp. 2223–2250] between their lower bounds and those of Boschetti and Mingozzi [Boschetti, M. and A. Mingozzi, The two-dimensional finite bin packing problem part I: New lower bounds for the oriented case, 40R 1 (2003), pp. 27–42] is not valid. We analyze the performance of lower bounds from the literature and we provide the results of a computational experiment.
ISSN:1571-0653
1571-0653
DOI:10.1016/j.endm.2010.05.113