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

parallel branch-and-bound methods for the job-shop scheduling problem

ANNALS OF OPERATIONS RESEARCH 1998年第0期83卷 137-160页

作者： Perregaard, M Clausen, J Univ Copenhagen Dept Comp Sci DIKU DK-2100 Copenhagen O Denmark

Job-Shop Scheduling (JSS) problems are among the more difficult to solve in the class of NP-complete problems. The only successful approach has been branch-and-bound based algorithms, but such algorithms depend heavily on good bound functions. Much work has been done to identify such functions for the JSS problem, but with limited success. Even with recent methods, it is still not possible to solve problems substantially larger than 10 machines and 10 jobs. In the current study, we focus on parallel methods for solving JSS problems. We implement two different parallel branch-and-bound algorithms for JSS on a 16-processor MEIKO Computing Surface with Intel i860 processors and perform extensive computational testing using classical publicly available benchmark problems. The parallel part of one of the implementations is based on a similar parallel code for Quadratic Assignment Problems. Results are reported for different branching rules proposed in the literature.

关键词： combinatorial optimization parallel branch-and-bound Job-Shop Scheduling

来源：评论

学校读者我要写书评

暂无评论

parallel branch-and-bound using Private IVM-based Work Stealing on Xeon Phi MIC Coprocessor 13

Parallel Branch-and-Bound using Private IVM-based Work Steal...

引用

International Conference on High Performance Computing and Simulation (HPCS)

作者： Melab, Nouredine Leroy, Rudi Mezmaz, Mohand Tuyttens, Daniel Univ Lille 1 Inria Lille Nord Europe CNRS CRIStAL F-59655 Villeneuve Dascq France Univ Mons Math & OR Dept B-7000 Mons Belgium

ISBN: (纸本)9781467378130

Many combinatorial optimization problems are modeled in practice as permutation-based ones. We have recently proposed a new data structure called IVM dedicated to those problems. IVM is memory efficient in terms of size and management time for solving large permutation problems using branch-and-bound (B&B) algorithm. We believe that those memory properties make IVM well-suited for Many Integrated Cores (MIC) architecture. This paper deals with the parallel design and implementation of the B&B algorithm on MIC architectures using private IVM-based work stealing. The proposed approach has been extensively experimented on an Intel Xeon Phi 5110P using several instances of the Flow-Shop scheduling permutation problem. The reported results show that the IVM-based work stealing approach is about 1 0 times faster than the linked-list traditionally used for parallel B&B.

关键词： parallel branch-and-bound MIC architecture Intel Xeon Phi Permutation problems Flow-Shop Problem

来源：评论

学校读者我要写书评

暂无评论

Adaptive Quality Equalizing: High-performance load balancing for parallel branch-and-bound across applications and computing systems

引用

parallel COMPUTING 2004年第7期30卷 867-881页

作者： Mahapatra, NR Dutt, S Michigan State Univ Dept Elect & Comp Engn E Lansing MI 48824 USA Univ Illinois Dept Elect & Comp Engn Chicago IL 60607 USA

In this paper, we present an adaptive version of our previously proposed quality equalizing (QE) load balancing strategy that attempts to maximize the performance of parallel branch-and-bound (B&B) by adapting to application and target computing system characteristics. Adaptive QE (AQE) incorporates the following salient adaptive features: (1) Anticipatory quantitative and qualitative load balancing mechanisms. (2) Regulation of load information exchange overhead. (3) Deterministic load balancing in extended neighborhoods instead of just immediate neighborhoods as in non-adaptive QE. (4) Randomized global load balancing to fetch work from outside the extended neighborhood. AQE yields speedup improvements of up to 80%, and 15% on the average, compared to that provided by QE for several real-world mixed-integer programming (MIP) problems, and near-ideal speedups for two of the largest problems in the MIPLIB benchmark suite on an IBM SP2 system. (C) 2004 Elsevier B.V. All rights reserved.

关键词： adaptive load balancing best-first search dynamic load balancing granularity mixed-integer programming parallel branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

A difference-of-convex programming approach with parallel branch-and-bound for sentence compression via a hybrid extractive model

引用

OPTIMIZATION LETTERS 2021年第7期15卷 2407-2432页

作者： Niu, Yi-Shuai You, Yu Xu, Wenxu Ding, Wentao Hu, Junpeng Yao, Songquan Shanghai Jiao Tong Univ Sch Math Sci Shanghai Peoples R China Shanghai Jiao Tong Univ SJTU Paristech Elite Inst Technol Shanghai Peoples R China Shanghai Univ Engn Sci Sch Mech & Automot Engn Shanghai Peoples R China

