Open AccessPositions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem
Author(s) -
Néstor M. Cid-García,
Yasmin Rios Solis
Publication year - 2020
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0229358
Subject(s) - bin packing problem , bin , set (abstract data type) , combinatorics , mathematics , point (geometry) , rotation (mathematics) , combinatorial optimization , computer science , mathematical optimization , algorithm , geometry , programming language
We present a two-stage methodology called Positions and Covering (P&C) to solve the two-dimensional bin packing problem (2D-BPP). The objective of this classical combinatorial NP-hard problem is to pack a set of items (small rectangles) in the minimum number of bins (larger rectangles). The first stage is the key-point of the Positions and Covering , where for each item, it is generated in a pseudo-polynomial way a set of valid positions that indicate the possible ways of packing the item into the bin. In the second stage, a new set-covering formulation, strengthen with three sets of valid inequalities, is used to select the optimal non-overlapping configuration of items for each bin. Experimental results for the P&C method are presented and compared with some of the best algorithms in the literature for small and medium size instances. Furthermore, we are considering both cases of the 2D-BPP, with and without rotations of the items by 90°. To the best of our knowledge, this is one of the first exact approaches to obtain optimal solutions for the rotation case.