poster

Performance analysis of parallel constraint-based local search

Authors:

Salvador AbreuAuthors Info & Claims

PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

Pages 337 - 338

https://doi.org/10.1145/2145816.2145883

Published: 25 February 2012 Publication History

Get Access

Abstract

We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results for hard combinatorial optimization problems on two different platforms up to several hundreds of cores. On a variety of classical CSPs benchmarks, speedups are very good for a few tens of cores, and good up to a hundred cores. More challenging problems derived from reallife applications (Costas array) shows even better speedups, nearly optimal up to 256 cores.

References

[1]

E. Alba. Special issue on new advances on parallel meta-heuristics for complex problems. Journal of Heuristics, 10(3):239--380, 2004.

Digital Library

Google Scholar

[2]

Y. Caniou, P. Codognet, D. Diaz, and S. Abreu. Experiments in parallel constraint-based local search. In EvoCOP11, 11th European Conference on Evolutionary Computation in Combinatorial Optimisation, LNCS 6622, pages 96--107. Springer Verlag, 2011.

Digital Library

Google Scholar

[3]

P. Codognet and D. Diaz. Yet another local search method for constraint solving. In proceedings of SAGA'01, pages 73--90. Springer Verlag, 2001.

Digital Library

Google Scholar

[4]

P. Codognet and D. Diaz. An efficient library for solving CSP with local search. In T. Ibaraki, editor, MIC'03, 5th International Conference on Metaheuristics, 2003.

Google Scholar

[5]

T. Crainic and M. Toulouse. Special issue on parallel meta-heuristics. Journal of Heuristics, 8(3):247--388, 2002.

Digital Library

Google Scholar

[6]

K. Drakakis. A review of costas arrays. Journal of Applied Mathematics, 2006:1--32, 2006.

Crossref

Google Scholar

[7]

I. P. Gent and T.Walsh. CSPLIB: A benchmark library for constraints. In proceedings of CP'99, pages 480--481. Springer Verlag, 1999.

Digital Library

Google Scholar

[8]

T. Gonzalez, editor. Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall / CRC, 2007.

Digital Library

Google Scholar

[9]

P. V. Hentenryck and L. Michel. Constraint-Based Local Search. The MIT Press, 2005.

Digital Library

Google Scholar

[10]

T. Ibaraki, K. Nonobe, and M. Yagiura, editors. Metaheuristics: Progress as Real Problem Solvers. Springer Verlag, 2005.

Google Scholar

[11]

S. Kadioglu and M. Sellmann. Dialectic search. In CP'09, Int. Conf. on Principles and Practice of Constraint Programming. Springer Verlag, 2009.

Digital Library

Google Scholar

[12]

M. Verhoeven and E. Aarts. Parallel local search. Journal of Heuristics, 1(1):43--65, 1995.

Crossref

Google Scholar

Cited By

View all

Arbelaez AMehta DO'sullivan BQuesada L(2018)A constraint-based parallel local search for the edge-disjoint rooted distance-constrained minimum spanning tree problemJournal of Heuristics10.1007/s10732-017-9342-024:3(359-394)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10732-017-9342-0
Arbelaez AMehta DO’Sullivan BQuesad L(2018)Parallel Constraint-Based Local Search: An Application to Designing Resilient Long-Reach Passive Optical NetworksHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_17(633-665)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_17
Codognet PMunera DDiaz DAbreu S(2018)Parallel Local SearchHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_10(381-417)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_10
Show More Cited By

Index Terms

Performance analysis of parallel constraint-based local search

Recommendations

Performance analysis of parallel constraint-based local search
PPOPP '12

We present a parallel implementation of a constraint-based local search algorithm and investigate its performance results for hard combinatorial optimization problems on two different platforms up to several hundreds of cores. On a variety of classical ...
Local search algorithms for the k-cardinality tree problem

In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node-weighted graphs. This problem has several applications, which justify the need for efficient methods to obtain good solutions. We review ...
A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs

We propose a new neighborhood structure for the problem. The results demonstrate that our neighborhood structure is better than the current ones, and it has the additional benefit that it can be explored using a GPU-based massively parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming

February 2012

352 pages

ISBN:9781450311601

DOI:10.1145/2145816

General Chair:
J. Ramanujam
Louisiana State University, USA
,
Program Chair:
P. Sadayappan
The Ohio State University, USA

ACM SIGPLAN Notices Volume 47, Issue 8
PPOPP '12
August 2012
334 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2370036
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 February 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

PPoPP '12

Sponsor:

SIGPLAN

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

February 25 - 29, 2012

Louisiana, New Orleans, USA

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
172
Total Downloads

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

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Arbelaez AMehta DO'sullivan BQuesada L(2018)A constraint-based parallel local search for the edge-disjoint rooted distance-constrained minimum spanning tree problemJournal of Heuristics10.1007/s10732-017-9342-024:3(359-394)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s10732-017-9342-0
Arbelaez AMehta DO’Sullivan BQuesad L(2018)Parallel Constraint-Based Local Search: An Application to Designing Resilient Long-Reach Passive Optical NetworksHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_17(633-665)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_17
Codognet PMunera DDiaz DAbreu S(2018)Parallel Local SearchHandbook of Parallel Constraint Reasoning10.1007/978-3-319-63516-3_10(381-417)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-63516-3_10
Truchet CArbelaez ARichoux FCodognet P(2016)Estimating parallel runtimes for randomized algorithms in constraint solvingJournal of Heuristics10.1007/s10732-015-9292-322:4(613-648)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10732-015-9292-3
Ravichandran KPande S(2013)MultiverseACM SIGPLAN Notices10.1145/2544173.250952548:10(533-552)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509525
Ravichandran KPande SHosking AEugster PLopes C(2013)MultiverseProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509525(533-552)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509525
Truchet CRichoux FCodognet P(2013)Prediction of Parallel Speed-Ups for Las Vegas AlgorithmsProceedings of the 2013 42nd International Conference on Parallel Processing10.1109/ICPP.2013.25(160-169)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1109/ICPP.2013.25
Machado RAbreu SDiaz D(2013)Parallel Performance of Declarative Programming Using a PGAS ModelProceedings of the 15th International Symposium on Practical Aspects of Declarative Languages - Volume 775210.1007/978-3-642-45284-0_17(244-260)Online publication date: 21-Jan-2013
https://dl.acm.org/doi/10.1007/978-3-642-45284-0_17

View Options

Get Access

Login options

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

Cited By

Index Terms

Recommendations

Performance analysis of parallel constraint-based local search

Local search algorithms for the k-cardinality tree problem

A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs