New formulation and resolution method for the p-center problem

Sourour Elloumi, Martine Labbé and Yves Pochet

No 2001053, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The p-Center problem consists in locating p facilities among a set of M possible locations and assigning N clients to them in order to minimize the maximum distance between a client and the facility to which it is allocated. We present a new integer linear programming formulation for this Min-Max problem with a polynomial number of variables and constraints, and show that its LP-relaxation provides a lower bound tighter than the classical one. Moreover, we show that an even better lower bound LB*, obtained by keeping the integrality restrictions on a subset of the variables, can be computed in polynomial time by solving at most O(log2(NM))linear programs, each made of N rows and M columns. We also show that, when the distances satisfy triangle inequalities, LB* is at least equal to half of the optimal value. Finally, we use LB* as a starting point in an exact solution method and report extensive computational results on test problems from the literature. For Euclidean instances, our method outperforms the runtime of other recent exact methods by an order of magnitude. Moreover, it is the first one to solve large instances of size up to N = M = 1817.

Keywords: min-max objective; facility location; p-center; mathematical programming (search for similar items in EconPapers)
Date: 2001-12
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2001.html (text/html)

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:cor:louvco:2001053

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().