论文标题
放松的双重最佳不等式的放松柱：应用车辆路由
Relaxed Dual Optimal Inequalities for Relaxed Columns: with Application to Vehicle Routing
论文作者
论文摘要
我们解决了为设定覆盖问题加速列生成的问题，在该问题中，我们放宽了列的状态空间以进行有效的定价。我们通过调整最近引入的光滑和柔性双重最佳不等式（DOI）来实现这一目标，以与放松的柱一起使用。平滑的DOI利用了类似项目几乎可及格的观察结果，因此应与相似的双重变量相关。灵活的DOI利用了这样的观察，即可以通过删除项目诱导的柱子的成本变化可以界定。在NG-Route放松的背景下，我们将这些DOI适应了电容车辆路由的问题。我们在基准数据集上显示出明显的速度，而事实证明并不削弱放松。
We address the problem of accelerating column generation for set cover problems in which we relax the state space of the columns to do efficient pricing. We achieve this by adapting the recently introduced smooth and flexible dual optimal inequalities (DOI) for use with relaxed columns. Smooth DOI exploit the observation that similar items are nearly fungible, and hence should be associated with similarly valued dual variables. Flexible DOI exploit the observation that the change in cost of a column induced by removing an item can be bounded. We adapt these DOI to the problem of capacitated vehicle routing in the context of ng-route relaxations. We demonstrate significant speed ups on a benchmark data set, while provably not weakening the relaxation.
