[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Parallel local search

Published: 01 September 1995 Publication History

Abstract

We present a survey of parallel local search algorithms in which we review the concepts that can be used to incorporate parallelism into local search. For this purpose we distinguish between single-walk and multiple-walk parallel local search and between asynchronous and synchronous parallelism. Within the class of single-walk algorithms we differentiate between multiple-step and single-step parallelism. To describe parallel local search we introduce the concepts of hyper neighborhood structures and distributed neighborhood structures. Furthermore, we present templates that capture most of the parallel local search algorithms proposed in the literature. Finally, we discuss some complexity issues related to parallel local search.

References

[1]
Aarts E.H.L., De Bont F.M.I., Habers J.H.A., and Van Laarhoven P.J.M. Parallel implementations of the statistical cooling algorithms Integration 1986 4 209-238
[2]
Aarts E.H.L. and Korst J. Simulated Annealing and Bolztmann Machines 1989 New York Wiley
[3]
Aarts E.H.L. and Lenstra J.K. Local Search in Combinatorial Optimization 1995 New York Wiley
[4]
Abramson D. Constructing school timetables using simulated annealing: Sequential and parallel algorithms Management Science 1991 37 98-113
[5]
Allwright J.R.A. and Carpenter D.B. A distributed implementation of simulated annealing for the traveling salesman problem Parallel Computing 1989 10 335-338
[6]
Azencott R. Simulated Annealing: Parallelization Techniques 1992 New York Wiley
[7]
Bachem A. and Wottawa. Parallelization of Heuristics for Large Traveling Salesman Problems (in German). Report no. 92. 119 1992 Germany Universität zu Köln
[8]
Barbosa V.C. and Boeres M.C.S. An Occam-based evaluation of a parallel version of simulated annealing Microprocessing and Microprogramming 1990 30 85-92
[9]
Barbosa V.C. and Gafni E. A distributed implementation of simulated annealing Journal of Parallel and Distributed Computing 1989 6 411-434
[10]
Battiti R. and Tecchiolli G. Parallel biased search for combinatorial optimization: Genetic algorithms and tabu Microprocessors and Microsystems 1992 16 351-367
[11]
Brent R.P. The parallel evaluation of general arithmetic expressions Journal ACM 1974 21 201-206
[12]
Casotto A., Romeo F., and Sangiovanni-Vincentelli A. A parallel simulated annealing algorithm for the placement of macro-cells IEEE Transactions on Computer-Aided Design 1987 6 838-847
[13]
Chakrapani J. and Skorin-Kapov J. Connection machine implementation of a tabu search algorithm for the traveling salesman problem Journal of Computing and Information Technology 1993 1 29-36
[14]
Chakrapani J. and Skorin-Kapov J. Massively parallel tabu search for the quadratic assignment problem Annals of Operations Research 1993 41 327-342
[15]
Crainic, T.G., Toulouse, M., and Gendreau, M. (1993a).Parallel Asynchronous Tabu Search for Multicommodity Location-Allocation with Balancing Requirements. Publication 935, Centre de recherche sur les transports, Université de Montréal.
[16]
Crainic, T.G., Toulouse, M., and Gendreau, M. (1993b).Towards a Taxonomy of Parallel Tabu Search Algorithms. Publication 933, Centre de recherche sur les transports, Université de Montréal.
[17]
Crainic, T.G., Toulouse, M., and Gendreau, M. (1995). Synchronous tabu search parallelization strategies for multicommodity location-allocation with balancing requirements.OR Spektrum 17.
[18]
Darema F., Kirkpatrick S., and Norton V.A. Parallel algorithms for chip placement by simulated annealing IBM Journal of Research and Development 1987 31 391-402
[19]
Diekmann R., Lüling R., and Simon J. Vidal R.V.V. Problem independent distributed simulated annealing and its applications Applied Simulated Annealing 1993 Berlin Springer-Verlag 18-44
[20]
Dodd N. Slow annealing versus multiple fast annealing runs: An empirical investigation Parallel Computing 1990 16 269-272
[21]
Ten Eikelder H.M.M., Verhoeven M.G.A., Vossen T.W.M., and Aarts E.H.L. Osman I.H. and Kelly J.P. A probabilistic analysis of local search Metaheuristics: The State of the Art 1995 1995 Boston Kluwer
[22]
Felten, E., Karlin, S., and Otto, S.W. (1985). The traveling salesman problem on a hypercubic MIMD machine.Proceedings of the International Conference on Parallel Processing (pp. 6–10). New York.
[23]
Ferreira A.G. and Zerovnik J. Bounding the probability of success of stochastic methods for global optimization Computers and Mathematics with Applications 1993 25 1-8
[24]
Fiechter C.N. A parallel tabu search algorithm for large travelling salesman problems Discrete Applied Mathematics 1994 51 243-267
[25]
Fox B.L. Integrating and accelerating tabu search, simulated annealing, and genetic algorithms Annals of Operations Research 1993 41 47-67
[26]
Garcia B.L., Potvin J.Y., and Rousseau J.M. A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints Computer Operations Research 1994 21 1025-1033
[27]
Garey M.R. and Johnson D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness 1979 New York Freeman
[28]
Glover F. Tabus search: Part I ORSA Journal on Computing 1989 1 190-206
[29]
Glover F., Taillard E., and De Werra D. A user's guide to tabu search Annals of Operations Research 1993 41 3-28
[30]
Goloberg D.E. Genetic Algorithms in Search, Optimization, and Machine Learning 1989 Reading, MA Addison-Wesley
[31]
Greening D.R. Parallel simulated annealing techniques Physica D 1990 42 293-306
[32]
Jog P. and Van Gucht D. Parallelisation of probabilistic sequential search algorithms Proceedings of the Second International Conference on Genetic Algorithms 1987 San Mateo Morgan Kaufmann 170-176
[33]
Johnson D.S. Local optimization and the traveling salesman problem Proceedings of the Seventeenth Colloquium on Automata, Languages, and Programming 1990 Berlin Springer 446-461
[34]
Johnson D.S., Papadimitriou C.H., and Yannakakis M. How easy is local search? Journal of Computer and System Sciences 1988 37 79-100
[35]
Jones, M.H., and Banerjee, P. (1987). An improved simulated annelaing algorithm for standard cell placement.Proceedings of the International Conference on Computer Design (pp. 83–86). Washington, D.C.
[36]
Kernighan B.W. and Lin S. An efficient heuristic procedure for partitioning graphs Bell systems Technical Journal 1970 49 291-307
[37]
Kindervater G.A.P., Lenstra J.K., and Savelsbergh M.W.P. Sequential and parallel local search for the time constrained traveling salesman problem Discrete Applied Mathematics 1993 42 211-225
[38]
Kirkpatrick S., Gelatt C.D. Jr., and Vecchi M.P. Optimization by simulated annealing Science 1983 220 671-680
[39]
Kirkpatrick S. and Toulouse G. Configuration space analysis of travelling salesman problems Journal Physique 1985 46 1277-1292
[40]
Kravitz S.A. and Rutenbar R.A. Placement by simulated annealing on a multiprocessor IEEE Transactions on Computer Aided Design 1987 6 534-549
[41]
Kruskal C.P., Rudolph L., and Snir M. A complexity theory of efficient parallel algorithms Theoretical Computer Science 1990 71 95-132
[42]
Li Y. and Pardalos P.M. Pardalos P.M. Parallel algorithms for the quadratic assignment problem Advances in Optimization and Parallel Computing 1992 Amsterdam Elsevier Science Publishers 177-189
[43]
Lin S. Computer solutions of the traveling salesman problem Bell System Technical Journal 1965 44 2245-2269
[44]
Lin S. and Kernichan B.W. An effective heuristic algorithm for the traveling salesman problem Operations Research 1973 21 498-516
[45]
Lueker, G. (1975).Two NP-Complete Problems in Nonnegative Integer Programming. Manuscript, Princeton University.
[46]
Mahfoud S.W. and Goldberg D.E. Parallel recombinative simulated annealing: A genetic algorithm Parallel Computing 1995 21 1-28
[47]
Malek M., Guruswamy M., and Pandya M. Serial and parallel simulated annealing and tabu search for the traveling salesman problem annals of Operations Research 1989 21 59-84
[48]
Martin O, Otto S.W., and Felten E.W. Large-steps Markov chains for the travelling salesman problem Complex Systems 1991 5 299-326
[49]
Michalewicz Z. Genetic Algorithms+Data Structures=Evolution Programs 1992 Berlin Springer-Verlag
[50]
Moscato P. An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search Annals of Operations Research 1993 41 85-122
[51]
Mühlenbein H. Balci O. Parallel genetic algorithms in combinatorial optimization Computer Science and Operations Research 1992 London Pergamon Press
[52]
Mühlenbein H., Gorges-Schleuter M., and Krämer O. Evolution algorithms in combinatorial optimization Parallel Computing 1988 7 65-85
[53]
Osborne L.J. and Gillett B.E. A comparison of two simulated annealing algorithms applied to the directed Steiner problem on networks ORSA Journal on Computing 1991 3 213-225
[54]
Papadimitriou C.H. and Steiglitz K. Combinatorial Optimization: Algorithms and Complexity 1982 Englewood Cliffs, NJ Prentice-Hall
[55]
Parberry I. Parallel Complexity Theory 1987 London Pitman
[56]
Ravikumar C.P. Parallel techniques for solving large scale travelling salesperson problems Microprocessors and Microsystems 1992 16 149-158
[57]
Reeves C.R. Modern Heuristic Techniques for Combinatorial Problems 1993 London Blackwell
[58]
Romeo F. and Sangiovanni-Vicentelli A. a theoretical framework for simulated annealing Algorithmica 1991 6 302-345
[59]
Rose J.S., Snelgrove W.M., and Vranesic Z.G. Parallel standard cell placement algorithms with quality equivalent to simulated annealing IEEE Transactions on Computer-Aided Design 1988 7 387-396
[60]
Roussel-Ragot P. and Dreyfus G. A problem independent parallel implementation for simulated annealing: Models and experiments IEEE Transactions on Computer-Aided Design 1990 9 827-835
[61]
Savage J.E. and Wloka M.G. Parallelism in graph-partioning Journal of Parallel and Distributed Computing 1991 13 257-272
[62]
Sechen C. VLSI Placement and Global Routing Using Simulated Annealing 1988 Boston Kluwer
[63]
Shahookar K. and Mazunder P. VLSI cell-placement techniques ACM Computing Surveys 1991 23 143-220
[64]
Taillard E. Some efficient heuristic methods for the flow shop sequencing problem European Journal of Operations Research 1990 47 65-74
[65]
Taillard E. Robust taboo search for the quadratic assignment problem Parallel Computing 1991 17 443-455
[66]
Taillard E. Parallel iterative search methods for vehicle routing problems Networks 1993 23 661-673
[67]
Taillard E. Parallel taboo search techniques for the job shop scheduling problem ORSA Journal on Computing 1994 6 108-117
[68]
Vaessens R.J.M., Aarts E.H.L., and Lenstra J.K. A local search template Parallel Problem Solving from Nature 1992 2 65-74
[69]
Verhoeven M.G.A., Aarts E.H.L., and Swinkels P.C.J. A parallel 2-opt algorithm for the traveling salesman problem Future Generation Computer Systems 1995 11 175-182
[70]
Verhoeven M.G.A., Aarts E.H.L., Van de Sluis E., and Vaessens R.J.M. Parallel local search and the travelling salesman problem (extended abstract) Proceedings of Parallel Problem Solving from Nature 1992 2 543-552
[71]
Verhoeven, M.G.A., Swinkels, P.C.J., and Aarts, E.H.L. (1995). Parallel local search and the traveling salesman problem. Working document.
[72]
Voss, S. (1993). Tabu search: Applications and Prospects. In D.Z. Du and P.M. Pardalos (Eds.),Network Optimization Problems (pp. 333–353). City: World Scientific.
[73]
Yannakakis M. The analysis of local search problems and their heuristics Proceedings of the Seventh Symposium on Theoretical Aspects of Computer Science 1990 Berlin Springer-Verlag 298-311
[74]
Yannakakis M. Aarts E.H.L. and Lenstra J.K. Computational complexity of local search Local Search in Combinatorial Optimization 1995 Berlin Springer-Verlag
[75]
Yeong C.S. and Kim M.H. Fast parallel simulated annealing for traveling salesman problem on SIMD machines with linear interconnections Parallel Computing 1991 17 221-228

Cited By

View all
  • (2024)CPLNS: Cooperative Parallel Large Neighborhood Search for Large-Scale Multi-Agent Path FindingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.340803035:11(2069-2086)Online publication date: 1-Nov-2024
  • (2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
  • (2022)Defining Parallel Local Search Procedures with Neighborhood CombinatorsSN Computer Science10.1007/s42979-022-01120-13:3Online publication date: 20-Apr-2022
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Heuristics
Journal of Heuristics  Volume 1, Issue 1
Sep 1995
105 pages

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 September 1995

Author Tags

  1. local search
  2. parallel algorithms
  3. survey
  4. single-walk and multiple-walk parallelism

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 23 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)CPLNS: Cooperative Parallel Large Neighborhood Search for Large-Scale Multi-Agent Path FindingIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2024.340803035:11(2069-2086)Online publication date: 1-Nov-2024
  • (2024)Large-scale and cooperative graybox parallel optimization on the supercomputer FugakuJournal of Parallel and Distributed Computing10.1016/j.jpdc.2024.104921191:COnline publication date: 18-Jul-2024
  • (2022)Defining Parallel Local Search Procedures with Neighborhood CombinatorsSN Computer Science10.1007/s42979-022-01120-13:3Online publication date: 20-Apr-2022
  • (2022)Runtime Analysis of Unbalanced Block-Parallel Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVII10.1007/978-3-031-14721-0_39(555-568)Online publication date: 10-Sep-2022
  • (2012)Parallel GPU Implementation of Iterated Local Search for the Travelling Salesman ProblemRevised Selected Papers of the 6th International Conference on Learning and Intelligent Optimization - Volume 721910.5555/2961491.2961523(372-377)Online publication date: 16-Jan-2012
  • (2002)Probability Distribution of Solution Time in GRASPJournal of Heuristics10.1023/A:10150618026598:3(343-373)Online publication date: 1-May-2002

View Options

View options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media