---

论文来源：（2006）Dual-Optimal Inequalities for Stabilized Column Generation
作者：Hatem Ben Amor 等人

---

摘要

• 列生成是求解大规模线性规划问题最成功的方法之一。然而，当问题变得更大时，已知会出现退化困难和长尾效应。幸运的是，一些对偶变量的稳定技术已被证明是有效的。
• 作者研究了利用两类对偶最优不等式来加速和稳定整个收敛过程。添加到对偶公式中，这些约束被所有或一个子集的对偶最优解所满足。因此，增广对偶问题的最优目标函数值与原问题相同。
• 向对偶问题添加约束会导致向原始问题添加列，并且可能失去解决方案的可行性。作者提出了两种方法来恢复原始可行性和最优性，这取决于所使用的不等式的类型。
• 作者对二进制和经典切割库存问题的计算实验，更具体地说，在所谓的三重实例上，表明使用相关的对偶信息对减少列生成迭代次数有巨大的影响。

---

一、介绍

列生成是大规模优化中最成功的方法之一。它包括通过一次只考虑变量的一小部分来求解巨大的线性规划。考虑线性规划 $P$，也称为主问题，以及它的对偶问题 $D$，其中 $A$ 是一个 $m\times n$ 矩阵：

在列生成过程的任意迭代 $k$ 中，只处理一个 $A$ 的列子集 $A_k$。通过求解一个受限的主问题，得到一个原始可行解 $x_k^{\ast }$，以及一个由对偶乘数组成的向量 ${\pi }_k^{\ast }$。有了这些乘数，我们计算矩阵 $A$ 中所有列的最小 Reduced Cost 来生成一些具有负 Reudced Cost 的列。如果存在这样的列，就将其加入受限主问题中，否则 $(x_k^{\ast },{\pi }_k^{\ast })$ 分别是 $P$ 和 $D$ 的最优解和对偶最优解。

---

二、对偶最优不等式（Dual-Optimal Inequalities）

假设 $P$ 和 $D$ 有有限个最优解。令 $D^{\ast }$ 是 $D$ 的最优解集合，同时假设对偶空间受到一组新的约束条件的限制（它截断了对偶空间的一部分）。

如果 D ∗ ⊆ { π : E T π ≤ e } D^* \subseteq \{\pi : E^T \pi \le e\} D∗⊆{π:ETπ≤e} ，则 $E^T\pi \le e$ 被称为对偶最优不等式的集合。这些不等式实际上是对偶最优多面体上的有效不等式，即，当添加它们到对偶公式中时，不会削减任何对偶最优解。

如果上述条件不一定全部满足，即条件变为：对于 $\pi \in D^{\ast }$，条件变为 ∅ ≠ D ∗ ∩ { π : E T π ≤ e } \varnothing \neq D^* \cap \{\pi : E^T \pi \le e\} ∅=D∗∩{π:ETπ≤e}，则 $E^T\pi \le e$ 可以切割对偶最优解的非空子集。因此，$E^T\pi \le e$ 被称为深度对偶最优不等式（deep dual-optimal inequalities）。

事实上，对偶最优不等式是所有对偶最优解都满足的不等式；深度最优不等式是至少有一个对偶最优解满足的不等式。

现在，我们考虑将 $E^T\pi \le e$ 加入 $D$，并令 $\tilde{D}$ 为加入之后得到的对偶问题，以及相关的原始问题定义为 $\tilde{P}$：

当添加的约束裁断了对偶可行区域的非空子集时，$\tilde{D}$ 是 $D$ 的一个受限版本。然后通过引入非负变量 $y$ 的向量来松弛原始空间，并通过引入由这些变量引起的项 $e^{T}y$ 来改变目标函数。与变量 $y$ 对应的列在原始问题中作为静态列，而不是生成的列。也就是说，它们在列生成之前引入。这确保了在任何列生成迭代中，相应的受限主问题的最优性下计算的对偶乘子都满足添加的约束集合 $E^T\pi \le e$。因此，这可以看作一种预处理技术。但是，它也可以动态地实现，即在每个列生成迭代结束时选择要添加的不等式，还可以消除冗余的对偶不等式，使主问题求解更加高效。这些策略都是有用的，特别是当在一个非常大的集合中难以选择最佳不等式时。

