A branch-and-cut algorithm for nesting problems with guillotine constraints
提出首个精确求解带断头台约束的不规则件排样问题的分支切割算法，基于点阵模型，通过D函数和不相容图识别并消除非断头台模式，适用于四种变体，多数算例求得最优解。
• First exact method for nesting problems with guillotine cuts • An innovative branch and cut based on the dotted board model • Extension of the dotted board model to new nesting problem variants Cutting and packing problems have been widely studied because of their potential to improve industrial processes economically and environmentally. While many variants have been studied, some, particularly those with practical features necessary for industrial adoption, remain poorly addressed by exact methods. One such variant is the irregular packing (or nesting) problem, where pieces and/or stock materials have irregular shapes. A key industrial requirement - guillotinable cutting patterns - has rarely been studied and only with heuristic methods. This paper proposes a branch-and-cut approach based on the dotted board model to address guillotinability in irregular packing. The method iteratively identifies and eliminates non-guillotinable patterns by introducing specific cuts. These are derived using D-functions and formed by cliques in an incompatibility graph of piece placements. The approach is adapted to four variants of the problem: Irregular Strip Packing, Irregular Placement, Irregular Knapsack, and Irregular Identical Item Packing. Computational experiments were conducted using benchmark instances across the four problem variants. The method found optimal solutions for most instances. Those instances that remained unsolved or for which optimality was not confirmed indicate areas for further research. A limitation of the method is that the nesting model restricts piece placement to discrete points. Extending the model to continuous domains is a significant but promising challenge for future work.