Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6895609 | European Journal of Operational Research | 2016 | 10 Pages |
Abstract
Given a collection of n items (elements) and an associated symmetric distance dij between each pair of items i and j, we seek a subset P of these items (with a given cardinality p) so that the minimum pairwise distance among the selected items is maximized. This problem is known as the max-min diversity problem or the p-dispersion problem, and it is shown to be np-hard. We define a collection of node packing problems associated with each instance of this problem and employ a binary search among these node packing problems to devise an effective procedure for solving the original problem. We employ existing integer programming techniques, i.e., branch-and-bound and strong valid inequalities, to solve these node packing problems. Through a computational experiment we show that this approach can be used to solve relatively large instances of the p-dispersion problem, i.e., instances with more than 1000 items. We also discuss an application of this problem in the context of locating traffic sensors in a highway network.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Fatemeh Sayyady, Yahya Fathi,