Skip to Main content Skip to Navigation
Journal articles

Solving the maximum min-sum dispersion by alternating formulations of two different problems

Abstract : The maximum min-sum dispersion problem aims to maximize the minimum accumulative dispersion among the chosen elements. It is known to be strongly NP-hard problem. In this paper we present heuristic where the objective functions of two different problems are shifted within variable neighborhood search framework. Though this heuristic can be seen as an extended variant of variable formulation search approach that takes into account alternative formulations of one problem, the important difference is that it allows using alternative formulations of more than one optimization problem. Here we use one alternative formulation that is of max-sum type of the originally max–min type maximum diversity problem. Computational experiments on the benchmark instances used in the literature show that the suggested approach improves the best known results for most instances in a shorter computing time.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03402282
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 3:51:36 PM
Last modification on : Wednesday, November 3, 2021 - 5:22:06 AM

Identifiers

Collections

Citation

Zhazira Amirgaliyeva, Nenad Mladenovic, Raca Todosijević, Dragan Urošević. Solving the maximum min-sum dispersion by alternating formulations of two different problems. European Journal of Operational Research, Elsevier, 2017, 260 (2), pp.444-459. ⟨10.1016/j.ejor.2016.12.039⟩. ⟨hal-03402282⟩

Share

Metrics

Record views

3