Yangming and Jin-Kao Hao. An iterated local search algorithm for the minimum differential dispersion problem. Knowledge-based Systems 125: 26-38, 2017. http://dx.doi.org/10.1016/j.knosys.2017.03.028  


The source code of our proposed ILS_MinDiff algorithm is available in here.

Please make sure that the above paper is cited if you use the code in your research. The software is distributed for academic puposes only. If you wish to use this software for commercial applications, please obtain a permission from Yangming Zhou (zhou.yangming@yahoo.com or yangming@info.univ-angers.fr) or Jin-Kao Hao (jin-kao.hao@univ-angers.fr).

Problem definition

Given a set of n elements separated by a pairwise distance matrix, the minimum differential dispersion problem (Min-Diff DP) aims to identify a subset of m elements (m < n) such that the difference between the maximum sum and the minimum sum of the inter-element distances between any two chosen elements is minimized.

Instance files

MDPLIB provides a comprehensive set of instances which are widely used for testing algorithms for diversity and dispersion problems, and it is available at http://www.optsicom.es/mindiff/. By excluding the small and easy instances, the remaining 190 benchmark instances tested in this work include the following six datasets: SOM-b, GKD-b, GKD-c, MDG-a, MDG-b and MDG-c.