检索结果-内蒙古大学图书馆

A parallel branch and bound algorithm for the maximum labelled clique problem

OPTIMIZATION LETTERS 2015年第5期9卷 949-960页

作者： McCreesh, Ciaran Prosser, Patrick Univ Glasgow Glasgow Lanark Scotland

The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.

关键词： Maximum labelled clique parallel branch and bound Combinatorial optimisation Computational experiments

来源：评论

学校读者我要写书评

暂无评论

branch and bound Algorithm for parallel Many-Core Architecture 6

Branch and Bound Algorithm for Parallel Many-Core Architectu...

引用

6th International Symposium on Computing and Networking (CANDAR) - Across Practical Development and Theoretical Research

作者： Hazama, Kazuki Ebara, Hiroyuki Kansai Univ GS Sci & Engn Suita Osaka Japan

ISBN: (纸本)9781538691847

In recent years, computer environment using multiple processors such as multi-core and many-core device attracts attention due to the limit of performance improvement per processor. In this paper, we propose a new algorithm for the combinatorial optimization problem using a parallel search method called LazySMP to efficiently use many-core processors. LazySMP is a method based on the iterative deepening depthfirst search, which is used for board searching of chess and shogi software. In this method, the search results are saved in a table that all processes can share, and the results are used in the search of other processes to shorten the search time. In the proposed method, LazySMP is applied to the branch and bound method. Specifically, it performs a branch and bound method that iteratively deepens in all threads and save a part of the result of some nodes in the shared hash table. Then, when it performs the subsequent searches, the hash table is referred to instead of researching the nodes. Our aim is to make efficient use of many-core processors. We make computer experiments with the traveling salesman problem as the benchmark in order to verify the performance of the proposed method.

关键词： Combinatorial optimization problem Many-core processors parallel branch and bound LazySMP Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

parallel PIPS-SBB: multi-level parallelism for stochastic mixed-integer programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2019年第2期73卷 575-601页

作者： Munguia, Lluis-Miquel Oxberry, Geoffrey Rajan, Deepak Shinano, Yuji Georgia Inst Technol Coll Comp Atlanta GA 30332 USA Lawrence Livermore Natl Lab Computat Engn Div Livermore CA 94550 USA Zuse Inst Berlin Dept Optimizat Takustr 7 D-14195 Berlin Germany

PIPS-SBB is a distributed-memory parallel solver with a scalable data distribution paradigm. It is designed to solve mixed integer programs (MIPs) with a dual-block angular structure, which is characteristic of deterministic-equivalent stochastic mixed-integer programs. In this paper, we present two different parallelizations of branch & bound (B&B), implementing both as extensions of PIPS-SBB, thus adding an additional layer of parallelism. In the first of the proposed frameworks, PIPS-PSBB, the coordination and load-balancing of the different optimization workers is done in a decentralized fashion. This new framework is designed to ensure all available cores are processing the most promising parts of the B&B tree. The second, ug[PIPS-SBB,MPI], is a parallel implementation using the Ubiquity Generator, a universal framework for parallelizing B&B tree search that has been sucessfully applied to other MIP solvers. We show the effects of leveraging multiple levels of parallelism in potentially improving scaling performance beyond thousands of cores.

关键词： MIPs Stochastic MIPs parallel algorithms parallel branch and bound

来源：评论

学校读者我要写书评

暂无评论

The single machine total weighted completion time scheduling problem with the sum-of-processing time based models: Strongly NP-hard

引用

APPLIED MATHEMATICAL MODELLING 2017年 50卷 314-332页

作者： Rudek, Radoslaw Wroclaw Univ Econ Komandorska 118-120 PL-53345 Wroclaw Poland

Although the single machine scheduling problem to minimize the total weighted completion times with the sum-of-processing time based learning or aging effects have been known for a decade, it is still an open question whether these problems are strongly NP hard. We resolve this issue and prove them to be strongly NP-hard with the learning effect as well as with the aging effect. Furthermore, we construct an exact parallel branch and bound algorithm for the problem with general sum-of-processing time based models, which can solve optimally moderate problem instances in reasonable time. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Scheduling Learning effect Aging effect Computational complexity Strongly NP-hard parallel branch and bound

来源：评论

学校读者我要写书评

暂无评论