直观而言，对偶最优不等式越紧，列生成求解过程就越高效。

实际上，这是因为不等式限制了可能的对偶值的集合，并且对偶空间中的震荡在幅度和频率上都减小了。在最优乘子周围，只生成相关的对偶割平面，以更快速地描述拉格朗日对偶函数的下包络。因此，不会生成无用的列。

从原始的观点来看，我们已经知道这个公式是松弛的。另外，这些静态列可能具有使求解过程更有效的特殊结构。当这些列允许考虑许多不需要显式生成的列时，就会出现这种情况（见第四节）。

$P,D,\tilde{P}$ 和 $\tilde{D}$ 的最优解分别由 $x^{\ast },{\pi }^{\ast },({\tilde{x}}^{\ast },y^{\ast })$ 和 ${\tilde{\pi }}^{\ast }$ 表示。下面的命题给出了当 $E^T\pi \le e$ 为对偶最优不等式时，原问题和修正问题的最优值之间的明显关系。

命题1：如果 D ∗ ∩ { π : E T π ≤ e } ≠ ∅ D^* \cap \{\pi : E^T \pi \le e\} \neq \varnothing D∗∩{π:ETπ≤e}=∅，则 $v(\stackrel{~}{}P)=v(\tilde{D})=v(D)=v(P)$，并且 $\tilde{D}$ 的任意最优解 ${\pi }^{\ast }$ 也是 $D$ 的最优解。

命题2：令 $({\tilde{x}}^{\ast },y^{\ast })$ 是 $\tilde{P}$ 的一个最优解，然后假设 $E^T\pi \le e$ 是对偶最优不等式的一个集合。因此，当 $E{y}^{\ast }=0$ 时，${\tilde{x}}^{\ast }$ 是 $P$ 的一个最优解。令 ${\tilde{\pi }}^{\ast }$ 是 $\tilde{D}$ 的一个最优解。尽管 ${\tilde{\pi }}^{\ast }$ 是 $D$ 的一个对偶最优解，但当 $E{y}^{\ast }\ne 0$ 时，${\tilde{x}}^{\ast }$ 对于 $P$ 是不可行的（因为 $A{\tilde{x}}^{\ast }\ne b$）。

因此，从上面的证明可以得出，当 ${\tilde{x}}^{\ast }$ 对于 $P$ 可行时，$e^T{y}^{\ast }=0$。

---

三、确定P的最优原始解

令 $({\tilde{x}}^{\ast },y^{\ast })$ 是 $\tilde{P}$ 的一个最优解，${\tilde{\pi }}^{\ast }$ 是 $\tilde{D}$ 的一个最优解。当 $E{y}^{\ast }\ne 0$ 时，${\tilde{x}}^{\ast }$ 对于 $P$ 不可行（因为 $A{\tilde{x}}^{\ast }\ne b$）。

由于我们的目标是获取 $P$ 的最优解，因此我们需要一种有效的方法来恢复给定原问题 $\tilde{P}$ 和对偶问题 $\tilde{D}$的原始最优性。

接下来，我们考虑添加的对偶不等式或相应的原始列具有特殊解释的情况，允许从 ${\tilde{x}}^{\ast }$ 建立 $P$ 的最优解。

命题3：假设 $\tilde{P}$ 的任意一个可行解为 $(\tilde{x},y)$，它有可能为 $P$ 建立一个可行解，使得 $c^{T}x\le c^T\tilde{x}+e^{T}y$。然后，对于任意 $\tilde{P}$ 的最优解 $({\tilde{x}}^{\ast },y^{\ast })$，对应的解 ${\tilde{x}}^{\ast }$ 就是 $P$ 的最优解。

这种情况发生在稍后考虑的切割下料应用中。然而，当情况并非如此时，需要一种有效的方法来恢复 $P$ 的最优解。该过程取决于所使用的对偶不等式的类型。

