Paper Info
Title
A branch-and-price algorithm for the two-dimensional level strip packing problem
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 NP-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.
Year
DOI
Venue
2008
10.1007/s10288-007-0051-7
A Quarterly Journal of Operations Research
Keywords
Field
DocType
90C27
Discrete mathematics,Mathematical optimization,Column generation,Branch and price,Algorithm,Continuous knapsack problem,Strip packing problem,Cutting stock problem,Knapsack problem,Mathematics
Journal
Volume
Issue
ISSN
6
4
1614-2411
Citations 
PageRank 
References 
4
0.46
11
Authors
3
Name
Order
Citations
PageRank
Andrea Bettinelli1193.43
Alberto Ceselli234130.53
Giovanni Righini352033.90