Logic based Benders' decomposition for orthogonal stock cutting problems |
| |
Affiliation: | 1. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang 330013 ,Jiangxi, China;2. Department of Management Sciences, City University of Hong Kong, Tat Chee Ave, Kowloon Tong, Hong Kong;3. School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore;1. DEI “Guglielmo Marconi”, Alma Mater Studiorum - Università di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy;2. DISMI, Università di Modena e Reggio Emilia, Via Giovanni Amendola 2, 42122 Reggio Emilia, Italy;1. Institute of Numerical Mathematics, Technische Universität Dresden, Germany;2. School of Mathematics, The University of Edinburgh, United Kingdom;3. DISMI, Università di Modena e Reggio Emilia, Italy |
| |
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. |
| |
Keywords: | Orthogonal stock cutting problem Logic based Benders' decomposition Rectangle packing Pallet loading |
本文献已被 ScienceDirect 等数据库收录! |
|