Abstract
Cooperative search is a parallelization strategy for search algorithms where parallelism is obtained by concurrently executing several search programs. The solution space is implicitly decomposed according to the search strategy of each program. The programs cooperate by exchanging information on previously explored regions of the solution space. In this paper we propose a new design for cooperative search algorithms which is also a new parallel problem solving paradigm for combinatorial optimization problems. Our new design is based on an innovative approach to decompose the solution space which is inspired from the modeling of cooperative algorithms based on dynamical systems theory. Our design also gives a new purpose to the sharing of information among cooperating tasks based on principles borrowed from scatter search evolutionary algorithms. We have applied this paradigm to the graph partitioning problem. We describe the parallel implementation of this algorithm on a cluster of workstations and compare our results with other well known graph partitioning methods.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
F. Glover. Heuristics for Integer Programming Using Surrogate Constraints. Decision Sciences, 8(1):156–166, 1977.
F. Glover. Ejection Chains, Reference Structures and Alternating Path Methods for the Traveling Salesman Problem. Report, University of Colorado, Boulder, 1992.
F. Glover. A Template for Scatter Search and Path Relinking. In J.K. Hao, E. Lutton, E. Ronald, M. Schoenauer and D. Snyers, editors, Lecture Notes in computer Science, 1997.
F. Glover and M. Laguna. Tabu Search. In C. Reeves, editor, Modern Heuristic Techniques for Combinatorial Problems, pages 70–141. Blackwell Scientific Publishing, 1993.
F. Glover and M. Laguna. Tabu Search. Kluwer Academic Publishers, 1997.
B. Hendrickson and R. Leland. A Multilevel Algorithm for Partitioning Graphs. Report SAND93-1301, Sandia National Laboratories, 1993.
B. Hendrickson and R. Leland. The Chaco User’s Guide: Version 2.0. Report SAND95-2344, Sandia National Laboratories, 1995.
G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. SIAM Journal on Scientific Computing, to appear.
G. Karypis and V. Kumar. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices: Version 3.0. Report, University of Minnesota, 1997.
J.P. Kelly and J. Xu. Tabu Search and Vocabulary Building for Routing Problems. Technical report, Graduate School of Business Administration, University of Colorado at Boulder, 1995.
L. Lopez, M.W. Carter, and M. Gendreau. The Hot StripMill Production Scheduling Problem: A Tabu Search Approach. Report, Center for Research on Transportation, Université de Montréal, 1996.
Y. Rochat and E. Taillard. Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Journal of Heuristics, 1(1):147–167, 1995.
E. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin. A New Neighborhood Structure for Vehicule Routing with Time Window. Report CRT-95-66, Center for Research on Transportation, Université de Montréal, 1995.
M. Toulouse, T.G. Crainic, and B. Sanśo. An Experimental Study of Systemic Behavior of Cooperative Search Algorithms. In I.H. Osman S. Voss, S. Martello and C. Roucairol, editors, Meta-Heuristics: Theory and Applications, pages 373–392. Kluwer Academic Publishers, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Toulouse, M., Thulasiraman, K., Glover, F. (1999). Multi-level Cooperative Search: A New Paradigm for Combinatorial Optimization and an Application to Graph Partitioning. In: Amestoy, P., et al. Euro-Par’99 Parallel Processing. Euro-Par 1999. Lecture Notes in Computer Science, vol 1685. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48311-X_75
Download citation
DOI: https://doi.org/10.1007/3-540-48311-X_75
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66443-7
Online ISBN: 978-3-540-48311-3
eBook Packages: Springer Book Archive