Optimization Online


New formulation and resolution method for the p-Center problem

Sourour Elloumi (elloumi***at***cnam.fr)
Martine Labbé (mlabbe***at***smg.ulb.ac.be)
Yves Pochet (ypochet***at***core.ucl.ac.be)

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 he 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 tighter lower bound 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(log_2(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 solution 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 very 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

Category 1: Integer Programming (0-1 Programming )

Category 2: Applications -- Science and Engineering (Facility Planning and Design )

Category 3: Combinatorial Optimization

Citation: ULB-ISRO preprint 2001/03. October 2001. ULB-ISRO- Service Optimisation Bld du Triomphe- CP210/01 B-1050 Brussels Belgium


Entry Submitted: 10/30/2001
Entry Accepted: 10/30/2001
Entry Last Modified: 01/09/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society