An integer programming approach for solving the p-dispersion problem

Fatemeh Sayyady

doi:10.1016/j.ejor.2016.02.026

Return

An integer programming approach for solving the p-dispersion problem

2016-08-01

PRE

Fatemeh Sayyady *

Yahya Fathi

DOI：10.1016/j.ejor.2016.02.026

Original

Original request for help

Save

Abstract

En 中文

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. (C) 2016 Elsevier B.V. All rights reserved.

Keywords:

Location problem

Max-min diversity

Integer programming

Traffic sensor location

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.