A new compact formulation for the discrete p-dispersion problem

David Sayah and Stefan Irnich

European Journal of Operational Research, 2017, vol. 256, issue 1, 62-67

Abstract: This paper addresses the discrete p-dispersion problem (PDP) which is about selecting p facilities from a given set of candidates in such a way that the minimum distance between selected facilities is maximized. We propose a new compact formulation for this problem. In addition, we discuss two simple enhancements of the new formulation: Simple bounds on the optimal distance can be exploited to reduce the size and to increase the tightness of the model at a relatively low cost of additional computation time. Moreover, the new formulation can be further strengthened by adding valid inequalities. We present a computational study carried out over a set of large-scale test instances in order to compare the new formulation against a standard mixed-integer programming model of the PDP, a line search, and a binary search. Our numerical results indicate that the new formulation in combination with the simple bounds is solved to optimality by an out-of-the-box mixed-integer programming solver in 34 out of 40 instances, while this is neither possible with the standard model nor with the search procedures. For instances in which the line and binary search fail to find a provably optimal solution, we achieve this by adding cuts to our enhanced formulation. With the new techniques we are able to exactly solve instances of one order of magnitude larger than previously solved in the literature.

Keywords: Facility location; Dispersion problems; Max–min objective; Integer programming (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171630457X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:256:y:2017:i:1:p:62-67

DOI: 10.1016/j.ejor.2016.06.036

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().