@[toc]

论文来源：（2014）Combinatorial Benders’ Cuts for the Strip Packing Problem
作者：Jean-François Côté 等人

一、摘要

• 我们研究了条形包装问题，即一组二维矩形物品必须被包装在一个固定宽度和无限高的矩形条形中，目的是使使用的高度最小。
• 这个问题很重要，因为它模拟了大量的现实应用，包括切割作业，如纸张或木材等材料的库存是大量的，必须以最小的浪费进行切割，调度问题，任务需要相同资源的连续子集，以及运输无法堆叠的物品时产生的集装箱装载问题。
• 在文献中，条形包装问题已经被几种启发式和精确算法攻击，然而，小规模的基准实例仍然没有被证实的最优性。
• 在本文中，我们提出了一种新的精确方法，可以在有限的计算量内求解大量的开放基准测试实例。
• 我们的方法是基于Benders的分解，在主程序中，我们将项目切割成单位宽度的切片，并将它们连续地打包在条中，在从程序中，我们试图通过固定其单位宽度切片的垂直位置来重建矩形项目。如果从节点证明重建项目是不可能的，那么就向主节点添加一个切点，并重复该算法。
• 我们证明了主问题和从问题都是强NP难问题，并通过定制预处理、上下边界技术和精确算法来解决它们。
• 我们还提出了几种新的技术来改进标准的弯曲切割，使用所谓的组合Benders切割和额外的提升程序。
• 大量的计算测试表明，相对于以前发表的算法，我们提出的算法提供了一个实质性的突破。

二、求解条形装箱的Benders分解

2.1 Notation

采用 normal patterns 减少摆放位置数量

什么是 normal patterns ？下面给出定义：

每个项目都尽可能往下和向左移动以改善结果，所以，任意一个项目都是挨着另一个项目或者边界的，这可以表示为，任意一个项目的摆放位置，都是其他项目的线性组合。

normal patterns 的公式如下：

而项目的线性组合，可以通过动态规划的方式计算

2.2 SPP的数学逻辑模型

SPP可以通过使用两组变量来建模:一个二元变量$x_{jp}$，如果项目$j$被包装在列$p$中，则值为1，否则为0，一个连续的非负变量$y_j$给出项目j的底边框的高度。然后使用单个变量$z$定义解的总高度。SPP可通过以下数学逻辑模型描述:

• 约束条件(6)要求每个项目都精确地包装在一列中。
• 约束(7)强制$z$不小于占据任何列$q$的项目的总高度
• 约束(8)强制$z$不小于任何项目$j$的上边界。注意，约束(7)对模型的正确性不是严格必要的，但对我们的分解方法是必要的。
• 逻辑约束(9)要求占用同一列$q$的项集合对应的垂直区间$[y_j,y_j+h_j]$不重叠。

2.3 分解方法

对于SPP问题，从公式（5）-（11）中删除变量y可以得到下面的式子：

主程序

Boschetti和Montaletti(2010)使用模型(12)-(15)得到其下界，假设现在已经计算出一个整数解，然后从程序将找到问题的可行解(如果有的话)

从程序( y-check )

如果y-check返回一个可行解，则我们得到了原SPP实例的最优解。否则我们禁止当前的解，在主问题上加一个Cut。为了这个目的，让：

$$ p_j^s=\sum_{p \in \mathscr{W}(j)} p x_{j p}^s $$

$$ \sum_{j \in N} x_{j, p_j^s} \leqslant n-1 $$

假设现在我们可以找到项目$C^s$⊆N的精简子集，这样，如果我们把它的所有项目放在位置$p^s_j$，那么问题$y-check$仍然有一个不可行的解决方案(我们寻找Cs的方法在§4中讨论)。然后，我们得到组合Benders的切割：

$$ \sum_{j \in C^s} x_{j, p_j^j} \leqslant\left|C^s\right|-1 $$

然后我们可以将SPP建模为以下主问题:

这种分解的优点在于，它可以利用主节点和从节点的组合结构，为它们开发定制的优化技术。

下图展示了分解的示例：

三、从问题的解决方案

3.1 复杂性分析

本文的作者证明了$y-check$是NP完全问题。有兴趣可以看看原文详细证明。

3.2 y-check的算法

针对y检验的求解，我们开发了几种算法，并利用组合枚举树，丰富了约简和深探准则，获得了最佳的计算性能。由此产生的算法，在本文的其余部分称为y-check算法，从三种新的预处理技术开始，依次调用。

3.2.1 预处理过程

3.2.1.1 Merge Items 合并项目

对于任意的项目 j ，我们可以将项目 j 左边的其他项目和右边的其他项目分成两个集合

首先我们考虑第一个块（从不增序排列的$p^s_j$中取）。对于项目j左边的项目集合A，如果A中所有项目的高都小于项目j的高，则调用组合枚举树将A中的项目打包到宽度为$p^s_j$，高度为$h_j$的子区域中。如果A中所有项目都能被打包进去，那我们就将他们合并为一个新的项目k，项目k具有宽度$w_k=p^s_j+w_j$，高度$h_k=h_j$，x坐标 $p^s_k=0$。这保持了解决方案的最佳性，因为没有其他项目可以进入。

3.2.1.2 Lift Item Widths 增大项目宽度

