• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >0-1 reformulations of the multicommodity capacitated network design problem
【24h】

0-1 reformulations of the multicommodity capacitated network design problem

机译：0-1重新设计了多商品电容网络设计问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study 0-1 reformulations of the multicommodity capacitated network design problem, which is usually modeled with general integer variables to represent design decisions on the number of facilities to install on each arc of the network. The reformulations are based on the multiple choice model, a generic approach to represent piecewise linear costs using 0-1 variables. This model is improved by the addition of extended linking inequalities, derived from variable disaggregation techniques. We show that these extended linking inequalities for the 0-1 model are equivalent to the residual capacity inequalities, a class of valid inequalities derived for the model with general integer variables. In this paper, we compare two cutting-plane algorithms to compute the same lower bound on the optimal value of the problem: one based on the generation of residual capacity inequalities within the model with general integer variables, and the other based on the addition of extended linking inequalities to the 0-1 reformulation. To further improve the computational results of the latter approach, we develop a column-and-row generation approach; the resulting algorithm is shown to be competitive with the approach relying on residual capacity inequalities.
机译：我们研究了多商品容量网络设计问题的0-1公式化，该问题通常使用通用整数变量建模，以表示关于在网络的每个弧上安装的设施数量的设计决策。重新制定以多选模型为基础，多选模型是使用0-1变量表示分段线性成本的通用方法。该模型通过添加扩展链不等式而得到改进，该不等式源自变量分解技术。我们表明，对于0-1模型，这些扩展的链接不等式等于剩余容量不等式，这是为带有常规整数变量的模型得出的一类有效不等式。在本文中，我们比较了两种切割平面算法，以计算问题的最佳值的相同下限：一种是基于模型中具有一般整数变量的剩余容量不等式的生成，另一种是基于相加的将不平等联系扩展到0-1重新制定。为了进一步改善后一种方法的计算结果，我们开发了一种行列生成方法。结果表明，与依赖剩余容量不等式的方法相比，所得算法具有竞争力。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号