58同城百姓网,四川网站推广优化,做外贸学习网站,wordpress改站教程文章目录 摘要一、介绍二、对偶最优不等式#xff08;Dual-Optimal Inequalities#xff09;三、确定P的最优原始解四、二元切割下料问题4.1 约束聚合4.2 相等约束4.3 计算结果 五、切割下料问题5.1 计算结果 六、三元组的深度对偶最优不等式#xff08;Deep Dual-Optimal I… 文章目录 摘要一、介绍二、对偶最优不等式Dual-Optimal Inequalities三、确定P的最优原始解四、二元切割下料问题4.1 约束聚合4.2 相等约束4.3 计算结果 五、切割下料问题5.1 计算结果 六、三元组的深度对偶最优不等式Deep Dual-Optimal Inequalities for the Triplet6.1 计算结果 七、总结 论文来源2006Dual-Optimal Inequalities for Stabilized Column Generation 作者Hatem Ben Amor 等人 摘要
列生成是求解大规模线性规划问题最成功的方法之一。然而当问题变得更大时已知会出现退化困难和长尾效应。幸运的是一些对偶变量的稳定技术已被证明是有效的。作者研究了利用两类对偶最优不等式来加速和稳定整个收敛过程。添加到对偶公式中这些约束被所有或一个子集的对偶最优解所满足。因此增广对偶问题的最优目标函数值与原问题相同。向对偶问题添加约束会导致向原始问题添加列并且可能失去解决方案的可行性。作者提出了两种方法来恢复原始可行性和最优性这取决于所使用的不等式的类型。作者对二进制和经典切割库存问题的计算实验更具体地说在所谓的三重实例上表明使用相关的对偶信息对减少列生成迭代次数有巨大的影响。 一、介绍
列生成是大规模优化中最成功的方法之一。它包括通过一次只考虑变量的一小部分来求解巨大的线性规划。考虑线性规划 P P P也称为主问题以及它的对偶问题 D D D其中 A A A 是一个 m × n m × n m×n 矩阵 在列生成过程的任意迭代 k k k 中只处理一个 A A A 的列子集 A k A_k Ak。通过求解一个受限的主问题得到一个原始可行解 x k ∗ x^*_k xk∗以及一个由对偶乘数组成的向量 π k ∗ \pi^*_k πk∗。有了这些乘数我们计算矩阵 A A A 中所有列的最小 Reduced Cost 来生成一些具有负 Reudced Cost 的列。如果存在这样的列就将其加入受限主问题中否则 ( x k ∗ , π k ∗ ) (x^*_k,\pi^*_k) (xk∗,πk∗) 分别是 P P P 和 D D D 的最优解和对偶最优解。 二、对偶最优不等式Dual-Optimal Inequalities
假设 P P P 和 D D D 有有限个最优解。令 D ∗ D^* D∗ 是 D D D 的最优解集合同时假设对偶空间受到一组新的约束条件的限制它截断了对偶空间的一部分。
如果 D ∗ ⊆ { π : E T π ≤ e } D^* \subseteq \{\pi : E^T \pi \le e\} D∗⊆{π:ETπ≤e} 则 E T π ≤ e E^T \pi \le e ETπ≤e 被称为对偶最优不等式的集合。这些不等式实际上是对偶最优多面体上的有效不等式即当添加它们到对偶公式中时不会削减任何对偶最优解。
如果上述条件不一定全部满足即条件变为对于 π ∈ D ∗ \pi \in D^* π∈D∗条件变为 ∅ ≠ D ∗ ∩ { π : E T π ≤ e } \varnothing \neq D^* \cap \{\pi : E^T \pi \le e\} ∅D∗∩{π:ETπ≤e}则 E T π ≤ e E^T \pi \le e ETπ≤e 可以切割对偶最优解的非空子集。因此 E T π ≤ e E^T \pi \le e ETπ≤e 被称为深度对偶最优不等式deep dual-optimal inequalities。
事实上对偶最优不等式是所有对偶最优解都满足的不等式深度最优不等式是至少有一个对偶最优解满足的不等式。
现在我们考虑将 E T π ≤ e E^T \pi \le e ETπ≤e 加入 D D D并令 D ~ \tilde{D} D~ 为加入之后得到的对偶问题以及相关的原始问题定义为 P ~ \tilde{P} P~ 当添加的约束裁断了对偶可行区域的非空子集时 D ~ \tilde{D} D~ 是 D D D 的一个受限版本。然后通过引入非负变量 y y y 的向量来松弛原始空间并通过引入由这些变量引起的项 e T y e^T y eTy 来改变目标函数。与变量 y y y 对应的列在原始问题中作为静态列而不是生成的列。也就是说它们在列生成之前引入。这确保了在任何列生成迭代中相应的受限主问题的最优性下计算的对偶乘子都满足添加的约束集合 E T π ≤ e E^T \pi \le e ETπ≤e。因此这可以看作一种预处理技术。但是它也可以动态地实现即在每个列生成迭代结束时选择要添加的不等式还可以消除冗余的对偶不等式使主问题求解更加高效。这些策略都是有用的特别是当在一个非常大的集合中难以选择最佳不等式时。
直观而言对偶最优不等式越紧列生成求解过程就越高效。
实际上这是因为不等式限制了可能的对偶值的集合并且对偶空间中的震荡在幅度和频率上都减小了。在最优乘子周围只生成相关的对偶割平面以更快速地描述拉格朗日对偶函数的下包络。因此不会生成无用的列。
从原始的观点来看我们已经知道这个公式是松弛的。另外这些静态列可能具有使求解过程更有效的特殊结构。当这些列允许考虑许多不需要显式生成的列时就会出现这种情况见第四节。 P , D , P ~ P,D,\tilde{P} P,D,P~ 和 D ~ \tilde{D} D~ 的最优解分别由 x ∗ , π ∗ , ( x ~ ∗ , y ∗ ) x^*,\pi^*,(\tilde{x}^*,y^*) x∗,π∗,(x~∗,y∗) 和 π ~ ∗ \tilde{\pi}^* π~∗ 表示。下面的命题给出了当 E T π ≤ e E^T \pi \le e ETπ≤e 为对偶最优不等式时原问题和修正问题的最优值之间的明显关系。 命题1如果 D ∗ ∩ { π : E T π ≤ e } ≠ ∅ D^* \cap \{\pi : E^T \pi \le e\} \neq \varnothing D∗∩{π:ETπ≤e}∅则 v ( ~ P ) v ( D ~ ) v ( D ) v ( P ) v(\tilde{}P)v(\tilde{D}) v(D) v(P) v(~P)v(D~)v(D)v(P)并且 D ~ \tilde{D} D~ 的任意最优解 π ∗ \pi^* π∗ 也是 D D D 的最优解。 命题2令 ( x ~ ∗ , y ∗ ) (\tilde{x}^*,y^*) (x~∗,y∗) 是 P ~ \tilde{P} P~ 的一个最优解然后假设 E T π ≤ e E^T \pi \le e ETπ≤e 是对偶最优不等式的一个集合。因此当 E y ∗ 0 Ey^* 0 Ey∗0 时 x ~ ∗ \tilde{x}^* x~∗ 是 P P P 的一个最优解。令 π ~ ∗ \tilde{\pi}^* π~∗ 是 D ~ \tilde{D} D~ 的一个最优解。尽管 π ~ ∗ \tilde{\pi}^* π~∗ 是 D D D 的一个对偶最优解但当 E y ∗ ≠ 0 Ey^* \neq 0 Ey∗0 时 x ~ ∗ \tilde{x}^* x~∗ 对于 P P P 是不可行的因为 A x ~ ∗ ≠ b A\tilde{x}^* \neq b Ax~∗b。 因此从上面的证明可以得出当 x ~ ∗ \tilde{x}^* x~∗ 对于 P P P 可行时 e T y ∗ 0 e^Ty^* 0 eTy∗0。 三、确定P的最优原始解
令 ( x ~ ∗ , y ∗ ) (\tilde{x}^*,y^*) (x~∗,y∗) 是 P ~ \tilde{P} P~ 的一个最优解 π ~ ∗ \tilde{\pi}^* π~∗ 是 D ~ \tilde{D} D~ 的一个最优解。当 E y ∗ ≠ 0 Ey^* \neq 0 Ey∗0 时 x ~ ∗ \tilde{x}^* x~∗ 对于 P P P 不可行因为 A x ~ ∗ ≠ b A \tilde{x}^* \neq b Ax~∗b。
由于我们的目标是获取 P P P 的最优解因此我们需要一种有效的方法来恢复给定原问题 P ~ \tilde{P} P~ 和对偶问题 D ~ \tilde{D} D~的原始最优性。
接下来我们考虑添加的对偶不等式或相应的原始列具有特殊解释的情况允许从 x ~ ∗ \tilde{x}^* x~∗ 建立 P P P 的最优解。 命题3假设 P ~ \tilde{P} P~ 的任意一个可行解为 ( x ~ , y ) (\tilde{x},y) (x~,y)它有可能为 P P P 建立一个可行解使得 c T x ≤ c T x ~ e T y c^Tx \le c^T\tilde{x} e^Ty cTx≤cTx~eTy。然后对于任意 P ~ \tilde{P} P~ 的最优解 ( x ~ ∗ , y ∗ ) (\tilde{x}^*,y^*) (x~∗,y∗)对应的解 x ~ ∗ \tilde{x}^* x~∗ 就是 P P P 的最优解。 这种情况发生在稍后考虑的切割下料应用中。然而当情况并非如此时需要一种有效的方法来恢复 P P P 的最优解。该过程取决于所使用的对偶不等式的类型。
假设 E T π ≤ e E^T\pi \le e ETπ≤e 是对偶最优不等式的一个集合。通过求解一个稍微修改的问题 P ~ ε \tilde{P}_\varepsilon P~ε对应的对偶问题为 D ~ ε \tilde{D}_\varepsilon D~ε可以得到 P P P 的最优解。给定一个标量向量 ε 0 \varepsilon 0 ε0我们用 E T π ≤ e ε E^T\pi \le e\varepsilon ETπ≤eε 替换 P ~ \tilde{P} P~ 和 D ~ \tilde{D} D~ 定义中的 E T π ≤ e E^T\pi \le e ETπ≤e 命题4令 ( x ~ ε ∗ , y ε ∗ ) (\tilde{x}^*_\varepsilon,y^*_\varepsilon) (x~ε∗,yε∗) 是 P ~ ε \tilde{P}_\varepsilon P~ε 的一个最优解则 y ε ∗ 0 y^*_\varepsilon0 yε∗0且 x ~ ε ∗ \tilde{x}^*_\varepsilon x~ε∗ 是 P P P 的一个最优解。 标量向量 ε \varepsilon ε 必须足够小以保证应用于 P ~ ε \tilde{P}_\varepsilon P~ε 的列生成的效率。另外太小的值可能也会导致数值困难和对偶不等式集无效这取决于现有线性规划求解器使用的参数的准确性。
现在假设 E T π ≤ e E^T \pi \le e ETπ≤e 是深度对偶最优不等式的一个集合。给定 D ~ \tilde{D} D~ 的对偶最优解为 π ~ ∗ \tilde{\pi}^* π~∗ 和一个标量向量 Δ 0 \varDelta 0 Δ0定义稳定的原问题 P ˉ ( π ~ ∗ ) \bar{P}(\tilde{\pi}^*) Pˉ(π~∗) 和对偶问题 D ˉ ( π ~ ∗ ) \bar{D}(\tilde{\pi}^*) Dˉ(π~∗) 如下 稳定的对偶问题 D ˉ ( π ~ ∗ ) \bar{D}(\tilde{\pi}^*) Dˉ(π~∗) 被构造为对偶解被限制在一个严格包含 D ~ \tilde{D} D~ 的最优解 π ~ ∗ \tilde{\pi}^* π~∗ 的非空盒子中该最优解确实是 D D D 的最优解根据命题1。利用非负冗余变量 y 1 y_1 y1 和松弛变量 y 2 y_2 y2给出了相应的稳定的原始问题 P ˉ ( π ~ ∗ ) \bar{P}(\tilde{\pi}^*) Pˉ(π~∗) 的定义。
给出 E T π ≤ e E^T \pi \le e ETπ≤e 为深度对偶最优不等式的一个集合则 P P P 的一个最优原始解可以通过一个两阶段的方法获得。首先我们求解 P ~ \tilde{P} P~ 获得一个 D D D 的对偶最优解 π ~ ∗ \tilde{\pi}^* π~∗。其次我们求解稳定的原始问题 P ˉ ( π ~ ∗ ) \bar{P}(\tilde{\pi}^*) Pˉ(π~∗)。下面的命题表明第二阶段的解就是 P P P 的最优解。 命题5令 E T π ≤ e E^T \pi \le e ETπ≤e 是一个深度对偶最优不等式的集合 ( x ˉ ∗ , y 1 ∗ , y 2 ∗ ) (\bar{x}^*,y_1^*,y_2^*) (xˉ∗,y1∗,y2∗) 是 P ˉ ( π ~ ∗ ) \bar{P}(\tilde{\pi}^*) Pˉ(π~∗) 的一个原始最优解。则 x ˉ ∗ \bar{x}^* xˉ∗ 是 P P P 的一个原始最优解。 注意上面的证明并不依赖于 D ˉ ( π ~ ∗ ) \bar{D}(\tilde{\pi}^*) Dˉ(π~∗) 的实际对偶最优解即 π ˉ ∗ \bar{\pi}^* πˉ∗ 可能等于也可能不等于 π ~ ∗ \tilde{\pi}^* π~∗ 。首先用列生成求解松弛原问题 P ~ \tilde{P} P~ 得到 π ~ ∗ \tilde{\pi}^* π~∗ 的效率主要取决于对偶不等式的紧密性。对于第二阶段即 P ˉ ( π ~ ∗ ) \bar{P}(\tilde{\pi}^*) Pˉ(π~∗) 的解当用严格包含对偶最优解的小框初始化时赞成列生成的效率参见第五节。通过使用在求解 P P P 时已经生成的列这种效率更有可能得到加强。 四、二元切割下料问题
给定一组宽度为 L L L 的卷和一组物品集合 I { 1 , 2 , . . . , m } I\{1,2,...,m\} I{1,2,...,m}其中每个物品 i ∈ I i \in I i∈I 具有长度 w i w_i wi 和单位需求。二元切割下料问题BCS的目的是找到满足需求的一组切割模式同时最小化所使用的卷的数量。
可行的切割模式是一个子集 C ⊂ I C \subset I C⊂I 使得 ∑ i ∈ C w i ≤ L \sum_{i\in C}{w_i} \le L ∑i∈Cwi≤L。令 Ω \Omega Ω 为所有可行切割模式的集合。广为人知的公式Gilmore 和 Gomory 1961使用二元变量 如果在解决方案中使用了切割模式 p p p 则 x p 1 x_p1 xp1否则 x p 0 x_p0 xp0。
我们感兴趣的是解这个问题的线性松弛。分别考虑以下原始和对偶线性规划公式 P B C S P_{BCS} PBCS 和 D B C S D_{BCS} DBCS其中二元系数 a i p a_{ip} aip 表示模式 p p p 中是否使用了物品 i i i 原始问题是通过列生成求解的。事实上二元切割下料问题也可以模拟为一个车辆路径问题其中车辆和它们的容量分别对用于要切成小块的大卷和它们的宽度。这些模式是通过求解带时间窗的最短路径问题的一种特殊情况0-1背包问题得到的。
在作者的例子中它是在一个无环图上表述的每个节点上都有一个容量窗口并通过动态规划求解。
物品大小为整数的大型装箱实例BCS往往有几个相同大小的物品这些物品最好被一个需求等于重复数量的单一物品取代。这种聚合相当于要求相同长度的项对应的对偶变量相等。下面的命题强调了这一点它表明这些条件确实是深度对偶最优不等式。结果还表明对于 BCS 聚合保留了相同的线性规划界。 命题6对于任意二元切割下料问题的两个物品 i i i 和 j j j 如果 w i w j w_iw_j wiwj 则 D B C S D_{BCS} DBCS 存在一个对偶最优解满足 π i ∗ π j ∗ \pi^*_i \pi^*_j πi∗πj∗ 。 作者测试了两种不同的方式来施加这些对偶约束
在原始公式中相同项目的约束聚合在对偶公式中显式添加相等约束
每种方法对问题的大小和结构有不同的影响。我们分别处理它们。
4.1 约束聚合
相同大小的物品对应的需求约束聚合为一个约束其右侧需求大于1。因此一个可行的模式可能会被使用不止一次一个项目可能会出现不止一次。
4.2 相等约束
对物品集合按照大小降序排序对于每个物品对 ( i , i 1 ) (i,i1) (i,i1)如果 w i w i 1 w_i w_{i1} wiwi1 则在 D ~ B C S \tilde{D}_{BCS} D~BCS 中添加相等约束 − π i π i 1 0 -\pi_i \pi_{i1} 0 −πiπi10。这将导致在 P ~ B C S \tilde{P}_{BCS} P~BCS 中添加相应的零成本变量 y i , i 1 y_{i,i1} yi,i1 在第 i i i 行其系数为 -1在第 i 1 i1 i1 行其系数为 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}) L150,m∈{500,1000},lmin∈{1,20},lmax100,(wi)i∈I∼U(lmin,lmax) 的四类均匀生成问题(u-problem)
还有一类三联问题(t-problem)其中每个卷被切成恰好三阶而不丢失包含 m 501 m 501 m501 个项目。物品长度都相对接近于 L / 3 L/3 L/3 并且(整数和连续的)最优掷出次数为 m / 3 m/3 m/3 。为每个类生成十个实例并计算每个类的平均值。
表1给出了使用标准列生成、项目约束聚合和添加相等约束为每个类获得的结果。 L r ( s ) Lr (s) Lr(s)、 m p ( s ) mp(s) mp(s) 和 s p ( s ) sp(s) sp(s) 分别给出了用于解决线性松弛、主问题和子问题的CPU时间(以秒为单位)(其中 L r ( s ) m p ( s ) s p ( s ) Lr (s) mp(s) sp(s) Lr(s)mp(s)sp(s) ) i t r itr itr 是达到最优性所需的列生成迭代次数 % i t r \% itr %itr 是列生成迭代次数的相对改进。
由于子问题是通过动态规划作为约束最短路径问题来解决的因此在最优状态下可以使用许多负的降低成本列。因此在每个列生成迭代中生成几个列。值得注意的是这两种方法使用相同的列生成器这并不影响它们之间的比较。 五、切割下料问题
切割下料问题CSP和二元切割下料问题相似不同之处在于要求 b i b_i bi 为一般正整数。因此一个项目可以在一个可行的切割模式中出现不止一次。将子问题中的背包约束替换为 Gilmore and Gomory(1961)也表明需求约束中的等号可以用大号或等号代替并且通过这种简单的转换列生成求解过程略有加快。线性松弛 P C S P_{CS} PCS 及其对偶 D C S D_{CS} DCS 的公式如下 根据Gilmore和Gomory提出的变换对偶变量只能取非负值。因此 π i ≥ 0 , i ∈ I \pi_i \ge 0 , i\in I πi≥0,i∈I 是一组对偶最优不等式。
现在讨论Valerio de Carvalho (2005b)引入的对偶子集不等式。利用命题3作者证明了这样一个事实即有可能在给定修改的原始问题的最优解的情况下重建原始最优解从而证明了这些切割的使用。在本文中作者证明了这些对偶切割实际上是切料问题的对偶最优不等式 命题7对于每个物品 i i i 和 子集 S ⊂ I S\subset I S⊂I D C S D_{CS} DCS 的任意一个最优解满足 w i ≥ ∑ l ∈ S w l π i ∗ ≥ ∑ l ∈ S π l ∗ w_i \ge \sum_{l \in S}{w_l} \pi_i^* \ge \sum_{l\in S}{\pi^*_l} wi≥∑l∈Swlπi∗≥∑l∈Sπl∗ 当 ∣ S ∣ 1 |S|1 ∣S∣1 时这些子集不等式有一个有趣的解释。 D D D 的任意最优解都满足排序 此外将这个结果应用于相同长度的两个项目 i i i 和 j j j我们得到 D C S D_{CS} DCS 的所有对偶最优解都满足 w i w j π i ∗ π j ∗ w_i w_j \pi^*_i\pi^*_j wiwjπi∗πj∗ 。
然而这并不适用于二元切割下料问题因为在生成二元切割模式时存在一个隐含的约束即一个项目不能切割超过一次而对于经典的所谓切割下料问题一个项目可能被切割任意整数次而与该项目的需求无关。 例子考虑一个二元切割下料问题其中 m 2 , w 1 4 , w 2 4 , W 10 m2,w_14,w_24,W10 m2,w14,w24,W10 并且需求都为1。它只有三种可行的二元模式 { [ w 1 , w 2 ] , [ w 1 ] , [ w 2 ] } \{[w_1,w_2],[w_1],[w_2]\} {[w1,w2],[w1],[w2]}对应的非负原始变量为 x 1 , x 2 , x 3 x_1,x_2,x_3 x1,x2,x3。对偶域定义为 很容易验证对偶点 ( 1 , 0 ) (1,0) (1,0) 和 ( 0 , 1 ) (0,1) (0,1) 是与原最优解 x 1 1 , x 2 x 3 0 x_11,x_2x_30 x11,x2x30 对应的对偶最优解即使这些对偶解不满足 π 1 π 2 \pi_1\pi_2 π1π2 w 1 w 2 w_1w_2 w1w2。的确命题6只是规定存在一个使 π 1 π 2 \pi_1\pi_2 π1π2 的对偶最优解此处为上述对偶最优解的凸组合。
现在把这个例子看作一个经典的库存问题也就是说我们从模式生成中去掉了二元限制。两种新的模式是可行的 [ w 1 , w 1 ] , [ w 2 , w 2 ] [w_1,w_1],[w_2,w_2] [w1,w1],[w2,w2]。这些用两个新的约束修改了对偶空间 2 π 1 ≤ 1 2\pi_1 \le 1 2π1≤1 和 2 π 2 ≤ 1 2\pi_2 \le 1 2π2≤1。唯一的对偶最优解现在是 π 1 π 2 1 / 2 \pi_1\pi_21/2 π1π21/2这是命题7的直接结果其中证明了所有最优解满足 π 1 π 2 \pi_1\pi_2 π1π2。
子集不等式的数量是指数的我们必须选择一个合理的数量来使用。如果 ∣ S ∣ |S| ∣S∣ 是固定的则可能的切割次数是 m m m 的多项式。最简单的情况是 ∣ S ∣ ≤ 2 |S| \le 2 ∣S∣≤2。当 ∣ S ∣ 2 |S|2 ∣S∣2 时可能的对偶约束数为 O ( m 3 ) O(m^3) O(m3)。为了提高效率特别是当 m m m 很大时Valerio de Carvalho (2005b) 对每个 i ∈ I i\in I i∈I 只使用了一个对偶约束(如果有的话)。这个不等式是使用最小的索引 j j j ( 对应最大的宽度 w j w_j wj ) 生成的如果存在这样的值那么存在 k k k使得 w i ≥ w j w k w_i \ge w_j w_k wi≥wjwk。这将会导致向 D ~ C S \tilde{D}_{CS} D~CS 中添加 O ( m ) O(m) O(m) 个约束并向原始问题 P ~ C S \tilde{P}_{CS} P~CS 中添加列。
添加到原始问题的列具有特殊的含义。引入零成本变量 y i , S y_{i,S} yi,S 的系数为 -1(row i i i)1row l ∈ S l\in S l∈S和 0其他行。这允许原始问题在包含 i i i 的任何可行模式中用 S S S 的项替换项目 i i i 。
因此包含 i i i 的切割模式的存在以及变量 y i , S y_{i,S} yi,S 对应的列的存在隐式地保证了所有地可行切割模式的存在其中 i i i 被集合 S S S 中的项所取代因此不需要生成这些列。这种推理可以递归地应用于 S S S 中的某些项因此也隐含地考虑了一些具有 ∣ S ∣ ≥ 3 |S|\ge 3 ∣S∣≥3 的子集不等式。
最后上述段落给出了一种直接的方法来重建一个原始最优解。对于任何覆盖项 i i i 覆盖模式必须通过将 i i i 替换为 S S S 中 y i , S 0 y_{i,S}0 yi,S0 的项来修改。
5.1 计算结果 六、三元组的深度对偶最优不等式Deep Dual-Optimal Inequalities for the Triplet
t问题中的三元组是这样构建的在最优状态下损失为零。表2显示了给定它们的大小这些问题相当困难并且需要非常多的列生成迭代。然而对于没有损失的 P C S P_{CS} PCS 实例有一个非常有趣的结果。事实上从物品的长度可以直接计算出最优掷出次数即所有物品的总长度除以 L L L 而且还可以得到对偶最优解 命题8考虑一个没有损失的 P C S P_{CS} PCS 实例则 π i ∗ w i / L \pi^*_i w_i /L πi∗wi/L 是一个对偶最优解。 如命题5给定已知的对偶最优解 π ~ ∗ \tilde{\pi}^* π~∗ 可以使用以下深度对偶最优不等式 π ~ ∗ − Δ ≤ π ≤ π ~ ∗ Δ \tilde{\pi}^* - \varDelta \le \pi \le \tilde{\pi}^* \varDelta π~∗−Δ≤π≤π~∗Δ 其中 Δ 0 \varDelta 0 Δ0是一个小的标量向量。这些框不等式限制了所有列生成迭代期间的对偶值。注意到使用松弛变量 y 2 b y_2b y2b 已经可以获得基本解并且对于相应的基单位矩阵对偶乘数对于 Δ \varDelta Δ 几乎是最优的并且取值 ( π ~ ∗ Δ ) (\tilde{\pi}^* \varDelta) (π~∗Δ)从而加速了问题 P ˉ ( π ~ ∗ ) \bar{P}(\tilde{\pi}^*) Pˉ(π~∗) 的解决。
6.1 计算结果 七、总结
本文讨论了对偶信息对列生成效率的作用。对偶最优不等式不会切割任何对偶最优解而深度的对偶最优解可能会移除其中的一个非空子集。
这些不等式的使用限制了对偶空间同时放宽了原始可行集。从而限制了对偶乘子可能的中间值集合更快地得到对偶最优解。然而原始可行性可能会丢失需要恢复原始最优解。在某些情况下对偶不等式对于当前的应用具有特殊的意义并且可以在给定修正问题的解的情况下建立原始最优解。当这是不可能的时候作者提出了两种一般的方法来恢复原始的可行性和最优性每一种都针对一个类型的不等式。
众所周知用于二进制切割下料问题的聚合技术可以看作是实现一组深度对偶最优不等式的隐式方法。这种隐式方法大大减少了行数因此无法确定对偶不等式的实际影响。因此作者测试了这些对偶约束的显式实现结果是在不改变行数的情况下增加了原始变量的数量。我们在减少列生成迭代数方面也观察到同样的改善这证实了相关对偶信息的重要性。
对于切割下料问题作者证明了Valerio de Carvalho (2005b)引入的子集不等式可以加速列的生成。
作者还表明当使用由易于计算的对偶最优解导出的对偶最优盒不等式求解三元组实例时通常被认为是困难的切料实例实际上非常容易。
计算结果再次表明显著的对偶信息明显有利于列生成求解过程。一个类似的程序已经被提出用于设计线性规划的有效交叉方法(Ben Amor et al . 2006)。给定由内点算法提供的最优内原解和对偶最优解 π ∗ \pi^* π∗用单纯形算法重新求解原问题同时在对偶公式加入小的对偶盒不等式(如 π ∗ ± 1 0 − 3 \pi^* ±10^{-3} π∗±10−3 )。这个简单的程序是非常稳定和相当快的。
最后切割下料问题是一个结构良好的优化问题但许多其他组合优化问题也具有良好的结构。对于切割下料问题的结果表明寻找其他组合问题的对偶最优解的更好的表征是有意义的。
