iBet uBet web content aggregator. Adding the entire web to your favor.

Link to original content: https://unpaywall.org/10.1145/2578948.2560694

Work Stealing Strategies For Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System | Proceedings of Programming Models and Applications on Multicores and Manycores

tutorial

Work Stealing Strategies For Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System

Authors:

Nouredine Melab,

Daniel TuyttensAuthors Info & Claims

PMAM'14: Proceedings of Programming Models and Applications on Multicores and Manycores

Pages 111 - 119

https://doi.org/10.1145/2578948.2560694

Published: 07 February 2014 Publication History

Abstract

Many real-world problems in different industrial and economic fields are permutation combinatorial optimization problems. Solving to optimality large instances of these problems, such as the flowshop problem, is a challenge for multi-core computing.

This paper proposes four work stealing strategies for the multithreaded factoradic-based branch-and-bound (B&B) algorithm to solve permutation combinatorial problems on multi-core processors. The factoradic, called also factorial number system, is a mixed radix numeral system adapted to numbering permutations. In our new parallel strategies, the B&B is based on a matrix of integers instead of a pool of permutations, and work units exchanged between threads are intervals of factoradics instead of sets of nodes.

The experiments show that the strategy based on selecting the largest interval is better than the three other strategies in terms of the number of interval sharing events. Furthermore, the worst factoradic-based strategy spends on average 7.2 times less time managing the pool of subproblems than a conventional pool-based parallel B&B algorithm.

References

[1]

L. Barreto and M. Bauer. Parallel branch and bound algorithm-a comparison between serial, openmp and mpi implementations. In Journal of Physics: Conference Series, volume 256, page 012018. IOP Publishing, 2010.

[2]

G. Cantor. Zeitschrift für mathematik und physik 14, 1869.

[3]

S. Climer and W. Zhang. Cut-and-solve: an iterative search strategy for combinatorial optimization problems, artificial intelligence. 170:714--738, 2006.

Digital Library

[4]

V.D. Cung, S. Dowaji, B. Le Cun, T. Mautor, and C. Roucairol. Parallel and distributed branch-and-bound/A* algorithms. Technical Report 94/31, Laboratoire PRISM, Université de Versailles, 1994.

[5]

J. Eckstein, C. A. Phillips, and W. E. Hart. PICO: An object-oriented framework for parallel branch-and-bound. Research Report 40--2000, RUTCOR, 2000.

[6]

M.R. Garey, D.S. Johnson, and R. Sethi. The complexity of flow-shop and job-shop scheduling. Mathematics of Operations Research, 1:117--129, 1976.

Digital Library

[7]

B. Gendron and T.G. Crainic. Parallel Branch and Bound Algorithms: Survey and Synthesis. Operations Research, 42:1042--1066, 1994.

Digital Library

[8]

B. Goldengorin, D. Ghosh, and G. Sierksma. Branch and peg algorithms for the simple plant location problem. Computers & Operations Research, 31:241--255, 2004.

Digital Library

[9]

V.K. Janakiram, D.P. Agrawal, and R. Mehrotra. A Randomized Parallel Branch-and-bound Algorithm. In in Proc. of Int. Conf. on Parallel Processing, pages 69--75, Aug. 1988.

Digital Library

[10]

S.M. Johnson. Optimal two and three-stage production schedules with setup times included. Naval Research Logistis Quarterly, 1:61--68, 1954.

[11]

D.E. Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Reading, Ma, page 192, 1997. ISBN=9780201896848.

Digital Library

[12]

V. Kumar and L. Kanal. Parallel Branch-and-Bound Formulations For And/Or Tree Search. IEEE Trans. Pattern. Anal. and Machine Intell., PAMI--6:768--778, 1984.

Digital Library

[13]

C-A. Laisant. Sur la numération factorielle, application aux permutations. Bulletin de la Société Mathématique de France, 16:176--183, 1888.

[14]

J.K. Lenstra, B.J. Lageweg, and A.H.G. Rinnooy Kan. A General bounding scheme for the permutation flow-shop problem. Operations Research, 26(1):53--67, 1978.

Digital Library

[15]

J. McCaffrey. Using permutations in .NET for improved systems security, 2003.

[16]

N. Melab. Contributions à la résolution de problèmes d'optimisation combinatoire sur grilles de calcul. LIFL, USTL, Novembre 2005. Thèse HDR.

[17]

M. Mezmaz, N. Melab, and E-G. Talbi. A grid-enabled branch and bound algorithm for solving challenging combinatorial optimization problems. In In Proc. of 21th IEEE Intl. Parallel and Distributed Processing Symp. (IPDPS). Long Beach, California, March 2007.

[18]

