Positions and covering: A two-stage methodology to obtain optimal solutions for the 2d-bin packing problem.
PLoS One
; 15(4): e0229358, 2020.
Article
em En
| MEDLINE
| ID: mdl-32251428
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.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Software
/
Biologia Computacional
/
Modelos Teóricos
Idioma:
En
Revista:
PLoS One
Assunto da revista:
CIENCIA
/
MEDICINA
Ano de publicação:
2020
Tipo de documento:
Article
País de afiliação:
México
País de publicação:
Estados Unidos