Sentence compression is an important problem in natural language processing with wide applications in text summarization, search engine and human-AI interaction system etc. In this paper, we design a hybrid extractive sentence compression model combining a probability language model and a parse tree language model for compressing sentences by guaranteeing the syntax correctness of the compression results. Our compression model is formulated as an integer linear programming problem, which can be rewritten as a difference-of-convex (DC) programming problem based on the exact penalty technique. We use a well-known efficient DC algorithm-DCA to handle the penalized problem for local optimal solutions. Then a hybrid global optimization algorithm combining DCA with a parallel branch-and-bound framework, namely PDCABB, is used for finding global optimal solutions. Numerical results demonstrate that our sentence compression model can provide excellent compression results evaluated by F-score, and indicate that PDCABB is a promising algorithm for solving our sentence compression model.

关键词： Sentence compression Probabilistic model Parse tree model DCA parallel branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

POSTER: A parallel branch-and-bound Algorithm with History-Based Domination 27

POSTER: A Parallel Branch-and-Bound Algorithm with History-B...

引用

27th ACM SIGPLAN Symposium on Principles and Practice of parallel Programming (PPoPP)

作者： Gonggiatgul, Taspon Shobaki, Ghassan Muyan-Ozcelik, Pinar Calif State Univ Sacramento CA USA

ISBN: (纸本)9781450392044

In this paper, we describe a parallel branch-and-bound (B&B) algorithm with a history-based domination technique, and we apply it to the Sequential Ordering Problem (SOP). To the best of our knowledge, the proposed algorithm is the first parallel B&B algorithm that includes a history-based domination technique and is the first parallel B&B algorithm for solving the SOP using a pure B&B approach. The proposed algorithm takes a pool-based approach and employs a collection of novel techniques that we have developed to achieve effective parallel exploration of the solution space, including parallel history domination, history table memory management, and a thread restart technique. The proposed algorithm was experimentally evaluated using the SOPLIB and TSPLIB benchmarks. The results show that using ten threads with a time limit of one hour on the medium-difficulty instances, the proposed algorithm gives a geometric-mean speedup of 19.9 on SOPLIB and 10.23 on TSPLIB, with super-linear speedups up to 65x seen on 17 instances.

关键词： parallel branch-and-bound sequential ordering problem combinatorial optimization NP-complete problems

来源：评论

学校读者我要写书评

暂无评论

Combining a parallel branch-and-bound Algorithm with a Strong Heuristic to Solve the Sequential Ordering Problem 23

Combining a Parallel Branch-and-Bound Algorithm with a Stron...

引用

52nd International Conference on parallel Processing (ICPP)

作者： Shobaki, Ghassan Gonggiatgul, Taspon Normington, Jacob Muyan-Ozcelik, Pinar Calif State Univ Sacramento Sacramento CA 95819 USA

ISBN: (纸本)9798400708428

In this paper, we describe how to combine a parallel branch-and-bound (B&B) algorithm and a strong heuristic to solve the Sequential Ordering Problem (SOP), which is an NP-hard optimization problem. A parallel B&B algorithm is run in parallel with the Lin-Kernighan-Helsgaun heuristic algorithm, which is known to be one of the strongest heuristic algorithms for solving the SOP. The best solutions found by each algorithm are shared with the other algorithm, and each algorithm benefits from the better solutions found by the other. With the better solutions found by B&B, LKH can find even better solutions. With the better solutions found by LKH, B&B will have a tighter upper bound that enables it to prune at shallower tree nodes and thus complete it search faster. The combined algorithm is evaluated experimentally on the SOPLIB and TSPLIB benchmarks. The results show that the combined algorithm gives significantly better performance than any of the B&B algorithm or the LKH heuristic individually. Significant improvements in both speed and solution quality are seen on both benchmark suites. For example, the proposed algorithm delivers a geometric-mean speedup of 10.17 relative to LKH on the medium-difficulty SOPLIB instances. On the hard SOPLIB instances, it improves the cost by up to 22% relative to B&B and up to 90% relative to LKH

关键词： parallel branch-and-bound Lin-Kernighan-Helsgaun heuristic sequential ordering problem combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Mitigating Anomalies in parallel branch-and-bound Based Algorithms for Mixed-Integer Nonlinear Optimization 7th

Mitigating Anomalies in Parallel Branch-and-Bound Based Algo...

引用

7th International Symposium on Combinatorial Optimization (ISCO)

作者： Palkar, Prashant Mahajan, Ashutosh Univ Augsburg Inst Math D-86159 Augsburg Germany Indian Inst Technol Ind Engn & Operat Res Mumbai 400076 India

ISBN: (纸本)9783031185298;9783031185304

