Logic based Benders' decomposition for orthogonal stock cutting problems. (February 2017)

• Record Type: Journal Article
• Authors: Delorme, Maxence; Iori, Manuel; Martello, Silvano
• Is Part Of: Computers & operations research. Volume 78(2017)
• Page Start: 290
• Page End: 298
• Publication Date: 2017-02
• Subjects: Orthogonal stock cutting problem -- Logic based Benders' decomposition -- Rectangle packing -- Pallet loading; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.09.009
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Abstract : Highlights: Orthogonal stock cutting problem, rectangle packing and pallet loading. Mathematical model and exact approach. Logic based Benders' decomposition. Extensive computational experiments.