...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>European Journal of Operational Research >Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
【24h】

Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem

机译：SemideFinite编程下限和分支和绑定算法，用于二次最小生成树问题

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

摘要

In this paper, we investigate Semidefinite Programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying Branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new Branch-and-bound algorithms stands out as the new best exact solution approach for the problem. (C) 2019 Elsevier B.V. All rights reserved.
机译：在本文中，我们调查了二次最小生成树问题（QMSTP）的SemideFinite编程（SDP）下限。这里介绍了两个SDP较低的边界方法。适用拉格朗日放松对问题的SDP放松。第一个明确地分为半角异性约束，附着到它是拉格朗日乘法器的正半纤维矩阵。第二依赖于正半纤维矩阵的锥体的半无限重构，并对近似锥体的动态更新的有限一组不等式进行了两种。这些较低的限制程序是两个QMSTP分支和绑定算法的核心成分。我们的计算实验表明，这里计算的SDP边界非常强大，能够在文献中关闭至少70％的最具竞争力的配方的间隙。结果，它们随附的分支和绑定算法具有竞争力的最佳可用QMSTP精确算法。事实上，这些新的分支和绑定算法中的一个突出了作为问题的新的最佳精确解决方法。 （c）2019 Elsevier B.v.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号