Skip to main content
SpringerLink
Log in

Diversification strategies in tabu search algorithms for the maximum clique problem

  • Tabu Search
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The purpose of this study is to develop some understanding of the benefits that can be derived from the inclusion of diversification strategies in tabu search methods. To do so, we discuss the implementation of various diversification strategies in several tabu search heuristics developed for the maximum clique problem. Computational results on a large set of randomly generated test problems are reported and compared to assess the impact of these techniques on solution quality and running time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. L. Babel and G. Tinhofer, A branch and bound algorithm for the maximum clique problem, ZOR — Meth. Mod. Oper. Res. 34(1990)207–217.

    Article  Google Scholar 

  2. E. Balas and C.S. Yu, Finding a maximum clique in an arbitrary graph, SIAM J. Comp. 15(1986)1054–1068.

    Article  Google Scholar 

  3. P. Berman and A. Pelc, Distributed fault diagnosis for multiprocessor systems,Proc. 20th Annual Int. Symp. on Fault-Tolerant Computing, Newcastle, UK (1990) pp. 340–346.

  4. C. Berge,Théorie des Graphes et ses Applications (Dunod, Paris, 1962).

    Google Scholar 

  5. C. Bron and J. Kerbosh, Finding all cliques of an undirected graph, Commun. ACM 16(1973)575–577.

    Article  Google Scholar 

  6. R. Carraghan and P.M. Pardalos, An exact algorithm for the maximum clique problem, Oper. Res. Lett. 9(1990)375–382.

    Article  Google Scholar 

  7. M.W. Carter and M. Gendreau, A practical algorithm for finding the largest clique in a graph, Publication No. 820, Centre de Recherche sur les Transports, Université de Montréal, Montréal, P.Q., Canada (1992).

    Google Scholar 

  8. T.G. Crainic, M. Gendreau, P. Soriano and M. Toulouse, A tabu search procedure for multicommodity location/allocation with balancing requirements, Ann. Oper. Res. 41(1993)359–383.

    Article  Google Scholar 

  9. V. Degot and J.M. Hualde, De l'utilisation de la notion de clique (sous-graphe complet symmétrique) en matière de typologie des populations, R.A.I.R.O. 9(1975)5–18.

    Google Scholar 

  10. C. Friden, A. Hertz and D. de Werra, Tabaris: An exact algorithm based on tabu search for finding a maximum independent set in a graph, Comp. Oper. Res. 17(1990)437–445.

    Article  Google Scholar 

  11. M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).

    Google Scholar 

  12. M. Gendreau, P. Soriano and L. Salvail, Solving the maximum clique problem using a tabu search approach, Ann. Oper. Res. 41(1993)385–403.

    Article  Google Scholar 

  13. M. Gendreau, A. Hertz and G. Laporte, A tabu search heuristic for the vehicle routing problem, Manag. Sci., to appear.

  14. F. Glover, M. Laguna, E. Taillard and D. de Werra (eds.), Ann. Oper. Res. 41: Tabu search (1993).

  15. F. Glover, E. Taillard and D. de Werra, A user's guide to tabu search, Ann. Oper. Res. 41(1993)3–28.

    Article  Google Scholar 

  16. F. Glover and M. Laguna, Tabu search, in:Modern Heuristic Techniques for Combinatorial Problems, ed. C. Reeves (Blackwell Scientific, Oxford, UK, 1992).

    Google Scholar 

  17. F. Glover, Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem, ORSA J. Comp. (1991).

  18. F. Glover, Future paths for integer programming and links to artificial intelligence, Comp. Oper. Res. 5(1986)533–549.

    Article  Google Scholar 

  19. P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming,Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986).

  20. A. Hertz, E. Taillard and D. de Werra, Tabu search, in:Local Search in Combinatorial Optimization, ed. J.K. Lenstra (1992), and ORPW 92/18, Dep. de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, Switzerland (1992).

    Google Scholar 

  21. A. Hertz and D. de Werra, Using tabu search techniques for graph coloring, Computing 29(1987)345–351.

    Google Scholar 

  22. D.S. Johnson, Approximation algorithms for combinatorial problems, J. Comp. Syst. Sci. 9(1974)256–278.

    Google Scholar 

  23. J.P. Kelly, M. Laguna and F. Glover, A study of diversification strategies for the quadratic assignment problem, Comp. Oper. Res. (1992).

  24. M. Laguna and F. Glover, Integrating target analysis and tabu search for improved scheduling systems, Expert Syst. Appl. (1992).

  25. L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Info. Theory 25(1979)1–7.

    Article  Google Scholar 

  26. I.H. Osman, Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Ann. Oper. Res. 41(1993)421–452.

    Article  Google Scholar 

  27. P.M. Pardalos and J. Xue, The maximum clique problem, Research Report 93-1, Department of Industrial and Systems Engineering, University of Florida (1993).

  28. P.M. Pardalos and G.P. Rodgers, A branch and bound algorithm for the maximum clique problem, Comp. Oper. Res. 19(1992)363–375.

    Article  Google Scholar 

  29. J. Skorin-Kapov, Tabu seartch applied to the quadratic assignment problem, ORSA J. Comp. 2(1990)33–45.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centre de Recherche sur les Transports, Université de Montréal, succursale A, C.P. 6128, H3C 3J7, Montréal, Québec, Canada

    Patrick Soriano

  2. Département d'Informatique et de Recherche Opérationnelle et Centre de Recherche sur les Transports, Université de Montréal, succursale A, C.P. 6128, H3C 3J7, Montréal, Québec, Canada

    Michel Gendreau

Authors
  1. Patrick Soriano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michel Gendreau
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Soriano, P., Gendreau, M. Diversification strategies in tabu search algorithms for the maximum clique problem. Ann Oper Res 63, 189–207 (1996). https://doi.org/10.1007/BF02125454

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02125454

Keywords

Search

Navigation