An improved best-first branch-and-bound algorithm for constrained two-dimensional guillotine cutting problems

Abstract

The constrained two-dimensional cutting problem involves maximising the sum of the profits obtained from small rectangular pieces cut from a large rectangular plate where the number of each type of cut piece cannot exceed a prescribed quantity. This paper proposes a best-first branch-and-bound algorithm to find the optimal solution to the problem. The proposed algorithm uses an efficient method to remove the duplicate patterns, and it improves the existing upper bounds. It also prevents the construction of dominated patterns and introduces a new bounding strategy that can prune more than one node at a time. Computational results are compared with a well-known exact algorithm to demonstrate the efficiency of the proposed algorithm. The proposed algorithm is as fast as or faster than the existing algorithm and reduces the average computing time by up to 99% for benchmark problems. For some problems, it can also find optimal solutions that existing algorithms are not able to find.

Keywords:

• cutting problem
• optimisation
• branch and bound
• constrained two-dimensional cutting
• guillotine cutting pattern

Acknowledgements

This work was supported by the research fund of Hanyang University (HY-2011-P).