### G-2019-61

# The conditional \(p\)-dispersion problem

## Marilène Cherkesly and Claudio Contardo

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.

Published **August 2019**
,
40 pages