The conditional p-dispersion problem

We introduce the conditional p-dispersion problem (c-pDP), an incremental variant of the p-dispersion problem (pDP). In the c-pDP, one is given a set N of n points, a symmetric dissimilarity matrix D of dimensions $$n\times n$$ n × n , an integer $$p\ge 1$$ p ≥ 1 and a set $$Q\subseteq N$$ Q ⊆ N of cardinality $$q\ge 1$$ q ≥ 1 . The objective is to select a set $$P\subset N\setminus Q$$ P ⊂ N \ Q of cardinality p that maximizes the minimal dissimilarity between every pair of selected vertices, i.e., $$z(P\cup Q) {:}{=}\min \{D(i, j), i, j\in P\cup Q\}$$ z ( P ∪ Q ) : = min { D ( i , j ) , i , j ∈ P ∪ Q } . The set Q may model a predefined subset of preferences or hard location constraints in incremental network design. We adapt the state-of-the-art algorithm for the pDP to the c-pDP and include an ad-hoc acceleration mechanism designed to leverage the information provided by the set Q to further reduce the size of the problem instance. We perform exhaustive computational experiments and show that the proposed acceleration mechanism helps reduce the total computational time by a factor of five on average. We also assess the scalability of the algorithm and derive sensitivity analyses.