We address detrimental anomalies in parallel versions of two state-of-the-art algorithms for convex mixed-integer nonlinear programs (MINLPs): nonlinear branch-and-bound (NLP-BB) and the LP/NLP based branch-and-bound (QG). A detrimental anomaly is when a parallel algorithm performs worse than its sequential counterpart. Unambiguous node selection functions have been developed in the past to avoid these anomalies. We extend this notion of unambiguity to subroutines for branching and generating linearization cuts. We implement the proposed unambiguous branching and cut generation strategies alongside unambiguous node selection in NLP-BB and QG in the open-source MINLP solver Minotaur. Our computational experiments on convex instances from the MINLPLib library show that detrimental anomalies can be reduced to a great extent in practical algorithms. We also compare these algorithms with opportunistic parallel versions. Our results highlight that opportunistic versions perform better in terms of wall clock times, while the deterministic versions avoid detrimental anomalies with theoretically established guarantees and also provide reproducible results, a feature that is desirable while developing parallel algorithms. We recommend settings in Minotaur that yield opportunistic or deterministic runs for the parallel NLP-BB and QG algorithms.

关键词： Mixed-integer nonlinear programming parallel branch-and-bound Anomalies LP/NLP based branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel branch-and-bound approaches for exact graph edit distance problem

引用

parallel COMPUTING 2022年 114卷

作者： Dabah, Adel Chegrane, Ibrahim Yahiaoui, Said Bendjoudi, Ahcene Nouali-Taboudjemat, Nadia CERIST Res Ctr Sci & Tech Informat Algiers Algeria Univ Sherbrooke Qc Dept Comp Sci CoBIUS Lab Sherbrooke PQ Canada

Graph Edit Distance (GED) is a well-known measure used in the graph matching to measure the similar-ity/dissimilarity between two graphs by computing the minimum cost of edit operations needed to transform one graph into another. This process, Which appears to be simple, is known NP-hard and time consuming since the search space is increasing exponentially. One way to optimally solve this problem is by using branch and bound (B&B) algorithms, Which reduce the computation time required to explore the whole search space by performing an implicit enumeration of the search space instead of an exhaustive one based on a pruning technique. nevertheless, They remain inefficient when dealing with large problem instances due to the impractical running time needed to explore the whole search space. To overcome this issue, We propose in this paper three parallel B&B approaches based on shared memory to exploit the multi-core CPU processors: First, a work-stealing approach where several instances of the B&B algorithm explore a single search tree concurrently achieving speedups up to symbolscript faster than the sequential version. Second, a tree-based approach where multiple parts of the search tree are explored simultaneously by independent B&B instances achieving speedups up to symbolscript Finally, Due to the irregular nature of the GED problem, two load-balancing strategies are proposed to ensure a fair workload between parallel processes achieving impressive speedups up to symbolscript all experiments have been carried out on well-known datasets

关键词： parallel branch-and-bound Graph matching Graph edit distance

来源：评论

学校读者我要写书评

暂无评论

ON THE EFFECTIVENESS OF SYNCHRONOUS parallel branch-and-bound ALGORITHMS

引用

parallel Processing Letters 1995年第3期5卷 375-386页

作者： RICARDO CORRÊA AFONSO FERREIRA LMC — INPG — IMAG 46 av. Félix Viallet 38031 Grenoble Cédex France Partially supported by a CNPq (Brazil) fellowship grant 201421/92-5 (BC). CNRS — LIP — ENS Lyon 46 allée d'Italie 69364 Lyon Cédex 07 France

We theoretically compare the efficiency of two versions, sequential and parallel (synchronous), of the method called branch-and-bound used for searching for an optimal solution in the scope of combinatorial optimization. The sequential version consists of successive decompositions of the original problem in smaller disjoint subproblems and its parallel version consists of a high level parallelization that assumes a shared memory model of parallel computation. Its principle consists of decomposing several subproblems in parallel at each iteration in a synchronous way, and its efficiency is usually defined with respect to its sequential counterpart. In this paper, we redefine the notion of efficiency in such a way that the usefulness of the work done by each processor will be taken into account. The knapsack problem is used as an application and some simulation results are presented to validate and illustrate the use of the new efficiency measures.

关键词： parallel branch-and-bound parallel efficiency knapsack problem

来源：评论

学校读者我要写书评

暂无评论

A massively parallel branch-&-bound algorithm for the balanced minimum evolution problem

引用

COMPUTERS & OPERATIONS RESEARCH 2023年第1期158卷

作者： Catanzaro, Daniele Frohn, Martin Gascuel, Olivier Pesenti, Raffaele Catholic Univ Louvain CORE Voie Roman Pays 34L1-03-01 B-1348 Louvain La Neuve Belgium Eindhoven Univ Technol Dept Math & Comp Sci De Groene Loper 5 NL-5612 AZ Eindhoven Netherlands Inst Systemat Evolut Biodiversite ISYEB UMR CNRS Paris France Museum Natl Hist Nat Paris France Univ Ca Foscari Dept Management Cannaregio 837 I-30121 Venice Italy

We build upon recent theoretical advances in the Balanced Minimum Evolution Problem (BMEP) to design a new massively parallel exact solution algorithm that proves to be up to one order of magnitude faster than the cur... 详细信息

关键词： Combinatorial optimization Integer programming parallel branch-and-bound Network design Balanced minimum evolution problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：