The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items.

A branch-and-price algorithm for the two-dimensional level strip packing problem / A. Bettinelli, A. Ceselli, G. Righini. - In: 4OR. - ISSN 1619-4500. - 6:4(2008), pp. 361-374. [10.1007/s10288-007-0051-7]

A branch-and-price algorithm for the two-dimensional level strip packing problem

A. Bettinelli
Primo
;
A. Ceselli
Secondo
;
G. Righini
Ultimo
2008

Abstract

The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items.
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
2008
4OR
http://hdl.handle.net/2434/5783
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/2434/60275
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 9
social impact