• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE International Parallel and Distributed Processing Symposium Workshops >An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ugSCIP-*,*-Libraries
【24h】

An Easy Way to Build Parallel State-of-the-art Combinatorial Optimization Problem Solvers: A Computational Study on Solving Steiner Tree Problems and Mixed Integer Semidefinite Programs by using ugSCIP-*,*-Libraries

机译：建立并行的最新组合优化问题求解器的简便方法：使用ug SCIP-*，*-Library解决Steiner树问题和混合整数半定程序的计算研究

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Branch-and-bound (B&B) is an algorithmic framework for solving NP-hard combinatorial optimization problems. Although several well-designed software frameworks for parallel B&B have been developed over the last two decades, there is very few literature about successfully solving previously intractable combinatorial optimization problem instances to optimality by using such frameworks. The main reason for this limited impact of parallel solvers is that the algorithmic improvements for specific problem types are significantly greater than performance gains obtained by parallelization in general. Therefore, in order to solve hard problem instances for the first time, one needs to accelerate state-of-the-art algorithm implementations. In this paper, we present a computational study for solving Steiner tree problems and mixed integer semidefinite programs in parallel. These state-of-the-art algorithm implementations are based on SCIP and were parallelized via the ug[SCIP-*,*]-libraries-by adding less than 200 lines of glue code. Despite the ease of their parallelization, these solvers have the potential to solve previously intractable instances. In this paper, we demonstrate the convenience of such a parallelization and present results for previously unsolvable instances from the well-known PUC benchmark set, widely regarded as the most difficult Steiner tree test set in the literature.
机译：分支定界（B＆B）是用于解决NP困难组合优化问题的算法框架。尽管在过去的二十年中已经开发了几种针对并行B＆B的精心设计的软件框架，但是很少有文献使用这种框架成功地解决了以前棘手的组合优化问题实例的最优性。并行求解器影响有限的主要原因是，针对特定问题类型的算法改进通常明显大于通过并行化获得的性能提升。因此，为了第一次解决难题实例，需要加速最新算法的实现。在本文中，我们提出了用于并行解决Steiner树问题和混合整数半定程序的计算研究。这些最新的算法实现基于SCIP，并通过添加少于200行的粘合代码，通过ug [SCIP-*，*]-库进行了并行化。尽管它们的并行化很容易，但这些求解器仍具有解决以前难以处理的实例的潜力。在本文中，我们演示了这种并行化的便利性，并针对众所周知的PUC基准测试集（以前被认为是文献中最困难的Steiner树测试集）提供了先前无法解决的实例的结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号