branching and bounding improvements for global optimization algorithms with Lipschitz continuity properties

引用

JOURNAL OF GLOBAL OPTIMIZATION 2015年第3期61卷 429-457页

作者： Cartis, Coralia Fowkes, Jaroslav M. Gould, Nicholas I. M. Univ Edinburgh Sch Math Kings Bldg Edinburgh EH9 3JZ Midlothian Scotland Rutherford Appleton Lab Computat Sci & Engn Dept Chilton OX11 0QX Oxon England

We present improvements to branch and bound techniques for globally optimizing functions with Lipschitz continuity properties by developing novel bounding procedures and parallelisation strategies. The bounding procedures involve nonconvex quadratic or cubic lower bounds on the objective and use estimates of the spectrum of the Hessian or derivative tensor, respectively. As the nonconvex lower bounds are only tractable if solved over Euclidean balls, we implement them in the context of a recent branch and bound algorithm (Fowkes et al. in J Glob Optim 56:1791-1815, 2013) that uses overlapping balls. Compared to the rectangular tessellations of traditional branch and bound, overlapping ball coverings result in an increased number of subproblems that need to be solved and hence makes the need for their parallelization even more stringent and challenging. We develop parallel variants based on both data- and task-parallel paradigms, which we test on an HPC cluster on standard test problems with promising results.

关键词： Global optimization Lipschitzian optimization parallel branch and bound Nonconvex programming

来源：评论

学校读者我要写书评

暂无评论

P2P design and implementation of a parallel branch and bound algorithm for grids

引用

INTERNATIONAL JOURNAL OF GRID AND UTILITY COMPUTING 2009年第2期1卷 159-168页

作者： Bendjoudi, Ahcene Melab, Nouredine Talbi, El-Ghazali Sci & Tech CERIST Ctr Rech Informat DTSI Algiers Algeria Univ Abderrahmane Mira Bejaia Algeria Univ Sci & Technol Lille LIFL UMR CNRS 8022 INRIA Lille Nord Europe DOLPHIN F-59655 Villeneuve Dascq France

Solving optimally large instances of combinatorial optimisation problems using branch and bound (B&B) algorithms is CPU-time intensive and requires a large number of computational resources. To harness such huge amount of resources Peer-to-Peer (P2P) communications must be allowed between resources, and adaptive load balancing and fault-tolerance have to be dealt with when designing and implementing a B&B algorithm. In this paper, we propose a P2P design and implementation of a parallel B&B algorithm on top of the ProActive grid middleware. Load distribution and fault-tolerance strategies are proposed to deal with the dynamic and heterogeneous characteristics of the computational grid. The approach has been promisingly applied to the Flow-Shop scheduling problem and experimented on a computational pool of 1500 CPUs from the GRID'5000 Nation-wide experimental Grid.

关键词： combinatorial optimisation permutation flow-shop problem parallel branch and bound peer-to-peer computing ProActive

来源：评论

学校读者我要写书评

暂无评论

FTH-B&B: A Fault-Tolerant Hierarchical branch and bound for Large Scale Unreliable Environments

引用

IEEE TRANSACTIONS ON COMPUTERS 2014年第9期63卷 2302-2315页

作者： Bendjoudi, Ahcene Melab, Nouredine Talbi, El-Ghazali CERIST Res Ctr Algiers 16030 Algeria Univ Abderrahmane Mira de Bejaia Bejaia 06000 Algeria Univ Lille 1 CNRS UMR 8022 LIFL F-59655 Villeneuve Dascq France

Solving to optimality large instances of combinatorial optimization problems using Brand and bound (B&B) algorithms requires a huge amount of computing resources. In this paper, we investigate the design and implementation of such algorithms on computational grids. Most of existing grid-based B&B algorithms are based on the Master-Worker paradigm, their scalability is therefore limited. In addition, even if the volatility of resources is a major issue in grids fault tolerance is rarely addressed in these works. We thereby propose FTH-B&B, a fault tolerant hierarchical B&B. FTH-B&B is based on different new mechanisms enabling to efficiently build and maintain balanced the hierarchy, and to store and recover work units (sub-problems). FTH-B&B has been implemented on top of the ProActive grid middleware and programming environment and applied to the Flow-Shop scheduling problem. Very often, the validation of existing grid-based B&B works is performed either through simulation or a very small real grid. In this paper, we experimented FTH-B&B on the Grid'5000 real French nation-wide computational grid using up to 1,900 processor cores distributed over six sites. The reported results show that the overhead induced by the proposed mechanisms is very low and an efficiency close to 100 percent can be achieved on some Taillards benchmarks of the Flow-Shop problem. In addition, the results demonstrate the robustness of the proposed mechanisms even in extreme failure situations.