假设 $E^T\pi \le e$ 是对偶最优不等式的一个集合。通过求解一个稍微修改的问题 ${\tilde{P}}_{\epsilon }$（对应的对偶问题为 ${\tilde{D}}_{\epsilon }$），可以得到 $P$ 的最优解。给定一个标量向量 $\epsilon >0$，我们用 $E^T\pi \le e+\epsilon$ 替换 $\tilde{P}$ 和 $\tilde{D}$ 定义中的 $E^T\pi \le e$：

命题4：令 $({\tilde{x}}_{\epsilon }^{\ast },y_{\epsilon }^{\ast })$ 是 ${\tilde{P}}_{\epsilon }$ 的一个最优解，则 $y_{\epsilon }^{\ast }=0$，且 ${\tilde{x}}_{\epsilon }^{\ast }$ 是 $P$ 的一个最优解。

标量向量 $\epsilon$ 必须足够小，以保证应用于 ${\tilde{P}}_{\epsilon }$ 的列生成的效率。另外，太小的值可能也会导致数值困难和对偶不等式集无效，这取决于现有线性规划求解器使用的参数的准确性。

现在假设 $E^T\pi \le e$ 是深度对偶最优不等式的一个集合。给定 $\tilde{D}$ 的对偶最优解为 ${\tilde{\pi }}^{\ast }$ 和一个标量向量 $\Delta >0$，定义稳定的原问题 $\bar{P}({\tilde{\pi }}^{\ast })$ 和对偶问题 $\bar{D}({\tilde{\pi }}^{\ast })$ 如下：

稳定的对偶问题 $\bar{D}({\tilde{\pi }}^{\ast })$ 被构造为对偶解被限制在一个严格包含 $\tilde{D}$ 的最优解 ${\tilde{\pi }}^{\ast }$ 的非空盒子中，该最优解确实是 $D$ 的最优解（根据命题1）。利用非负冗余变量 $y_1$ 和松弛变量 $y_2$，给出了相应的稳定的原始问题 $\bar{P}({\tilde{\pi }}^{\ast })$ 的定义。

给出 $E^T\pi \le e$ 为深度对偶最优不等式的一个集合，则 $P$ 的一个最优原始解可以通过一个两阶段的方法获得。首先，我们求解 $\tilde{P}$ 获得一个 $D$ 的对偶最优解 ${\tilde{\pi }}^{\ast }$。其次，我们求解稳定的原始问题 $\bar{P}({\tilde{\pi }}^{\ast })$。下面的命题表明第二阶段的解就是 $P$ 的最优解。

命题5：令 $E^T\pi \le e$ 是一个深度对偶最优不等式的集合，$({\bar{x}}^{\ast },y_1^{\ast },y_2^{\ast })$ 是 $\bar{P}({\tilde{\pi }}^{\ast })$ 的一个原始最优解。则 ${\bar{x}}^{\ast }$ 是 $P$ 的一个原始最优解。

注意，上面的证明并不依赖于 $\bar{D}({\tilde{\pi }}^{\ast })$ 的实际对偶最优解，即 ${\bar{\pi }}^{\ast }$ 可能等于（也可能不等于） ${\tilde{\pi }}^{\ast }$ 。首先用列生成求解松弛原问题 $\tilde{P}$ 得到 ${\tilde{\pi }}^{\ast }$ 的效率主要取决于对偶不等式的紧密性。对于第二阶段，即 $\bar{P}({\tilde{\pi }}^{\ast })$ 的解，当用严格包含对偶最优解的小框初始化时，赞成列生成的效率（参见第五节）。通过使用在求解 $P$ 时已经生成的列，这种效率更有可能得到加强。

---

四、二元切割下料问题

给定一组宽度为 $L$ 的卷和一组物品集合 I = { 1 , 2 , . . . , m } I=\{1,2,...,m\} I={1,2,...,m}（其中每个物品 $i\in I$ 具有长度 $w_i$ 和单位需求）。二元切割下料问题（BCS）的目的是找到满足需求的一组切割模式，同时最小化所使用的卷的数量。

可行的切割模式是一个子集 $C\subset I$ 使得 ${\sum }_{i\in C}{w}_i\le L$。令 $\Omega$ 为所有可行切割模式的集合。广为人知的公式（Gilmore 和 Gomory 1961）使用二元变量： 如果在解决方案中使用了切割模式 $p$ ，则 $x_p=1$，否则 $x_p=0$。

