Back

# The conditional $$p$$-dispersion problem

## Marilène Cherkesly and Claudio Contardo

BibTeX reference

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$$, an integer $$p\geq 1$$ and a set $$Q\subseteq N$$ of cardinality $$q\geq 1$$. The objective is to select a set $$P\subset N\setminus 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\}$$. 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 ad-hoc acceleration mechanisms designed to take advantage of the information provided by the set $$Q$$. We perform exhaustive computational experiments and show that the proposed acceleration mechanisms help reduce the total computational time by a large margin. We also assess the scalability of the algorithm and derive managerial insights regarding the value of building a network from scratch compared to an incremental design.

, 40 pages

### Publication

and
Journal of Global Optimization, 81, 23–83, 2021 BibTeX reference