A theoretical and experimental study of fast lower bounds for the two-dimensional bin packing problem
Author | Serairi M. |
Author | Haouari M. |
Available date | 2019-11-04T05:19:28Z |
Publication Date | 2018 |
Publication Name | RAIRO - Operations Research |
Resource | Scopus |
ISSN | 0399-0559 |
Abstract | We address the two-dimensional bin packing problem with fixed orientation. This problem requires packing a set of small rectangular items into a minimum number of standard two-dimensional bins. It is a notoriously intractable combinatorial optimization problem and has numerous applications in packing and cutting. The contribution of this paper is twofold. First, we propose a comprehensive theoretical analysis of lower bounds and we elucidate dominance relationships. We show that a previously presented dominance result is incorrect. Second, we present the results of an extensive computational study that was carried out, on a large set of 500 benchmark instances, to assess the empirical performance of the lower bounds. We found that the so-called Carlier-Clautiaux-Moukrim lower bounds exhibits an excellent relative performance and yields the tightest value for all of the benchmark instances. |
Sponsor | Acknowledgements. This work was carried out in the framework of the Labex MS2T, which was funded by the French Government, through the program -Investments for the future-managed by the National Agency for Research (Reference ANR-11-IDEX-0004-02). |
Language | en |
Publisher | EDP Sciences |
Subject | Dominance results Dual feasible functions Lower bounds Two-dimensional bin packing |
Type | Article |
Pagination | 391-414 |
Issue Number | 2 |
Volume Number | 52 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |
This item appears in the following Collection(s)
-
Mechanical & Industrial Engineering [1343 items ]