The p-Center Problem

First of all, the \(p\)-center problem holds a special place for me since it was the very first real research problem I worked on (My Journey for more information).

What is the p-Center Problem?

The $p$-center problem is a classical problem in operations research and combinatorial optimization, belonging to the family of location problems. This problem is known to be NP-complete for decision problems and NP-hard for optimization problems. It is particularly relevant in contexts where the maximum response time or maximum distance is critical, such as the location of emergency services (hospitals, fire stations, ambulances), military facilities, or distribution centers.

What does it consist of?

Consider a geographical map of a region with many towns. In our problem, we refer to these towns as points, nodes, or clients. These towns are connected by roads, which we call edges (or arcs if one-way), weighted by the distance between towns. We want to place a certain number of centers in the region. These centers can represent hospitals, fire stations, electric charging stations, or warehouses.

For simplicity, let’s assume each town is a candidate location for a hospital. However, for economic reasons, we cannot build a hospital in every town. The region’s budget only allows us to build $p$ centers. The question is then: How can we place the \(p\) hospitals in such a way that the maximum distance between towns and their nearest hospital is minimized?

Mathematical Definition

We model the region as a graph \(G=(N,E)\), where \(N\) is the set of nodes (\(n=card(N)\)) representing the towns. The set of edges \(E\) represents the connections between towns, each with a weight corresponding to distance or travel cost. The shortest distance between two towns \(i\) and \(j\) is denoted by \(d_{ij}\).

The objective is to find the placement of \(p\) centers in the towns such that the maximum distance between towns and their nearest hospital is minimized, while respecting the constraints.

Daskin

We define:

\[z=\max_{i \in N} \{ d_{ik} ; k \text{ being the nearest center to } i\}\]

as the maximum distance between towns and their nearest hospital.

The problem can be formulated as a Mixed Integer Program (MIP), based on Daskin’s model. We define the following decision variables:

\[\begin{align*} x_{ij} &= \begin{cases} 1 & \text{if } j \text{ is the center assigned to node } i \\ 0 & \text{otherwise, } \forall i,j \in N \end{cases} \\ y_{j} &= \begin{cases} 1 & \text{if a center is located at node } j \\ 0 & \text{otherwise, } \forall j \in N \end{cases} \end{align*}\]

Using these decision variables, we obtain the following model:

\[\begin{flalign} \mbox{Min}&~ z \label{obj1}&\\ \nonumber s.c~ \\ &\sum_{j\in N} y_j \leq p \label{c1}&\\ & \sum_{j\in N} x_{ij} = 1 & \forall i \in N, \label{c2} &\\ & x_{ij} \leq y_j & \forall i,j \in N,\label{c3}\\ & \sum_{j\in N} d_{ij} \cdot x_{ij} \leq z & \forall i \in N, \label{c4}\\ & x_{ij} \in \{0,1\} & \forall i,j \in N, \label{c5}\\ & y_{j} \in \{0,1\} & \forall j \in N\label{c6}\\ & z \geq 0 & \label{c7} \end{flalign}\]

The objective function $\eqref{obj1}$ seeks to minimize the largest distance between towns and their nearest hospital. Constraint $\eqref{c1}$ enforces that at most \(p\) centers can be opened. Constraint $\eqref{c2}$ ensures each town is assigned to exactly one center. Constraint $\eqref{c3}$ forces assignments only to open hospitals. Constraint $\eqref{c4}$ sets the upper bound for the distance between towns and their nearest hospital.

Elloumi et al.

This formulation is certainly one of the most basic and straightforward for the problem. Although it dates back to 1995, it remains relatively powerful, even though improvements have been proposed, notably by Elloumi et al. in 2004. This improved formulation uses the fact that the optimal objective value of the problem is restricted to a finite set of distances. They introduced new decision variables $z^k$ with \(k=2,...,K\), where \(z^k=0\) if all nodes can be covered by \(p\) centers within a radius of \(r_{k-1}\), and \(z^k=1\) otherwise. In this formulation, the assignment variables \(x_{ij}\) are no longer required.

The improved formulation is as follows:

\[\begin{flalign} \mbox{Min}&~ r_1 + \sum_{k=2}^K (r_k - r_{k-1}) z^k \label{obj2}&\\ \nonumber s.c~ \eqref{c1}, \eqref{c6}\\ & \sum_{j\in N} y_j \geq 1 \label{c8}&\\ & z^k + \sum_{\substack{j\in N\\ d_{ij} < r_k}} y_j \geq 1 & \forall i \in N, k=2,...,K \label{c9}&\\ & z^k \in \{0,1\}& k=2,...,K \label{c10}&\\ \end{flalign}\]

Constraint $\eqref{c8}$ eliminates solutions with no open centers. The combination of $\eqref{c9}$ and the objective function $\eqref{obj2}$ ensures that all towns are served by the nearest possible hospital.

Calik and Tansel

Finally, in 2013, Calik and Tansel proposed a new formulation of the problem. They associated a binary variable \(u_k\) with \(r_k\), for each \(k\in \{ 1, ..., K \}\). In particular, \(u_k\) is equal to 1 if \(r_k\) is selected as the optimal value and 0 otherwise. Initially, they proposed the following formulation :

\[\begin{flalign} \mbox{Min}&~ \sum_{k=1}^{K} r_k \cdot u_k \label{obj3}&\\ \nonumber s.c~ \eqref{c1}, \eqref{c6}\\ & \sum_{j:d_{ji} \leq r_k} y_i \geq u_k & \forall i \in N, k=1,...,K, \label{c11}&\\ & \sum_{k=1}^K u_k = 1 & \label{c12}&\\ & u_k \in \{0,1\}& k=1,...,K \label{c13}&\\ \end{flalign}\]