2016 journal article

An integer programming approach for solving the p-dispersion problem

*EUROPEAN JOURNAL OF OPERATIONAL RESEARCH*, *253*(1), 216–225.

author keywords: Location problem; Max-min diversity; Integer programming; Traffic sensor location

TL;DR:
This work defines a collection of node packing problems associated with each instance of this problem and employs existing integer programming techniques, i.e., branch-and-bound and strong valid inequalities, to solve these nodes packing problems.
(via Semantic Scholar)

Source: Web Of Science

Added: August 6, 2018

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.