...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational optimization and applications >Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem
【24h】

Branch-and-cut-and-price algorithms for the Degree Constrained Minimum Spanning Tree Problem

机译：度约束最小生成树问题的分支割价算法

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

摘要

Assume that a connected undirected edge weighted graph G is given. The Degree Constrained Minimum Spanning Tree Problem (DCMSTP) asks for a minimum cost spanning tree of G where vertex degrees do not exceed given pre-defined upper bounds. In this paper, three exact solution algorithms are investigated for the problem. All of them are Branch-and-cut based and rely on the strongest formulation currently available for the problem. Additionally, to speed up the computation of dual bounds, they all use column generation, in one way or another. To test the algorithms, new hard to solve DCMSTP instances are proposed here. These instances, combined with additional ones taken from the literature, are then used in computational experiments. The experiments compare the new algorithms among themselves and also against the best algorithms currently available in the literature. As an outcome of them, one of the new algorithms stands out on top.
机译：假设给出了一个连接的无向边缘加权图G。度约束最小生成树问题（DCMSTP）要求G的最小成本生成树，其中顶点度不超过给定的预定义上限。本文针对该问题研究了三种精确的求解算法。所有这些都是基于分支和剪切的，并且依赖于当前可用于该问题的最强大的公式。另外，为了加快对偶边界的计算，它们都以一种或另一种方式使用列生成。为了测试算法，这里提出了新的难以解决的DCMSTP实例。然后将这些实例与从文献中获取的其他实例结合起来，用于计算实验。实验将新算法相互比较，还与文献中当前可用的最佳算法进行了比较。结果，其中一种新算法脱颖而出。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号