关键词： Fault tolerance hierarchical master-worker grid computing parallel branch and bound large scale experiments

来源：评论

学校读者我要写书评

暂无评论

Multi-Threading a State-of-the-Art Maximum Clique Algorithm

引用

ALGORITHMS 2013年第4期6卷 618-635页

作者： McCreesh, Ciaran Prosser, Patrick Univ Glasgow Sch Comp Sci Glasgow G12 8QQ Lanark Scotland

We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear... 详细信息

关键词： maximum clique multi-core parallel algorithms parallel branch and bound

来源：评论

学校读者我要写书评

暂无评论

Operator-level GPU-Accelerated branch and bound Algorithms

引用

Procedia Computer Science 2013年 18卷 280-289页

作者： I. Chakroun N. Melab Université Lille 1 LIFL/UMR CNRS 8022 - INRIA Lille Nord Europe 59655 - Villeneuve d’Ascq cedex - France

branch-and-bound (B&B) algorithms are well-known tree-based exploratory methods for solving to optimality NP-hard discrete optimization problems. The construction of the B&B tree and its exploration are performed using four operators: branching, bounding, selection and pruning. Such algorithms are irregular which makes challenging their parallel design and implementation on GPU accelerators. Among the few existing related works, we have recently revisited on GPU the bounding operator. The reported results show that speedups up to × 100 can be obtained on recent GPU cards. In this paper, we address the GPU-based design and implementation of B&B algorithms considering the branching and pruning operators as well as the bounding one. The proposed template transforms the unpredictable and irregular workload associated to the explored B&B tree into regular data-parallel kernels optimized for the SIMD-based execution model of GPUs. Thread divergence and uncoalesced memory accesses are considered in the optimization process. The proposed approach has been experimented on the Flow-Shop scheduling problem and compared to another GPU-based strategy and to a cluster of workstations (COWs) based approach. The reported results demonstrate the efficiency of the proposed approach over the two other ones. Speedups up to × 160 are obtained for large problem instances using an Nvidia Tesla C2050 hardware configuration.

关键词： Irregular algorithms GPU Computing parallel branch and bound Flow-Shop Scheduling Problem.

来源：评论

学校读者我要写书评

暂无评论

Hierarchical branch and bound algorithm for computational grids

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2012年第8期28卷 1168-1176页

作者： Bendjoudi, A. Melab, N. Talbi, E. -G. DTISI Ctr Rech Informat Sci & Tech CER1ST Algiers 16030 Algeria Univ Abderrahmane Mira Bejaia Bejaia 06000 Algeria Univ Lille 1 F-59655 Villeneuve Dascq France CNRS LIFL UMR 8022 F-59655 Villeneuve Dascq France

branch and bound (B&B) algorithms are efficiently used for exact resolution of combinatorial optimization problems (COPs). They are easy to parallelize using the Master/Worker paradigm (MW) but limited in scalability when solving large instances of COPs on large scale environments such as computational grids. Indeed, the master process rapidly becomes a bottleneck. In this paper, we propose a new approach H-B&B for parallel B&B based on a hierarchical MW paradigm in order to deal with the scalability issue of the traditional MW-based B&B. The hierarchy is built dynamically and evolves over time according to the dynamic acquisition of computing nodes. The inner nodes of the hierarchy (masters) perform branching operations to generate sub-trees and the leaves (workers) perform a complete exploration of these sub-trees. Therefore, in addition to the parallel exploration of sub-trees, a parallel branching is adopted. H-B&B is applied to the Flow-Shop scheduling problem. Unlike most existing grid-based B&B algorithms, H-B&B has been experimented on a real computational grid (Grid'5000). The results demonstrate the scalability and efficiency of H-B&B. (C) 2012 Elsevier B.V. All rights reserved.

关键词： parallel branch and bound Master/worker Hierarchical master/worker Grid computing Large scale experiments

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：