AN ACCURATE BRANCH-AND-CUT METHOD FOR THE NESTING PROBLEM WITH GUILLOTINE CUTS

This paper proposes the first exact method for the strip packing problem with irregular pieces using guillotine cut constraints. Based on the Dotted Board Model, we have developed a branch-and-cut algorithm that eliminates infeasible patterns using valid cuts derived from D-functions. The pieces are convex, with discrete rotations, and the final cut is obtained by a valid sequence of guillotine cuts. We used unitary discretisation and a mathematical model based on $delta_{dtr}$ variables, subject to non-overlap, demand and length limit constraints. The combinatorial explosion was treated with clique coverage in the conflict graph and dynamic cut generation. In 76 benchmark instances, we proved optimality in 47% of the cases, with an average gap of 14.5% in the others, with a CPU time limit of one hour.