The conditional p -dispersion problem
- PDF / 1,406,784 Bytes
- 61 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 235 Views
The conditional p-dispersion problem Marilène Cherkesly1,2,3 · Claudio Contardo1,2,3 Received: 29 August 2019 / Accepted: 24 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract 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 × n, an integer p ≥ 1 and a set Q ⊆ N of cardinality q ≥ 1. The objective is to select a set P ⊂ N \ Q of cardinality p that maximizes the minimal dissimilarity between every pair of selected vertices, i.e., 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. Keywords p-Dispersion · Clustering · Conditional p-dispersion · Exact methods
1 Introduction The conditional p-dispersion problem (c-pDP) is defined on an undirected graph G = (N , E), where N is the set of vertices with cardinality n and E is the set of edges with cardinality n × n. The set of vertices N is composed of the union of two disjoint sets Q and R, where Q is the set of initial located vertices such that |Q| = q ≥ 1, and where R is the set of potential additional locations such that |R| ≥ p ≥ 1. Each edge (i, j) ∈ E is associated with a dissimilarity D(i, j) satisfying D(i, j) = D( j, i) ≥ 0 for every 1 ≤ i, j ≤ n and
B
Claudio Contardo [email protected] Marilène Cherkesly [email protected]
1
Department of Analytics, Operations and Information Technologies, ESG UQAM, Montreal, Canada
2
Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada
3
Group for Research in Decision Analysis (GERAD), Montreal, Canada
123
Journal of Global Optimization
D(i, i) = 0 for every 1 ≤ i ≤ n. We also denote by D = {D(i, j) : (i, j) ∈ E} the dissimilarity matrix. The objective is to select a subset of vertices P ⊆ R of cardinality p such that z(P ∪ Q):= min{D(i, j), i, j ∈ P ∪ Q} is maximum. We denote the associated c-pDP for given input parameters N , Q, D and p as c-pDP(N, Q, D, p). The c-pDP is N P -hard as an instance of the pDP—N P -hard as noticed by Erkut [24]—can be reduced to an equivalent instance of the c-pDP by adding a single vertex u to N with sufficiently large dissimilarity to every other vertex in N , and thus by solving c-pDP(N , Q , D , p), with N = N ∪ {u}, Q = {u} and D built from extending the dissimilarity matrix D by one row and column associated with the new vert
Data Loading...
