New formulation and resolution method for the p-center problem
(2004) Informs Journal on Computing — Vol. 16, p. 84-94 (2004)
Files
No attached file found for this publication.
Details
- Authors
- Abstract
- Thep-center problem consists of choosingp facilities among a set ofM possible locations and assigningN 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 boundLB*, obtained by keeping the integrality restrictions on a subset of the variables, can be computed in polynomial time by solving at mostO(log 2( NM)) linear programs, each havingN rows andM columns. We also show that, when the distances satisfy triangle inequalities,LB* is at least one third of the optimal value. Finally, we useLB* in an exact solution method and report extensive computational results on test problems from the literature. For instances where the triangle inequalities are satisfied, our method outperforms the running time of other recent exact methods by an order of magnitude. Moreover, it is the first one to solve large instances of size up toN =M = 1,817.
- Affiliations
Louvain School of Management Operations and Information
Citations
Elloumi, S., Pochet, Y., & Labbé, M. (2004). New formulation and resolution method for the p-center problem. Informs Journal on Computing, 16, 84-94. https://doi.org/10.1287/ijoc.1030.0028 (Original work published 2004)