Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 78, Issue -, Pages 290-298Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2016.09.009
Keywords
Orthogonal stock cutting problem; Logic based Benders' decomposition; Rectangle packing; Pallet loading
Categories
Funding
- Capes (Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior) [A007/2013]
- MIUR (Italy)
Ask authors/readers for more resources
We consider the problem of packing a set of rectangular items into a strip of fixed width, without overlapping, using minimum height. Items must be packed with their edges parallel to those of the strip, but rotation by 90 is allowed. The problem is usually solved through branch-and-bound algorithms. We propose an alternative method, based on Benders' decomposition. The master problem is solved through a new ILP model based on the arc flow formulation, while constraint programming is used to solve the slave problem. The resulting method is hybridized with a state-of-the-art branch-and-bound algorithm. Computational experiments on classical benchmarks from the literature show the effectiveness of the proposed approach. We additionally show that the algorithm can be successfully used to solve relevant related problems, like rectangle packing and pallet loading.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available