An integer programming approach for solving the p -dispersion problem

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.