Skip to main content
SpringerLink
Log in

Heuristics and metaheuristics for the maximum diversity problem

  • Published:
Journal of Heuristics Aims and scope Submit manuscript

Abstract

This paper presents extensive computational experiments to compare 10 heuristics and 20 metaheuristics for the maximum diversity problem (MDP). This problem consists of selecting a subset of maximum diversity from a given set of elements. It arises in a wide range of real-world settings and we can find a large number of studies, in which heuristic and metaheuristic methods are proposed. However, probably due to the fact that this problem has been referenced under different names, we have only found limited comparisons with a few methods on some sets of instances.

This paper reviews all the heuristics and metaheuristics for finding near-optimal solutions for the MDP. We present the new benchmark library MDPLIB, which includes most instances previously used for this problem, as well as new ones, giving a total of 315. We also present an exhaustive computational comparison of the 30 methods on the MDPLIB. Non-parametric statistical tests are reported in our study to draw significant conclusions.

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

  • Aringhieri, R., Cordone, R.: Better and faster solutions for the maximum diversity problem. Technical report, Université degli Studi di Milano, Polo Didattico e di Ricerca di Crema (2006)

  • Aringhieri, R., Cordone, R.: Comparing local search metaheuristics for the maximum diversity problem. J. Oper. Res. Soc. 62, 266–280 (2011)

    Article  Google Scholar 

  • Aringhieri, R., Cordone, R., Melzani, Y.: Tabu search vs. grasp for the maximum diversity problem. 4OR 6(1), 45–60 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  • Brimberg, J., Mladenovic, N., Urosevic, D., Ngai, E.: Variable neighborhood search for the heaviest k-subgraph. Comput. Oper. Res. 36(11), 2885–2891 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Cappanera, P.: A survey on obnoxious facility location problems. Technical Report TR-99-11, Dipartimento di Elettronica ed Informazione, Politecnico di Milano, 19 (1999)

  • Chandra, B., Halldorsson, M.M.: Approximation algorithms for dispersion problems. J. Algorithms 38(2), 438–465 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Duarte, A., Martí, R.: Tabu search and grasp for the maximum diversity problem. Eur. J. Oper. Res. 178, 71–84 (2007)

    Article  MATH  Google Scholar 

  • Erkut, E.: The discrete p-dispersion problem. Eur. J. Oper. Res. 46(1), 48–60 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  • Erkut, E., Neuman, S.: Comparison of four models for dispersing facilities. INFOR Can. J. Oper. Res. Inf. Process. 29, 68–86 (1991)

    MATH  Google Scholar 

  • Feige, U., Kortsarz, G., Peleg, D.: The dense k-subgraph problem. Algorithmica 29, 410–421 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  • Feo, T., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 2, 1–27 (1995)

    MathSciNet  Google Scholar 

  • Gallego, M., Duarte, A., Laguna, M., Martí, R.: Hybrid heuristics for the maximum diversity problem. Comput. Optim. Appl. 44(3), 411–426 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Ghosh, J.B.: Computational aspects of the maximum diversity problem. Oper. Res. Lett. 19(1), 175–181 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  • Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13, 533–549 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  • Glover, F., Laguna, M.: Tabu Search. Kluwer Academic, Boston (1997)

    Book  MATH  Google Scholar 

  • Glover, F., Kuo, C.C., Dhir, K.S.: Heuristic algorithms for the maximum diversity problem. J. Inf. Optim. Sci. 19(1), 109–132 (1998)

    MATH  Google Scholar 

  • Han, J., Kamber, M.: Data Mining: Concepts and Techniques. Morgan Kaufmann, San Mateo (2000)

    Google Scholar 

  • Hansen, P., Mladenovic, N.: Handbook of Metaheuristics. Springer, Berlin (2003). Chap. Variable neighborhood search, pp. 145–184

    Google Scholar 

  • Katayama, K., Narihisa, H.: An evolutionary approach for the maximum diversity problem. In: Hart, W., Krasnogor, N., Smith, J.E. (eds.) Recent Advances in Memetic Algorithms, vol. 166, pp. 31–47. Springer, Berlin (2005)

    Chapter  Google Scholar 

  • Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291–307 (1970) 1970

    MATH  Google Scholar 

  • Kincaid, R.K.: Good solutions to discrete noxious location problems via metaheurísticas. Ann. Oper. Res. 40(1), 265–281 (1992)

    Article  MATH  Google Scholar 

  • Kincaid, R.K., Yellin, L.G.: The discrete p-dispersion-sum problem: Results on trees and graphs. Comput. Oper. Res. 1(2), 171–186 (1993)

    MATH  Google Scholar 

  • Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  • Kuby, M.J.: Programming models for facility dispersion: The p-dispersion and maximum dispersion problem. Geogr. Anal. 19(4), 315–329 (1987)

    Article  Google Scholar 

  • Kuo, C.C., Glover, F., Dhir, K.S.: Analyzing and modeling the maximum diversity problem by zero-one programming. Decis. Sci. 24(6), 1171–1185 (1993)

    Article  Google Scholar 

  • Laguna, M., Martí, R.: Grasp and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11, 44–52 (1999)

    Article  MATH  Google Scholar 

  • Laguna, M., Marti, R.: Scatter Search Methodology and Implementations in C. Kluwer Academic, Dordrecht (2003)

    Book  Google Scholar 

  • Macambira, E.M.: An application of tabu search heuristic for the maximum edge-weighted subgraph problem. Ann. Oper. Res. 177, 175–190 (2002)

    Article  MathSciNet  Google Scholar 

  • Macambira, E.M., de Souza, C.C.: The edge-weighted clique problem: valid inequalities, facets and polyhedral computations. Eur. J. Oper. Res. 123, 346–371 (2000)

    Article  MATH  Google Scholar 

  • Martí, R., Gallego, M., Duarte, A.: A branch and bound algorithm for the maximum diversity problem. Eur. J. Oper. Res. 200(1), 36–44 (2010)

    Article  MATH  Google Scholar 

  • McConnell, S.: The new battle over immigration. Fortune 117(10), 89–102 (1988)

    Google Scholar 

  • Moon, I.D., Chaudhry, S.S.: An analysis of network location problems with distance constraints. Manag. Sci. 30(3), 290–307 (1984)

    Article  MATH  Google Scholar 

  • Moscato, P.: Memetic algorithms: A short introduction. In: Corne, D., Dorigo, M., Glover, F. (eds.) New Ideas in Optimization, pp. 219–234. McGraw-Hill, Maidenhead (1999)

    Google Scholar 

  • Palubeckis, G.: Iterated tabu search for the maximum diversity problem. Appl. Math. Comput. 189, 371–383 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  • Pearce, D.: Economics and genetic diversity. Future 19(6), 710–712 (1987)

    Article  MathSciNet  Google Scholar 

  • Pisinger, D.: Upper bounds and exact algorithms for p-dispersion problems. Comput. Oper. Res. 33(5), 1380–1398 (2006)

    Article  MATH  Google Scholar 

  • Porter, W.M., Rawal, K.M., Rachie, K.O., Wien, H.C., Williams, R.C.: Cowpea germplasm catalog No 1. International Institute of Tropical Agriculture, Ibadan, Nigeria (1975)

  • Prokopyev, O.A., Kong, N., Martinez-Torres, D.L.: The equitable dispersion problem. Eur. J. Oper. Res. 197(1), 59–67 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  • Ravi, S.S., Rosenkrantz, D.J., Tayi, G.K.: Heuristic and special case algorithms for dispersion problems. Oper. Res. 42(2), 299–310 (1994)

    Article  MATH  Google Scholar 

  • Ribeiro, C.C., Uchoa, E., Werneck, R.F.: A hybrid grasp with perturbations for the steiner problem in graphs. INFORMS J. Comput. 14(3), 228–246 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  • Santos, L.F., Ribeiro, M.H., Plastino, A., Martins, S.L.: A hybrid grasp with data mining for the maximum diversity problem. In: Blesa, M.J., Blum, C., Roli, A., Sampels, M. (eds.) Hybrid Metaheuristics. Lecture Notes in Computer Science, vol. 3636, pp. 116–127. Springer, Berlin (2005)

    Chapter  Google Scholar 

  • Silva, G.C., Ochi, L.S., Martins, S.L.: Experimental comparison of greedy randomized adaptive search procedures for the maximum diversity problem. In: Experimental and Efficient Algorithms. Lecture Notes in Computer Science, vol. 3059, pp. 498–512. Springer, Berlin (2004)

    Chapter  Google Scholar 

  • Silva, G.C., Andrade, M.R.Q., Ochi, L.S., Martins, S.L., Plastino, A.: New heuristics for the maximum diversity problem. J. Heuristics 13(4), 315–336 (2007)

    Article  Google Scholar 

  • Swierenga, R.P.: Ethnicity in historical perspective. Soc. Sci. 52(1), 31–44 (1977)

    Google Scholar 

  • Wang, J., Zhou, Y., Yin, J., Zhang, Y.: Competitive hopfield network combined with estimation of distribution for maximum diversity problems. IEEE Trans. Syst. Man Cybern., Part B, Cybern. 39(4), 1048–1066 (2009). Special Issue on Cybernetics and Cognitive Informatics

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departamento de Estadística e Investigación Operativa, Universidad de Valencia, Valencia, Spain

    Rafael Martí

  2. Departamento de Ciencias de la Computación, Universidad Rey Juan Carlos, Madrid, Spain

    Micael Gallego, Abraham Duarte & Eduardo G. Pardo

Authors
  1. Rafael Martí
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Micael Gallego
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Abraham Duarte
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Eduardo G. Pardo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rafael Martí.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Martí, R., Gallego, M., Duarte, A. et al. Heuristics and metaheuristics for the maximum diversity problem. J Heuristics 19, 591–615 (2013). https://doi.org/10.1007/s10732-011-9172-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10732-011-9172-4

Keywords

Search

Navigation