我们感兴趣的是解这个问题的线性松弛。分别考虑以下原始和对偶线性规划公式 $P_{BCS}$ 和 $D_{BCS}$，其中，二元系数 $a_{ip}$ 表示模式 $p$ 中是否使用了物品 $i$：

原始问题是通过列生成求解的。事实上，二元切割下料问题也可以模拟为一个车辆路径问题，其中车辆和它们的容量分别对用于要切成小块的大卷和它们的宽度。这些模式是通过求解带时间窗的最短路径问题的一种特殊情况（0-1背包问题）得到的。

在作者的例子中，它是在一个无环图上表述的，每个节点上都有一个容量窗口，并通过动态规划求解。

物品大小为整数的大型装箱实例（BCS）往往有几个相同大小的物品，这些物品最好被一个需求等于重复数量的单一物品取代。这种聚合相当于要求相同长度的项对应的对偶变量相等。下面的命题强调了这一点，它表明这些条件确实是深度对偶最优不等式。结果还表明，对于 BCS ，聚合保留了相同的线性规划界。

命题6：对于任意二元切割下料问题的两个物品 $i$ 和 $j$ ，如果 $w_i=w_j$ ，则 $D_{BCS}$ 存在一个对偶最优解满足 ${\pi }_i^{\ast }={\pi }_j^{\ast }$ 。

作者测试了两种不同的方式来施加这些对偶约束：

1. 在原始公式中相同项目的约束聚合
2. 在对偶公式中显式添加相等约束

每种方法对问题的大小和结构有不同的影响。我们分别处理它们。

4.1 约束聚合

相同大小的物品对应的需求约束聚合为一个约束，其右侧需求大于1。因此，一个可行的模式可能会被使用不止一次，一个项目可能会出现不止一次。

4.2 相等约束

对物品集合按照大小降序排序，对于每个物品对 $(i,i+1)$，如果 $w_i=w_{i+1}$ ，则在 ${\tilde{D}}_{BCS}$ 中添加相等约束 $-{\pi }_i+{\pi }_{i+1}=0$。这将导致在 ${\tilde{P}}_{BCS}$ 中添加相应的零成本变量 $y_{i,i+1}$ ，在第 $i$ 行，其系数为 -1，在第 $i+1$ 行，其系数为 1，其他行系数为 0。列数略有增加，但行数保持不变，背包子问题的大小也保持不变。

4.3 计算结果

作者使用了运筹学库中最难的问题(Beasley 1990)作为测试问题。这是参数 L = 150 , m ∈ { 500 , 1000 } , l m i n ∈ { 1 , 20 } , l m a x = 100 , ( w i ) i ∈ I ∼ U ( l m i n , l m a x ) L = 150,m\in \{500,1000\},l_{min}\in \{1,20\},l_{max}=100,(w_i)_{i\in I} \sim U(l_{min},l_{max}) L=150,m∈{500,1000},lmin​∈{1,20},lmax​=100,(wi​)i∈I​∼U(lmin​,lmax​) 的四类均匀生成问题(u-problem)；

还有一类三联问题(t-problem)，其中每个卷被切成恰好三阶而不丢失，包含 $m=501$ 个项目。物品长度都相对接近于 $L/3$ ，并且(整数和连续的)最优掷出次数为 $m/3$ 。为每个类生成十个实例，并计算每个类的平均值。

表1给出了使用标准列生成、项目约束聚合和添加相等约束为每个类获得的结果。$Lr(s)$、$mp(s)$ 和 $sp(s)$ 分别给出了用于解决线性松弛、主问题和子问题的CPU时间(以秒为单位)(其中 $Lr(s)=mp(s)+sp(s)$ )，$itr$ 是达到最优性所需的列生成迭代次数，$\%itr$ 是列生成迭代次数的相对改进。

由于子问题是通过动态规划作为约束最短路径问题来解决的，因此在最优状态下可以使用许多负的降低成本列。因此，在每个列生成迭代中生成几个列。值得注意的是，这两种方法使用相同的列生成器，这并不影响它们之间的比较。

---

五、切割下料问题

