An integer programming approach for solving the p-dispersion problem

作者：Sayyady Fatemeh^*; Fathi Yahya

来源：European Journal of Operational Research, 2016, 253(1): 216-225.

DOI：10.1016/j.ejor.2016.02.026

• Location problem
• Max-min diversity
• Integer programming
• Traffic sensor location

Given a collection of n items (elements) and an associated symmetric distance du 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.

• 出版日期2016-8-16