Discrete Diversity, Dispersion, and Coverage Subset Selection
Solves discrete location objectives on a distance matrix or
Euclidean coordinate set. The Max-Min Diversity (MMDP / p-dispersion)
objective, which maximizes the minimum pairwise distance within a selection
of k items, is solved by farthest-first selection (Gonzalez 1985)
; the DropAdd tabu-search heuristic
(Porumbel, Hao & Glover 2011) , GRASP with
path-relinking (Resende, Marti, Gallego & Duarte 2010)
, and an exact node-packing integer program
(Sayyady & Fathi 2016) .
The Max-Mean Dispersion objective, which selects a subset of
unrestricted size maximising the sum of its pairwise distances divided by the
number of selected elements, is solved by reinforcement-learning-guided tabu
search (Nijimbere et al. 2020) .
The discrete k-centre (min-max covering / facility location) objective,
which chooses k centres to minimise the largest distance from any point to
its nearest centre, is solved via the CDSh heuristic (Garcia-Diaz et al.
2017 , 2019 ),
and an exact minimum-cover integer program. The maximum-entropy (maxdet)
objective, which maximises the log-determinant of a similarity kernel built
from the distances (Shewry & Wynn 1987 ; the
mode of a determinantal point process, Kulesza & Taskar 2012
), is solved by greedy pivoted-Cholesky selection and,
for small instances, exact enumeration.