切割下料问题（CSP）和二元切割下料问题相似，不同之处在于要求 $b_i$ 为一般正整数。因此，一个项目可以在一个可行的切割模式中出现不止一次。将子问题中的背包约束替换为：

Gilmore and Gomory(1961)也表明，需求约束中的等号可以用大号或等号代替，并且通过这种简单的转换，列生成求解过程略有加快。线性松弛 $P_{CS}$ 及其对偶 $D_{CS}$ 的公式如下：

根据Gilmore和Gomory提出的变换，对偶变量只能取非负值。因此，${\pi }_i\ge 0,i\in I$ 是一组对偶最优不等式。

现在讨论Valerio de Carvalho (2005b)引入的对偶子集不等式。利用命题3，作者证明了这样一个事实，即有可能在给定修改的原始问题的最优解的情况下重建原始最优解，从而证明了这些切割的使用。在本文中，作者证明了这些对偶切割实际上是切料问题的对偶最优不等式：

命题7：对于每个物品 $i$ 和 子集 $S\subset I$，$D_{CS}$ 的任意一个最优解满足：$w_i\ge {\sum }_{l\in S}{w}_l=>{\pi }_i^{\ast }\ge {\sum }_{l\in S}{\pi }_l^{\ast }$

当 $|S|=1$ 时，这些子集不等式有一个有趣的解释。$D$ 的任意最优解都满足排序：

此外，将这个结果应用于相同长度的两个项目 $i$ 和 $j$，我们得到 $D_{CS}$ 的所有对偶最优解都满足 $w_i=w_j=>{\pi }_i^{\ast }={\pi }_j^{\ast }$ 。

然而，这并不适用于二元切割下料问题，因为在生成二元切割模式时，存在一个隐含的约束，即一个项目不能切割超过一次，而对于经典的所谓切割下料问题，一个项目可能被切割任意整数次，而与该项目的需求无关。

例子：考虑一个二元切割下料问题，其中 $m=2,w_1=4,w_2=4,W=10$ 并且需求都为1。它只有三种可行的二元模式：$\{[w_1,w_2],[w_1],[w_2]\}$，对应的非负原始变量为 $x_1,x_2,x_3$。对偶域定义为：

很容易验证，对偶点 $(1,0)$ 和 $(0,1)$ 是与原最优解 $x_1=1,x_2=x_3=0$ 对应的对偶最优解，即使这些对偶解不满足 ${\pi }_1={\pi }_2$ （$w_1=w_2$）。的确，命题6只是规定存在一个使 ${\pi }_1={\pi }_2$ 的对偶最优解（此处为上述对偶最优解的凸组合）。

现在，把这个例子看作一个经典的库存问题，也就是说，我们从模式生成中去掉了二元限制。两种新的模式是可行的：$[w_1,w_1],[w_2,w_2]$。这些用两个新的约束修改了对偶空间：$2{\pi }_1\le 1$ 和 $2{\pi }_2\le 1$。唯一的对偶最优解现在是 ${\pi }_1={\pi }_2=1/2$，这是命题7的直接结果，其中证明了所有最优解满足 ${\pi }_1={\pi }_2$。

子集不等式的数量是指数的，我们必须选择一个合理的数量来使用。如果 $|S|$ 是固定的，则可能的切割次数是 $m$ 的多项式。最简单的情况是 $|S|\le 2$。当 $|S|=2$ 时，可能的对偶约束数为 $O(m^3)$。为了提高效率，特别是当 $m$ 很大时，Valerio de Carvalho (2005b) 对每个 $i\in I$ 只使用了一个对偶约束(如果有的话)。这个不等式是使用最小的索引 $j$ ( 对应最大的宽度$w_j$ ) 生成的，如果存在这样的值，那么存在 $k$，使得 $w_i\ge w_j+w_k$。这将会导致向 ${\tilde{D}}_{CS}$ 中添加 $O(m)$ 个约束，并向原始问题 ${\tilde{P}}_{CS}$ 中添加列。

添加到原始问题的列具有特殊的含义。引入零成本变量 $y_{i,S}$ 的系数为 -1(row=$i$)，1（row=$l\in S$）和 0（其他行）。这允许原始问题在包含 $i$ 的任何可行模式中用 $S$ 的项替换项目 $i$ 。