假设现在有N个块，如果我们要对 块i 增大宽度，则我们需要从N个块中取出 块i ，放在x=0处，然后将剩下的N-1个块按照任意组合放在 块i 的右边（不重叠），假设N-1的块任意组合的最大宽度值为$W_{N-1}$，块i的宽度为$w_i$，容器宽度为$W$，则 块i 增大的宽度为$(W-W_{N-1}-w_i)$（任意组合的宽度可以通过动态规划求得）

3.2.1.3 Shrink the Strip 缩小长条容器

假设对N个块求任意组合的最大宽度为$W_{max}$，直接令容器宽度等于$W_{max}$（这一过程也可以通过DP实现）

3.2.2 Enumeration Tree for Problem y-Check 组合枚举树

这里我用不到，所以没有细看（好吧，确实也看不懂哈哈哈哈）。

四、改进Benders Cut

在下面，我们假设我们得到了一个解决方案S，它没有通过 y-check，我们需要通过添加Cut，将其从主问题中剔除。

我们开发了一个使用四个步骤（所有新开发的想法）的程序，前三个步骤用来寻找项目的最小不可行子集，最后一步，我们试图通过线性模型的求解添加$x_{jp}$变量来进一步提升Cut质量。具体在下面详细介绍。

4.1 寻找项目的最小不可行子集

4.1.1 找到可以分割成两个子问题的线

第一步，寻找一条垂直的线，可以将容器内的块分成左右两部分，而没有任何一个块与该线重叠。这样就可以使得原本的容器被一份为二，其中至少有一个部分还是不可行的。这样就找到了不可行子集。同样，这个过程可以递归下去，直到所有子集不能再分。

4.1.2 用线去删除矩形（删矩形效率较低）

第二步，从左往右用一根垂直的线（列）去遍历容器横轴，每次将被线穿过的矩形移除后，再进行y-check，此时如果check通过了，那就...；如果check还是失败，说明当前被线穿过的矩形不是导致check失败的原因，可以直接将其移除，这样就找到了更小的不可行集合。

4.1.3 一个一个删除矩形

第三步根据给定的顺序一次考虑一个项目。它从S中删除当前项，并在缩减实例上重新执行y-check算法。如果结果可行，则将项目重新插入S，否则我们会找到不可行的原因，并将当前项目排除在S之外。无论如何，我们会重复下一个项目，直到所有项目都已扫描完毕。在扫描结束时，我们只剩下一个子集的项目，这仍然会导致不可行。

此步骤的结果取决于选择项目的顺序。出于这个原因，我们用不同的顺序进行了多次尝试。

第一次尝试根据面积的非递减值选择项目。

在第二次尝试中，我们为每个项目分配一个成功分数。在当前SPP实例的解决方案开始时，该值最初设置为0，然后如果在分解算法的先前迭代中从S中移除项目成功（即，如果它导致了仍然不可行的缩减实例），则该值增加一个单位。然后，我们执行的第二次尝试根据成功分数的非递减值选择项目。

第三次尝试只是随机选择项目，并执行10次。

4.2 Lifting the Cut 提升Cut

我们程序的第四步，也是最后一步。我们假设所有项目的x坐标都不再是一个确实值，而是一个范围，线性程序规定，每个项目在自己的一定范围内，任意移动，项目间的重叠关系不会改变。
线性程序的目标是，所有项目的范围总和最大。

五、条形包装问题的精确算法

前面章节中给出的数学模型和算法已被插入到求解SPP的整体算法中。该算法还利用了一些额外的技术来加速收敛到最优值，无论是来自相关文献的最佳实践，还是新开发的程序。由于这个原因，我们称之为BLUE，来自Benders的分解和上界增强。

算法1中概述了一个非正式的伪代码。

BLUE首先对实例进行预处理，并计算最优解值的上界U和下界L。

然后，只要L严格小于U，它就解决了SPP的识别版本，称为SPP（L），其中条带的高度固定为L，目的是找到不超过L的物品的可行包装（如果有）（该问题在文献中也称为二维正交包装问题；例如，参见Clautiaux等人2007）。SPP（L）实例首先被传递到预处理过程，然后通过两种精确的方法求解，即组合分支和定界以及第二节的Benders分解。

（由于我需要的是用这个方法解决2DBPP，而不是2DSPP，所以后面的内容就没有进行阅读了，大家感兴趣可以阅读原论文）

5.1 Preprocessing and Bounds

5.2 Closing the Gap

六、Computational Results

所有算法都在C++中实现。运行在Intel Core（TM）2 Quad CPU Q8200上，在Linux openSUSE 11.4操作系统下运行2.33 GHz。

通过设置参数RepeatPresolve=3、Reduce=3、Probe=3、Simmetry=5，并强制使用单个处理器（Threads=1），使用IBM Ilog Cplex 12.5解决了LP和MILP。

Martello等人（1999）使用标准动态规划和程序组合的背包问题解决了子集和问题。允许使用蓝色算法

七、Conclusions

我们提出了一种用于精确解决带状包装问题的创新算法，该算法基于Benders分解，并丰富了几种定制技术。我们证明了分解中出现的从属问题是困难的，但用一种实际有效的算法解决了它。

我们提高了标准Benders，通过使用组合Benders Cut的概念和一种新的提升程序进行切割，这在困难情况下非常有效。所提出的算法始终优于先前发表的方法。

它以相似或较小的计算工作量提供了大量的最优解，并首次解决了几十年来开放的经验证的最优实例。

我们提出的一般框架可以适用于解决其他二维包装问题，如二维背包和二维箱式包装。它也可以推广到更高维的问题。这些代表了有趣的未来研究方向。