Authors: Amirgaliyeva, Zhazira
Mladenović, Nenad 
Todosijević, Raca 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Solving the maximum min-sum dispersion by alternating formulations of two different problems
Journal: European Journal of Operational Research
Volume: 260
Issue: 2
First page: 444
Last page: 459
Issue Date: 16-Jul-2017
Rank: M21a
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2016.12.039
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.
Keywords: Binary quadratic programing | Dispersion problems | Metaheuristics | Variable formulation search | Variable neighborhood search
Publisher: Elsevier

Show full item record


checked on Jul 13, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.