Given a set of rectangular items, and an unlimited number of identical rectangular bins, we consider the problem of allocating, without overlapping, all the items to the minimum number of bins. We assume that the items may be rotated by 90°. The problem is strongly NP-hard, and has several industrial applications. No specific lower bound is known for it. We present a lower bound which explicitly takes into account the possible item rotation. The bound is embedded into an exact branch-and-bound algorithm. The average performance is evaluated through computational experiments. © 2002 Elsevier Science B.V.
Dell'Amico M., Martello S., Vigo D. (2002). A lower bound for the non-oriented two-dimensional bin packing problem. DISCRETE APPLIED MATHEMATICS, 118(1-2), 13-24 [10.1016/S0166-218X(01)00253-0].
A lower bound for the non-oriented two-dimensional bin packing problem
Martello S.;Vigo D.
2002
Abstract
Given a set of rectangular items, and an unlimited number of identical rectangular bins, we consider the problem of allocating, without overlapping, all the items to the minimum number of bins. We assume that the items may be rotated by 90°. The problem is strongly NP-hard, and has several industrial applications. No specific lower bound is known for it. We present a lower bound which explicitly takes into account the possible item rotation. The bound is embedded into an exact branch-and-bound algorithm. The average performance is evaluated through computational experiments. © 2002 Elsevier Science B.V.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
