Enhanced solution for the irregular strip packing problem: valid inequalities and branching priorities

The irregular strip packing problem consists of packing a set of regular and irregular pieces on a board with fixed width and infinite length. All pieces are packed in such a way that they do not overlap while minimizing the used length of the board. Despite a few mathematical models having been proposed in the literature, solving the problem to optimality is still a challenge, and for only very few small instances, it is possible to find an optimal solution. In this paper, we apply a different branching strategy in the branch-and-bound method and add valid inequalities in a mathematical model of the literature. The usage of branching strategies and valid inequalities improve the performance of the commercial solver used to solve the mixed-integer programming model and provide the optimal solution for up to ten instances not proved in the previous paper.