论文标题
光滑，灵活的双重最佳不平等现象
Smooth and flexible dual optimal inequalities
论文作者
论文摘要
我们通过双重最佳不等式（DOI）解决了用于设定配方的加速柱生成（CG）的问题。 DOI使用对双重解决方案空间的知识来得出可能因限制的主问题而可能违反的不平等现象，因此有效地减少了迭代次数的数量和列在列生成过程中通常观察到的双重变量的振荡。我们分别研究了两种新型的DOI类，分别称为灵活的DOI（F-DOI）和平滑-DOI（S-DOI）（S-DOI）（并共同称为SF-DOI）。 F-DOI为覆盖物品的折扣提供了更多的回扣。 S-DOI描述了支付罚款，以允许物品覆盖不足，以换取其他物品的过度包含。与文献中的其他类别的DOI类别不同，S-DOI和F-DOI几乎没有依赖于特定问题的知识，因此有可能应用于大量问题域。特别是，我们通过将它们嵌入单个源电容的设施位置问题（SSCFLP）中来说明新不等式的效率。与同一CG程序的非稳定变体相比，可以观察到高达130倍的速度，以实现线性弛豫下的较低限制，这是在具有密集柱和结构化分配成本的问题上。
We address the problem of accelerating column generation (CG) for set-covering formulations via dual optimal inequalities (DOI). DOI use knowledge of the dual solution space to derive inequalities that might be violated by intermediate solutions to a restricted master problem, and as such are efficient at reducing the number of iterations and the oscillations of the dual variables commonly observed in column generation procedures. We study two novel classes of DOI which are referred to as Flexible DOI (F-DOI) and Smooth-DOI (S-DOI), respectively (and jointly as SF-DOI). F-DOI provide rebates for covering items more than necessary. S-DOI describe the payment of a penalty to permit the under-coverage of items in exchange for the over-inclusion of other items. Unlike other classes of DOI from the literature, the S-DOI and F-DOI rely on very little to no problem-specific knowledge, and as such have the potential to be applied to a vast number of problem domains. In particular, we illustrate the efficiency of the new inequalities by embedding them within a column generation solver for the single source capacitated facility location problem (SSCFLP). A speed-up of a factor of up to 130x can be observed as when compared to a non-stabilized variant of the same CG procedure to achieve the linear relaxation lower bound on problems with dense columns and structured assignments costs.
