Logic based Benders' decomposition for orthogonal stock cutting problems

Maxence Delorme*, Manuel Iori, Silvano Martello

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

19 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)290-298
Number of pages9
JournalComputers and Operations Research
Volume78
DOIs
Publication statusPublished - 1 Feb 2017
Externally publishedYes

Keywords

  • Logic based Benders' decomposition
  • Orthogonal stock cutting problem
  • Pallet loading
  • Rectangle packing

Fingerprint Dive into the research topics of 'Logic based Benders' decomposition for orthogonal stock cutting problems'. Together they form a unique fingerprint.

Cite this