Group for Research in Decision Analysis

G-2019-61

The conditional \(p\)-dispersion problem

and

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