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

Abstract

The two-dimensional cutting problem requires maximising the sum of the profits of small rectangular pieces, each of which has its own profit and size, obtained from a large rectangular plate. In this paper, a best-first branch-and-bound algorithm is proposed for the unconstrained problem, which has no limit on the number of pieces cut. Each small piece can have its own profit or can use the area of the piece instead of the profit. The proposed algorithm extends the concept of dominated patterns to remove the dominated patterns efficiently. Our proposed algorithm can also remove duplicate patterns and reduce the search space. The existing upper bound is revised and a new bounding strategy that can prune several nodes simultaneously is proposed. Additionally, new data structures are introduced to improve the performance of the algorithm. Computational results using the proposed algorithm on some benchmark examples were compared to the performance of previous algorithms to show the efficiency of the new algorithm. The proposed algorithm reduced the average computational time by up to 93% for 48 sample problems, excluding those problems that required almost no time using existing algorithms. Additionally, a large-scale problem that could not be solved in a reasonable time by the existing exact algorithms was solved successfully using the proposed algorithm.

Keywords:

• two-dimensional cutting problem
• optimisation
• branch-and-bound