Given a set N, a pairwise distance function d and an integer number m, the Dispersion Problems (DPs) require to extract from N a subset M of cardinality m, so as to optimize a suitable function of the distances between the elements in M. Different functions give rise to a whole family of combinatorial optimization problems. In particular, the max-sum DP and the max-min DP have received strong attention in the literature. Other problems (e.g., the max-minsum DP and the min-diffsum DP) have been recently proposed with the aim to model the optimization of equity requirements, as opposed to that of more classical efficiency requirements. Building on the main ideas which underly some state-of-the-art methods for the max-sum DP and the max-min DP, this work proposes some constructive procedures and a Tabu Search algorithm for the new problems. In particular, we investigate the extension to the new context of key features such as initialization, tenure management and diversification mechanisms. The computational experiments show that the algorithms applying these ideas perform effectively on the publicly available benchmarks, but also that there are some interesting differences with respect to the DPs more studied in the literature. As a result of this investigation, we also provide optimal results and bounds as a useful reference for further studies.

Construction and improvement algorithms for dispersion problems / R. Aringhieri, R. Cordone, A. Grosso. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 242:1(2015 Apr 01), pp. 21-33. [10.1016/j.ejor.2014.09.058]

Construction and improvement algorithms for dispersion problems

R. Cordone
Secondo
;
2015

Abstract

Given a set N, a pairwise distance function d and an integer number m, the Dispersion Problems (DPs) require to extract from N a subset M of cardinality m, so as to optimize a suitable function of the distances between the elements in M. Different functions give rise to a whole family of combinatorial optimization problems. In particular, the max-sum DP and the max-min DP have received strong attention in the literature. Other problems (e.g., the max-minsum DP and the min-diffsum DP) have been recently proposed with the aim to model the optimization of equity requirements, as opposed to that of more classical efficiency requirements. Building on the main ideas which underly some state-of-the-art methods for the max-sum DP and the max-min DP, this work proposes some constructive procedures and a Tabu Search algorithm for the new problems. In particular, we investigate the extension to the new context of key features such as initialization, tenure management and diversification mechanisms. The computational experiments show that the algorithms applying these ideas perform effectively on the publicly available benchmarks, but also that there are some interesting differences with respect to the DPs more studied in the literature. As a result of this investigation, we also provide optimal results and bounds as a useful reference for further studies.
Combinatorial optimization; Dispersion problems; Binary quadratic programming; Tabu Search
Settore MAT/09 - Ricerca Operativa
Settore INF/01 - Informatica
1-apr-2015
Article (author)
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0377221714007978-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 562.83 kB
Formato Adobe PDF
562.83 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/282974
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 14
social impact