M. Mezmaz, N. Melab, and D. Tuyttens. A multithreaded branch-and-bound algorithm for solving the flow-shop problem on a multicore environment, chapter 3, pages 53--70. Large Scale Network--Centric Distributed Systems. John Wiley & Sons, July 2013. ISBN-10: 0470936886, ISBN-13: 978-0470936887.

[19]

D.L. Miller and J.F. Pekny. The Role of Performance Metrics for Parallel Mathematical Programming Algorithms. ORSA J. Computing, 5(1):26--28, 1993.

[20]

R. Pastor and A. Corominas. Branch and win: Or tree search algorithms for solving combinatorial optimisation problems. Top, 1:169--192, 2004.

[21]

R. Paulavičius and J. Žilinskas. Parallel branch and bound algorithm with combination of lipschitz bounds over multidimensional simplices for multicore computers. Parallel Scientific Computing and Optimization, pages 93--102, 2009.

[22]

J.F. Sanjuan-Estrada, L.G. Casado, and I. García. Adaptive parallel interval branch and bound algorithms based on their performance for multicore architectures. The Journal of Supercomputing, pages 1--9, 2011.

[23]

E. Taillard. Benchmarks for basic scheduling problems. Journal of Operational Research, 64:278--285, 1993.

Cited By

Finnerty PKamada TOhta C(2021)A self‐adjusting task granularity mechanism for the Java lifeline‐based global load balancer library on many‐core clustersConcurrency and Computation: Practice and Experience10.1002/cpe.622434:2Online publication date: 18-Feb-2021
https://doi.org/10.1002/cpe.6224
Finnerty PKamada TOhta C(2020)Self-adjusting task granularity for Global load balancer library on clusters of many-core processorsProceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3380536.3380539(1-10)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3380536.3380539
Gmys JLeroy RMezmaz MMelab NTuyttens D(2018)Work stealing with private integer-vector-matrix data structure for multi-core branch-and-bound algorithmsConcurrency and Computation: Practice & Experience10.1002/cpe.377128:18(4463-4484)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1002/cpe.3771
Show More Cited By

Index Terms

Recommendations

Work Stealing Strategies For Multi-Core Parallel Branch-and-Bound Algorithm Using Factorial Number System
PMAM'14: Proceedings of Programming Models and Applications on Multicores and Manycores

Many real-world problems in different industrial and economic fields are permutation combinatorial optimization problems. Solving to optimality large instances of these problems, such as the flowshop problem, is a challenge for multi-core computing.

...
A Multi-core Parallel Branch-and-Bound Algorithm Using Factorial Number System
IPDPS '14: Proceedings of the 2014 IEEE 28th International Parallel and Distributed Processing Symposium

Many real-world problems in different industrial and economic fields are permutation combinatorial optimization problems. Solving to optimality large instances of these problems, such as flowshop problem, is a challenge for multi-core computing. This ...
Work stealing with private integer-vector-matrix data structure for multi-core branch-and-bound algorithms

In this paper, the focus is put on multi-core branch-and-bound algorithms for solving large-scale permutation-based optimization problems. We investigate five work stealing WS strategies with a new data structure called integer-vector-matrix IVM. In ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PMAM'14: Proceedings of Programming Models and Applications on Multicores and Manycores

February 2014

156 pages

ISBN:9781450326575

DOI:10.1145/2578948

Conference Chairs:
Pavan Balaji
Argonne National Laboratory, USA
,
Minyi Guo
Shanghai Jiao Tong, University, China
,
Zhiyi Huang
University of Otago, New Zealand

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 February 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial
Research
Refereed limited

Conference

PPoPP '14

Sponsor:

SIGPLAN

PPoPP '14: ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 15 - 19, 2014

FL, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 53 of 97 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
193
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Finnerty PKamada TOhta C(2021)A self‐adjusting task granularity mechanism for the Java lifeline‐based global load balancer library on many‐core clustersConcurrency and Computation: Practice and Experience10.1002/cpe.622434:2Online publication date: 18-Feb-2021
https://doi.org/10.1002/cpe.6224
Finnerty PKamada TOhta C(2020)Self-adjusting task granularity for Global load balancer library on clusters of many-core processorsProceedings of the Eleventh International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/3380536.3380539(1-10)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3380536.3380539
Gmys JLeroy RMezmaz MMelab NTuyttens D(2018)Work stealing with private integer-vector-matrix data structure for multi-core branch-and-bound algorithmsConcurrency and Computation: Practice & Experience10.1002/cpe.377128:18(4463-4484)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1002/cpe.3771
McCreesh CProsser P(2015)The Shape of the Search Tree for the Maximum Clique Problem and the Implications for Parallel Branch and BoundACM Transactions on Parallel Computing10.1145/27423592:1(1-27)Online publication date: 13-Apr-2015
https://dl.acm.org/doi/10.1145/2742359

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents