A parallel branch-and-bound-and-check algorithm for nesting

The irregular strip packing problem, also known as nesting, involves computing a non-overlapping placement of a set of polygons onto a rectangular strip of fixed width and minimum length. Recent performance gains in Mixed-Integer Linear Programming (MILP) solvers have encouraged the proposal of exact optimization models for nesting. The Dotted-Board (DB) MILP model solves the discrete version of the problem by constraining the positions of the polygons to lie on a fixed-point grid. However, the number of non-overlapping constraints grows quadratically with the number of dots and polygon types, which has encouraged the proposal of a Clique Covering reformulation (DB-CC), setting the current state-of-the-art by significantly reducing the constraints required. However, DB-CC requires a significant preprocessing time to compute edge and vertex clique coverings. Moreover, current knowledge of the stable set polytope suggests that achieving a tighter formulation is unlikely. Thus, our main hypothesis is that an ad hoc exact algorithm requiring no preprocessing might be a better option to solve the DB model than the costly Branch-and-Cut approach. This work proposes an exact parallel branch-and-bound-and-check algorithm to solve the DB model from the inverse conflict graph, using ad hoc data structures, bounding, and forward-checking to prune the search space. We also introduce a new Lower Bound (LB) algorithm as a by-product. Our experiments show that our algorithm significantly reduces the resolution time compared to DB-CC and eliminates its preprocessing step. Seventeen open instances are solved up to optimality, and our LB algorithm proves the optimality of fifty-one instances.