Improved dynamic programming algorithms for unconstrained two-dimensional guillotine cutting

In the unconstrained two-dimensional cutting problem (U2DCP), we are given a large rectangular sheet to be cut in order to extract small rectangular pieces, with no limits on the number (demand) of desired pieces. We face the variant with guillotine constraint, requiring to cut any rectangle in two parts through vertical/horizontal cuts with end points on the rectangle boundaries. For a given U2DCP instance, the dynamic programming approach can be used either to optimally solve it, or to obtain a full matrix of upper bounds suitable for the constrained variant of the problem where limits exist on the piece demands. The elements of the full matrix are also usable as partial solutions to build lower bounds for the non-guillotine variant. In this paper, we propose two major improvements to a dynamic programming procedure previously shown to be capable of solving very large size instances. First, we introduce a new option for one of the three conditions used for the anti-redundancy strategies on cut coordinates. Second, following the effort of the Operations Research community to exploit the feature of modern CPUs containing multi-core processors, we provide a parallelization scheme. An extended computational campaign is presented. We compare the upgraded procedure with its previous version on a single thread and with the currently state-of-the-art algorithm for multi-thread platforms, outperforming both in terms of execution time on average by a factor of 1.7 and 12, respectively, or for some problem instances up to 4.5 and 50, respectively. Moreover, the new procedure can solve two very large instances previously unsolved, as well as the new huge instances proposed in this paper.