A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems

Abstract

This paper is concerned with the problem of unconstrained two-dimensional cutting of small rectangular pieces, each of which has its own profit and size, from a large rectangular plate so as to maximize the profit-sum of the pieces produced. Hifi and Zissimopoulos's recursive algorithm using G and Kang's upper bound is presently the most efficient exact algorithm for the problem. We propose a best-first branch and bound algorithm based upon the bottom-up approach that is more efficient than their recursive algorithm. The proposed algorithm uses efficient upper bound and branching strategies that can reduce the number of nodes that must be searched significantly. We demonstrate the efficiency of the proposed algorithm through computational experiments.