The two-dimensional knapsack problem requires to pack a maximum profit subset of ‘‘small’’ rectangular items into a unique ‘‘large’’ rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem. In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are compu- tationally evaluated on well-known benchmark instances from the literature. The C++ source code of the recursive procedure is available upon request from the authors.

Exact Algorithms for the Two-Dimensional Guillotine Knapsack

LODI, ANDREA;MONACI, MICHELE
2012

Abstract

The two-dimensional knapsack problem requires to pack a maximum profit subset of ‘‘small’’ rectangular items into a unique ‘‘large’’ rectangular sheet. Packing must be orthogonal without rotation, i.e., all the rectangle heights must be parallel in the packing, and parallel to the height of the sheet. In addition, we require that each item can be unloaded from the sheet in stages, i.e., by unloading simultaneously all items packed at the same either y or x coordinate. This corresponds to use guillotine cuts in the associated cutting problem. In this paper we present a recursive exact procedure that, given a set of items and a unique sheet, constructs the set of associated guillotine packings. Such a procedure is then embedded into two exact algorithms for solving the guillotine two-dimensional knapsack problem. The algorithms are compu- tationally evaluated on well-known benchmark instances from the literature. The C++ source code of the recursive procedure is available upon request from the authors.
M. Dolatabadi; 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: http://hdl.handle.net/11585/100442
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 29
social impact