...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >The k-Cardinality Tree Problem: Reformulations and Lagrangian Relaxation
【24h】

The k-Cardinality Tree Problem: Reformulations and Lagrangian Relaxation

机译：k基数树问题：重构和拉格朗日松弛

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

摘要

Given an undirected defining graph for the k-Cardinality Tree Problem (KCTP), an associated directed graph involving two additional vertices is introduced in this paper and gives rise to two compact reformulations of the problem. For the first one, connectivity of feasible solutions is enforced through multicommodity flows while, for the other, lifted Miller-Tucker-Zemlin constraints are used. Comparing the two reformulations, much stronger Linear Programming relaxation bounds are obtained from the first one, albeit at much higher CPU times. However, a Branch-and-Bound algorithm based on the second reformulation proved much more effective and managed to obtain, for the first time, optimality certificates for a large number of KCTP instances from the literature. Additionally, for some instances where optimality could not be proven within the given pre-specified CPU time limit, new best upper bounds were generated. Finally, a Lagrangian heuristic based on the first reformulation was also implemented and proved capable of generating feasible KCTP solutions comparable in quality with the best overall results obtained by metaheuristic based heuristics found in the literature. For our test cases, Lagrangian upper bounds are no more than 3.8% away from the best upper bounds known. Additionally, several new best upper bounds and optimality certificates were obtained by the heuristic. Corresponding Lagrangian heuristic CPU times, however, are typically higher than those associated with their competitors.
机译：给定k基数树问题（KCTP）的无向定义图，本文引入了一个涉及两个附加顶点的关联有向图，并引起了该问题的两个紧凑形式。对于第一个，可行的解决方案的连通性通过多商品流来实现，而对于另一个，则使用了解除的Miller-Tucker-Zemlin约束。比较这两个重新编写的公式，尽管在CPU时间上要高得多，但从第一个公式获得的线性编程弛豫范围要强得多。然而，基于第二种重新制定的分支定界算法被证明更加有效，并且设法从文献中首次获得了针对大量KCTP实例的最优性证书。此外，对于某些无法在给定的预定CPU时间限制内证明最佳性的情况，会生成新的最佳上限。最后，基于第一个重新制定的拉格朗日启发式算法也已实施，并被证明能够生成质量可比的可行KCTP解决方案，而文献中发现的基于元启发式启发式算法的总体效果最佳。对于我们的测试用例，拉格朗日上限与已知的最佳上限相差不超过3.8％。此外，通过启发式方法获得了几个新的最佳上限和最优性证书。但是，相应的拉格朗日启发式CPU时间通常比与其竞争对手相关的时间高。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号