Optimal results and tight bounds for the maximum diversity problem

• Autorzy: Aringhieri R. , Bruglieri M. , Cordone R.
• Języki publikacji: EN

Abstrakty

EN

The Maximum Diversity Problem (MDP) consists in selecting a subset M of given cardinality out of a set N, in such a way that the sum of the pairwise diversities between the elements of M is maximum. New instances for this problem have been recently proposed in the literature and new algorithms are currently under study to solve them. As a reference for future research, this paper provides a collection of all best known results for the classical and the new instances, obtained by applying the state-of-the-art algorithms. Most of these results improve the published ones. In addition, the paper provides for the first time a collection of tight upper bounds, proving that some of these instances have been optimally solved. These bounds have been computed by a branch-and-bound algorithm based on a semidefinite formulation of the Quadratic Knapsack Problem (QKP), which is a generalization of the MDP.

Słowa kluczowe

EN

Maximum Diversity Problem; tabu search

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2009
• Tom: Vol. 34, No. 2
• Strony: 73--85
• Opis fizyczny: Bibliogr. 17 poz.

Twórcy

autor

Aringhieri R.

autor

Bruglieri M.

autor

Cordone R.

• Dipartimento di Informatica, Universita degli Studi di Torino, Corso Svizzera 185, 10149 Torino, Italy,

Bibliografia

• [1] P. M. D. Andrade, A. Plastino, L. S. Ochi, and S. L. Martins. GRASP for the Maximum Diversity Problem. In Proceedings of the Fifth Metaheuristics International Conference (MIC 2003), 2003.
• [2] P. M. D. Andrade, L. S. Plastino, and S. L. Martins. GRASP with path-relinking for the maximum diversity problem. In S. Nikoletseas, editor, Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA 2005), volume 3539 of Lecture Notes in Computer Science, pages 558-569. Springer Berlin / Heidelberg, 2005.
• [3] R. Aringhieri and R. Cordone. Better and faster solutions for the maximum diversity problem. Note del Polo 93, Università degli Studi di Milano, Crema, April 2006.
• [4] R. Aringhieri, R. Cordone, and Y. Melzani. Tabu search vs. GRASP for the maximum diversity problem. 4OR: A Quarterly Journal of Operations Research, 6(l):45-60, 2008.
• [5] B. Borchers. CSDP 5.0 User Guide, September 2005.
• [6] M. Dell’Amico and M. Trubian. Solution of large weighted equicut problems. European Jurnal of Operational Research, 106:500-521, 1998.
• [7] J. J. Dongarra. Performance of various computers using standard linear equations software. Report CS-89-85, Computer Science Department, University of Tennesse, 2008.
• [8] A. Duarte and R. Marti. Tabu search and GRASP for the maximum diversity problem. European Journal of Operational Research, 178(l):71-84, April 2007.
• [9] M. Gallego, A. Duarte, M. Laguna, and R. Martì. Hybrid heuristics for the maximum diversity problem. Technical report, University of Valencia, June 2006.
• [10] J. B. Ghosh. Computational aspects of maximum diversity problem. Operation Research Letters, 19:175-181, 1996.
• [11] F. Glover, G. Hersh, and C. McMillian. Selecting subset of maximum diversity. MS/IS 77-9, University of Colorado at Boulder, 1977.
• [12] C. Helmberg, F.Rendl, and R. Weismantel. A semidefinite programming approach to the quadratic knapsack problem. Journal of Combinatorial Optimization, 4(2):197-215, 2000.
• [13] C. C. Kuo, F. Glover, and K.S. Dhir. Analyzing and modeling the maximum diversity problem by zero-one programming. Decision Science, 24:1171-1185, 1993.
• [14] R. Martì, M. Gallego, and A. Duarte. A branch and bound algorithm for the maximum diversity problem. European Journal of Operational Research. [in press].
• [15] L.F. Santos, M.H. Ribeiro, A. Plastino, and S.L. Martins. A Hybrid GRASP with Data Mining for the Maximum Diversity Problem. In M.J. Blesa, C. Blum, A. Roli, and M. Sampels, editors, Hybrid Metaheuristics, Second International Workshop, volume 3636 of Lecture Notes in Computer Science, pages 116-127. Springer Berlin / Heidelberg, 2005.
• [16] G. C. Silva, M. R. Q. de Andrade, L. S. Ochi, S. L. Martins, and A. Plastino. New heuristics for the maximum diversity problem. Journal of Heuristics, 13:315-336, 2007.
• [17] G. C. Silva, L. S. Ochi, and S. L. Martins. Experimental comparison of greedy randomized adaptive search procedures for the maximum diversity problem. In Proceedings of the 3rd International Workshop on Efficient and Experimental Algorithms (WEA 2004), volume 3059 of Lectures Notes on Computer Science, pages 498-512. Springer Berlin / Heidelberg, 2004.