We present an asymptotic fully polynomial time approximation scheme for the two-dimensional generalization of Bin Packing, which requires packing (or cutting) a given set of rectangles from the minimum number of square bins, with the further restriction that packing the rectangles in the bins is done in two stages, as is frequently the case in real-world applications. To the best of our knowledge, this is the first approximation scheme for a nontrivial two-dimensional (and real-world) generalization of a classical one-dimensional packing problem in which rectangles have to be packed in (finite) squares. In addition to the approximability result, we obtain as a byproduct of our analysis an interesting structural result, namely the asymptotic optimality of the lower bound provided by the natural linear programming relaxation of the problem, having one variable for each bin pattern, that can be solved effectively by column generation techniques. Besides its practical relevance, a main reason to concentrate on the two-stage version of the problem is that its study continues to shed light on the general version. In particular, we strongly conjecture that the approximation guarantee of our algorithm for Two-Dimensional Bin Packing without the two-stage restriction is better than the best known ones. A simplification of the method leads to an approximation scheme for the two-stage version of Two-Dimensional Strip Packing.

We present an asymptotic fully polynomial time approximation scheme for the two-dimensional generalization of Bin Packing, which requires packing (or cutting) a given set of rectangles from the minimum number of square bins, with the further restriction that packing the rectangles in the bins is done in two stages, as is frequently the case in real-world applications. To the best of our knowledge, this is the first approximation scheme for a nontrivial two-dimensional (and real-world) generalization of a classical one-dimensional packing problem in which rectangles have to be packed in (finite) squares. In addition to the approximability result, we obtain as a byproduct of our analysis an interesting structural result, namely the asymptotic optimality of the lower bound provided by the natural linear programming relaxation of the problem, having one variable for each bin pattern, that can be solved effectively by column generation techniques. Besides its practical relevance, a main reason to concentrate on the two-stage version of the problem is that its study continues to shed light on the general version. In particular, we strongly conjecture that the approximation guarantee of our algorithm for two-dimensional Bin Packing without the two-stage restriction is better than the best known ones. A simplification of the method leads to an approximation scheme for the two-stage version of two-dimensional Strip Packing.

A. Caprara, A. Lodi, M. Monaci (2005). Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing. MATHEMATICS OF OPERATIONS RESEARCH, 30, 150-172 [10.1287/moor.1040.0112].

Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing

CAPRARA, ALBERTO;LODI, ANDREA;MONACI, MICHELE
2005

Abstract

We present an asymptotic fully polynomial time approximation scheme for the two-dimensional generalization of Bin Packing, which requires packing (or cutting) a given set of rectangles from the minimum number of square bins, with the further restriction that packing the rectangles in the bins is done in two stages, as is frequently the case in real-world applications. To the best of our knowledge, this is the first approximation scheme for a nontrivial two-dimensional (and real-world) generalization of a classical one-dimensional packing problem in which rectangles have to be packed in (finite) squares. In addition to the approximability result, we obtain as a byproduct of our analysis an interesting structural result, namely the asymptotic optimality of the lower bound provided by the natural linear programming relaxation of the problem, having one variable for each bin pattern, that can be solved effectively by column generation techniques. Besides its practical relevance, a main reason to concentrate on the two-stage version of the problem is that its study continues to shed light on the general version. In particular, we strongly conjecture that the approximation guarantee of our algorithm for two-dimensional Bin Packing without the two-stage restriction is better than the best known ones. A simplification of the method leads to an approximation scheme for the two-stage version of two-dimensional Strip Packing.
2005
A. Caprara, A. Lodi, M. Monaci (2005). Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing. MATHEMATICS OF OPERATIONS RESEARCH, 30, 150-172 [10.1287/moor.1040.0112].
A. Caprara; A. Lodi; M. Monaci
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/17029
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 20
social impact