因此，包含 $i$ 的切割模式的存在以及变量 $y_{i,S}$ 对应的列的存在隐式地保证了所有地可行切割模式的存在，其中 $i$ 被集合 $S$ 中的项所取代，因此不需要生成这些列。这种推理可以递归地应用于 $S$ 中的某些项，因此也隐含地考虑了一些具有 $|S|\ge 3$ 的子集不等式。

最后，上述段落给出了一种直接的方法来重建一个原始最优解。对于任何覆盖项 $i$ ，覆盖模式必须通过将 $i$ 替换为 $S$ 中 $y_{i,S}>0$ 的项来修改。

5.1 计算结果

---

六、三元组的深度对偶最优不等式（Deep Dual-Optimal Inequalities for the Triplet）

t问题中的三元组是这样构建的在最优状态下损失为零。表2显示了给定它们的大小，这些问题相当困难，并且需要非常多的列生成迭代。然而，对于没有损失的 $P_{CS}$ 实例，有一个非常有趣的结果。事实上，从物品的长度可以直接计算出最优掷出次数，即所有物品的总长度除以 $L$ ，而且还可以得到对偶最优解：

命题8：考虑一个没有损失的 $P_{CS}$ 实例，则 ${\pi }_i^{\ast }=w_i/L$ 是一个对偶最优解。

如命题5，给定已知的对偶最优解 ${\tilde{\pi }}^{\ast }$ ，可以使用以下深度对偶最优不等式 ${\tilde{\pi }}^{\ast }-\Delta \le \pi \le {\tilde{\pi }}^{\ast }+\Delta$ ，其中 $\Delta >0$，是一个小的标量向量。这些框不等式限制了所有列生成迭代期间的对偶值。注意到使用松弛变量 $y_2=b$ 已经可以获得基本解，并且对于相应的基（单位矩阵），对偶乘数对于 $\Delta$ 几乎是最优的，并且取值 $({\tilde{\pi }}^{\ast }+\Delta )$，从而加速了问题 $\bar{P}({\tilde{\pi }}^{\ast })$ 的解决。

6.1 计算结果

---

七、总结

本文讨论了对偶信息对列生成效率的作用。对偶最优不等式不会切割任何对偶最优解，而深度的对偶最优解可能会移除其中的一个非空子集。

这些不等式的使用限制了对偶空间，同时放宽了原始可行集。从而限制了对偶乘子可能的中间值集合，更快地得到对偶最优解。然而，原始可行性可能会丢失，需要恢复原始最优解。在某些情况下，对偶不等式对于当前的应用具有特殊的意义，并且可以在给定修正问题的解的情况下建立原始最优解。当这是不可能的时候，作者提出了两种一般的方法来恢复原始的可行性和最优性，每一种都针对一个类型的不等式。

众所周知，用于二进制切割下料问题的聚合技术可以看作是实现一组深度对偶最优不等式的隐式方法。这种隐式方法大大减少了行数，因此无法确定对偶不等式的实际影响。因此，作者测试了这些对偶约束的显式实现，结果是在不改变行数的情况下增加了原始变量的数量。我们在减少列生成迭代数方面也观察到同样的改善，这证实了相关对偶信息的重要性。

对于切割下料问题，作者证明了Valerio de Carvalho (2005b)引入的子集不等式可以加速列的生成。

作者还表明，当使用由易于计算的对偶最优解导出的对偶最优盒不等式求解三元组实例时，通常被认为是困难的切料实例，实际上非常容易。

计算结果再次表明，显著的对偶信息明显有利于列生成求解过程。一个类似的程序已经被提出用于设计线性规划的有效交叉方法(Ben Amor et al . 2006)。给定由内点算法提供的最优内原解和对偶最优解 ${\pi }^{\ast }$，用单纯形算法重新求解原问题，同时在对偶公式加入小的对偶盒不等式(如 ${\pi }^{\ast }\pm 10^{-3}$ )。这个简单的程序是非常稳定和相当快的。

最后，切割下料问题是一个结构良好的优化问题，但许多其他组合优化问题也具有良好的结构。对于切割下料问题的结果表明，寻找其他组合问题的对偶最优解的更好的表征是有意义的。