SOLVING IRREGULAR STRIP PACKING PROBLEMS WITH FREE ROTATIONS USING SEPARATION LINES

ABSTRACT Solving nesting problems or irregular strip packing problems is to position polygons on a fixed width and unlimited length strip, obeying polygon integrity containment constraints and nonoverlapping constraints, in order to minimize the used length of the strip. To ensure non-overlapping, we use separation lines, i.e., straight lines that separate polygons. We present a nonlinear programming model that considers free rotations of the polygons and of the separation lines. This model uses a considerable smaller number of variables than the few other approaches proposed in the literature. We use the nonlinear programming solver IPOPT (an algorithm of interior points type), which is part of COIN-OR. Computational tests were run using established benchmark instances and the results were compared with the ones obtained with other methodologies in the literature that use free rotations.