Covering Location Problems

Abstract

When deciding where to locate facilities (e.g., emergency points where an ambulance will wait for a call) that provide a service, it happens quite often that a customer (e.g., a person) can receive this service only if he/she is under a certain distance to the closest facility (e.g., the ambulance can arrive in less than 7 min at this person’s home). The problems that share this property receive the name of covering problems and have many applications (analysis of markets, archaeology, crew scheduling, emergency services, metallurgy, nature reserve selection, etc.). This chapter surveys the Set Covering Problem, the Maximal Covering Location Problem, and related problems and introduces a general model that has as particular cases the main covering location models. The main theoretical results in this topic as well as exact and heuristic algorithms are reviewed. A Lagrangian approach to solve the general model is detailed and, although the emphasis is on discrete models, some information on continuous covering is provided at the end of the chapter.

1 Introduction

When deciding where to locate facilities (e.g., emergency points where an ambulance will wait for a call) that provide a service, it happens quite often that a customer (e.g., a person) can receive this service only if he/she is under a certain distance to the closest facility (e.g., the ambulance can arrive in less than 7 min at this person’s home). The problems that have this property receive the name of covering problems and, when the previous condition holds, it is said that the customer is covered.

The first mentions to covering problems in literature can be found in Berge (1957) where the problem of finding a minimum cover on a graph is introduced and a theorem that provides an algorithm to find a minimum cover using a matching is stated and in Hakimi (1965) where it must be decided on the minimum number of police patrols required to protect a highway network. However, the problem was mathematically formulated for the first time in the Location area in Toregas et al. (1971), although out of a Location context it had already been formulated in Roth (1969).

In general, there are two types of covering problems: set covering and maximal covering. In a set covering problem (Toregas et al. 1971), the total cost of locating a set of facilities so that every customer is covered must be minimized. Particularly, if all the facilities have the same location cost, this is equivalent to minimize the total number of facilities to be located. A quick analysis of a solution to the set covering problem will usually show that with just a few facilities it is possible to cover an important percentage of the demand and that only by locating a high number full coverage can be achieved. Since locating as many facilities as needed may not be possible (e.g., due to budget constraints), a natural variant is to maximize the number of customers that are covered (or, equivalently, minimize the non-covered customers) by locating a fixed number of facilities. This problem is the maximal covering problem which was introduced in Church and ReVelle (1974).

According to Balas and Padberg (1976), the set covering problem is one of the three special structures in pure integer programming with the most wide-spread applications, together with set partitioning and the traveling salesman problem. Just to mention a few, set covering models have been applied in the following areas: analysis of markets (Storbeck 1988), archaeology (Bell and Church 1985), crew scheduling (Ceria et al. 1998), deployment of emergency services (Toregas et al. 1971; Eaton et al. 1986), mail advertising (Dwyer and Evans 1981), metallurgy (Vasko et al. 1989), nature reserve selection (Church et al. 1996) and Steiner matrices (Feo and Resende 1989).

Due to its importance and the rich literature on this topic, it is not surprising that reviews have been published regularly. The first one is Christofides and Korman (1975), a comparison of five computational methods for the set covering problem. Later, we have Chung (1986) which examines several applications of the maximal covering model to problems that do not belong to the Location field, and ReVelle (1989), a review focused on emergency service. Broader reviews are Schilling et al. (1993), an exhaustive survey on covering models in Location reviewing 96 papers, and Caprara et al. (2000), a comparison of recent algorithms (exact and heuristic) for the set covering problem. Plastria (2002) is an exhaustive review of continuous covering models and it is a perfect complement to this chapter. More recently, we have Berman et al. (2010) which considers some of the latest trends by reviewing gradual coverage, cooperative coverage, and variable radius coverage models, and Snyder (2011) which reviews the seminal covering models plus some extensions. Finally, the most recent survey is Farahani et al. (2012), an exhaustive list of models reviewing more than 150 papers that study covering problems in the area of facility location. More focused as a detailed tutorial than as a proper survey, Daskin (1995) is an excellent introduction to the basic properties of covering models.

At this point, it must be said that there are many different models involving covering and that the goal of this chapter is not to cover them all but to provide an insight on the main models and results on the topic. Particularly, we focus on discrete models because they have received most of the attention in literature. The rest of this chapter is organized as follows: the main models from the literature are obtained in Sect. 5.2 as particular cases of a general model. Section 5.3 summarizes the main theoretical results on two of the main models (Set Covering and Maximal Covering Location). Then, we survey exact (Sect. 5.4) and heuristic (Sect. 5.5) solution methods. Since Lagrangian relaxation technique is widely used for approaching covering models, we extend it to the general model described in Sect. 5.6. Finally, although the focus of this chapter is on discrete models, some information on continuous covering is provided in Sect. 5.7 for the sake of completeness.

2 Models

We will use a general covering model to present as particular cases the main covering location problems in the literature as well as several other basic location problems which can be also considered sophisticated extensions of covering models.

Let J = { 1, …, n} be the set of customers (also called demand points) and let I = { 1, …, m} be the set of potential centers (facilities). Since many applications of covering models come from Location, we will use indistinctively “sites” for customers and potential centers. For each pair (i, j) ∈ I × J, a known constant a _ij  ∈ { 0, 1} represents whether demand point j can be covered (value one) or not (value zero) by a center installed at site i. These constants can be obtained with different procedures depending on the model under consideration as we will see below.

Associated to each i ∈ I, a fixed cost f _i  ≥ 0 has to be paid for opening a center at site i. In some models it is possible to open more than one center at the same site. In this case we assume that the cost of the centers to be opened in i ∈ I is equal (i.e., f _i is the opening cost for all centers to be opened at site i). Each demand point j ∈ J must be covered by at least $b_{j} \in \mathbb{Z}_{0}^{+}$ facilities, where b _j  = 0 if site j does not need to be covered. Besides, a maximum number of $p \in \mathbb{Z}^{+}$ facilities can be opened (note that when the fixed costs of the centers are zero, this maximum number is always reached by some optimal solution).

Non-negative integer variables y _i represent the number of facilities to be opened at site i ∈ I. These are the main location variables and they will be explicitly present in all the particular cases that are obtained from the general model. The maximum number of facilities that can be opened at site i is given by the constant $e_{i} \in \mathbb{Z}^{+}$. Particularly, if e _i  = 1, then y _i  is a binary variable that takes value one if a facility is located at site i (and zero otherwise).

A second family of (binary) variables is w _jk . Here, j belongs to the set of demand points J while k belongs to an index set K = { 1, …, h}, whose meaning will depend on the particular model that is considered. Associated to variables w _jk , fixed costs $g_{\mathit{jk}} \in \mathbb{R}$ are given. These costs g _jk can be negative, representing in this case the profit from w _jk  taking value one. In order to avoid unnecessary complicating constraints in the basic model, without loss of generality, we assume that $g_{j1} \leq g_{j2} \leq \mathop{\ldots } \leq g_{\mathit{jh}}$ for each j ∈ J. Whenever this condition does not hold, it will be explicitly stated.

The mathematical Integer Programming formulation for our general covering model is:

$$\displaystyle\begin{array}{rcl} \mbox{ (COV) Minimize }& & \sum _{i\in I}f_{i}y_{i} +\sum _{j\in J}\sum _{k\in K}g_{\mathit{jk}}w_{\mathit{jk}}{}\end{array}$$

(5.1)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to }& & \sum _{i\in I}y_{i} \leq p,{}\end{array}$$

(5.2)

$$\displaystyle\begin{array}{rcl} & & \sum _{i\in I}a_{\mathit{ij}}y_{i} = b_{j} +\sum _{k\in K}w_{\mathit{jk}}\qquad \forall j \in J,{}\end{array}$$

(5.3)

$$\displaystyle\begin{array}{rcl} & & y_{i} \in \{ 0,1,\ldots,e_{i}\}\qquad \forall i \in I,{}\end{array}$$

(5.4)

$$\displaystyle\begin{array}{rcl} & & w_{\mathit{jk}} \in \{ 0,1\}\qquad \forall j \in J,\forall k \in K.{}\end{array}$$

(5.5)

The objective function (5.1) has two parts. The first sum returns the total fixed cost of opening y _i  facilities at site i ∈ I. The second sum returns the total cost (or profit, if negative) provided by the w-variables that take value one. Constraint (5.2) limits the number of centers to p. Note that all the centers installed at the same site contribute to the sum.

The main constraints in the model are (5.3). For each demand point j ∈ J, the left-hand side of (5.3) measures the number of open facilities which are covering j. This number must be at least equal to the lower bound b _j on the right-hand side, while the sum of w _jk  variables measures the slack in the coverage of j, i.e., the number of centers which are covering j besides the minimum number b _j . Due to the condition that we imposed on the g-values, the w-variables taking value one will be in the first positions, that is, constraints $w_{\mathit{jk}} \geq w_{j,k+1}$, j ∈ J, k ∈ { 1, …, h − 1} are satisfied without including them explicitly in the formulation. In such a way, a cost g _j1 will be paid if demand point j is covered by at least b _j + 1 centers; additional cost g _j2 will be paid if demand point j is covered by at least b _j + 2 centers and so on.

Constraints (5.4) are the integrality constraints for y-variables and impose that at most e _i centers can be installed at site i. Constraints (5.5) state that variables w are binary.

Therefore, model (COV) forces to cover each demand point j with a minimum of b _j  facilities by using at most p facilities while minimizing the location cost of the facilities plus an additional cost (or, instead, minus an additional benefit) associated to the number of facilities which over-cover customers. By giving particular values to the constants in (COV), different models from the literature (and, particularly, all the classical models) are obtained. The details are given next.

Set Covering Problem::

In the Set Covering Problem (SCP) we have that, under the context of emergency center location of Toregas et al. (1971), a _ij  = 1 if the response time or distance d _ij from a center located at i ∈ I when an emergency happens at j ∈ J is under a certain given threshold s (i.e., a _ij  = 1 if and only if d _ij  ≤ s). There is no maximum number of centers to be located (i.e., p = m) and all demand points must be covered at least once ($b_{j} = 1\ \forall j \in J$). The only costs in the objective function are $f_{i} = 1\ \forall i \in I$ because the goal is just to minimize the number of open centers. Therefore, variables w _jk can be removed from the model by replacing the equalities in (5.3) by inequalities “ ≥ ” (equivalently, take $h = m - 1$ and g _jk  = 0 for all j ∈ J, k ∈ K in (COV)). In the SCP, opening more than one facility at the same site is not optimal. Thus, $e_{i} = 1\ \forall i \in I$. Given the special importance of this model, its classical formulation is explicitly shown:

$$\displaystyle\begin{array}{rcl} \mbox{ (SCP) Minimize}& & \sum _{i\in I}y_{i} \\ \mbox{ subject to }& & \sum _{i\in I}a_{\mathit{ij}}y_{i} \geq 1\qquad \forall j \in J, \\ & & y_{i} \in \{ 0,1\}\qquad \forall i \in I. {}\end{array}$$

(5.6)

As an optimization problem, the SCP is a classical problem. The particular case where I = J is the set of nodes of an undirected graph and a _ij  = 1 if and only if edge (i, j) exists, usually called Node Covering Problem, has been deeply studied during the last century. The interested reader can consult the survey by Balinski (1965). Other interesting seminal papers are Norman and Rabin (1959) and Hohn (1955), where the mathematical problem is identified in the context of electronic circuits when analyzing a general way of designing a contact network satisfying given requirements and employing a minimum number of contacts.

Surprisingly, although the SCP is an NP-complete problem (Garey and Johnson 1979), it happens often that the linear relaxation already provides an integer solution. Another important property that must be remarked is that the SCP has usually many different optimal solutions, i.e., sets of centers with the same minimum cardinality which cover all the demand points.

Weighted Set Covering Problem::

The Weighted SCP (WSCP) is a generalization of the SCP where the opening costs f _i can be different from one.

Redundant Covering Location Problem::

The Redundant Covering Location Problem (RCLP) was approached in Daskin and Stern (1981) as an extension of the SCP where the aim is to choose, among the optimal solutions to the SCP, the one which maximizes the number of demand points covered at least twice. Each site can only shelter one center. Again, a _ij  = 1 if and only if d _ij  ≤ s, p = m, $b_{j} = 1\ \forall j \in J$ (because the demand points must be covered at least once), and $e_{i} = 1\ \forall i \in I$. Since we are also interested in knowing whether each demand point j ∈ J is covered or not by a second center (disregarding the number of additional facilities which cover j), only variables w _j1 would be necessary if equalities (5.3) were replaced by inequalities (5.6) as in the SCP discussed above. Alternatively, the RCLP can be obtained as a particular case of (COV) by taking $h = m - 1$, $g_{\mathit{jk}} = 0\ \forall j \in J$, k ≥ 2, and $g_{j1} = -1\ \forall j \in J$. In order to prioritize the minimization of the number of open facilities, we define $f_{i} = n + 1\ \forall i \in I$ as a cost large enough.

Hierarchical Covering Location Problem (HCLP)::

An objective function which allows the simultaneous minimization of the number of facilities that are opened and the maximization of the number of previously existing facilities that are kept (within the minimum total number of facilities) was introduced in Plane and Hendrick (1977) in a paper devoted to the location of fire stations. Values a _ij are equal to one if and only if focal point i can be served by a pumper company at location j in less than the response time specified for site i. They found a major difficulty when using the SCP: this model does not differentiate between those sites that have existing fire stations and those that require the construction of a station. This drawback was fixed by modifying the objective function of the SCP as follows: consider a partition of the set of facilities $I = I_{0} \cup I_{1}$, where I ₀ is the set of existing facilities and I ₁ is the set of potential new facilities. Then, define $f_{i} = 1\ \forall i \in I_{1}$ and $f_{i} = 1-\varepsilon > 0\ \forall i \in I_{0}$ with $\varepsilon$ a small positive amount. This way, the slightly lower cost of the already existing centers makes them more interesting when minimizing the total cost.

Maximal Covering Location Problem::

The Maximal (or Maximum) Covering Location Problem (MCLP) was introduced in Church and ReVelle (1974) and, as it has been explained in the previous section, it entails an important change with regard to the goal of the previous models listed in this section because, since now the number of facilities to be located is limited to a given value p < m, we do not require to cover all the demand but to maximize the covered demand. Then, h = p and $b_{j} = 0\ \forall j \in J$. Again, $e_{i} = 1\ \forall i \in I$ and values a _ij are defined as usual. Since we need to know whether a demand point is covered or not without minding about the number of different facilities that cover it, we avoid that variables y _i and variables w _jk with k ≠ 1 contribute to the objective function (5.1) by fixing their corresponding coefficients to zero, i.e., $f_{i} = 0\ \forall i \in I$ and $g_{\mathit{jk}} = 0\ \forall j \in J$, $\forall k \geq 2$. Besides, we set $g_{j1} = -1$ in order to maximize the number of demand points covered by the open facilities.

An alternative to this model that was proposed in Church and ReVelle (1974) is to combine mandatory covering of some demand points (assume these points are indexed by means of $J_{1} \subset J$) and maximization of the coverage of the remaining points (those in J ∖ J ₁). This situation can also be approached by means of model (COV) by taking h = p, $b_{j} = 1\ \forall j \in J_{1}$, $b_{j} = 0\ \forall j \in J\setminus J_{1}$, $e_{i} = 1\ \forall i \in I$, and $f_{i} = 0\ \forall i \in I$. The g-coefficients are defined as follows: $g_{j1} = -1\ \forall j \in J\setminus J_{1}$, $g_{\mathit{jk}} = 0\ \forall j \in J\setminus J_{1}$, $\forall k \geq 2$, and $g_{\mathit{jk}} = 0\ \forall j \in J_{1}$, $\forall k \in K$. We call this model MCLP’.

Backup Set Covering Problems::

Several models can be grouped under this name. The common idea is to cover the demand points with more than one facility in order to guarantee the coverage in case of either failure or overflow in one or some of the centers (in this sense, the RCLP can be considered a backup problem). There are two natural goals: minimization of the number of open facilities and maximization of the backup coverage. Sometimes this problem has been approached from the point of view of multiobjective optimization as, for example, in Storbeck and Vohra (1988) and model BACOP1 in Hogan and ReVelle (1986). Some other times, both objectives are combined into a unique function as in model BACOP2 in Hogan and ReVelle (1986). Details are provided next.

Coverage of all demand points is not mandatory, and each site can host several facilities. Demands t _j are associated to points j ∈ J. A maximum number of p facilities can be opened (h = p). Values a _ij are obtained as in most of the previous models. A parameter 0 < β < 1 measures the relative importance of covering once or twice each demand point: the smaller β is, the more importance is given to cover each point twice. The goal here is to maximize the demand covered by the facilities and also the demand covered twice, using β to give each objective its relative importance. Taking this into account, we define $f_{i} = 0\ \forall i \in I$, $e_{i} = p\ \forall i \in I$, $g_{\mathit{jk}} = 0\ \forall j \in J$, $\forall k \geq 3$ and $b_{j} = 0\ \forall j \in J$. Variables w _j1 are used to represent whether customer j is covered or not and variables w _j2 are used to check whether j is covered twice or not. We define $g_{j1} = -\beta t_{j}$ and $g_{j2} = -(1-\beta )t_{j}$. Model (COV) is valid when β ≥ 1∕2. When β < 1∕2, constraints $w_{j1} \geq w_{j2}\ \forall j \in J$ must be included to preserve the correct definition of the w-variables.

Batta and Mannur (1990) propose a different criterion for coverage which can also be viewed as a particular case of (COV). Recently, Curtin et al. (2010) developed a backup coverage model in order to locate police patrols, where a priority t _j of crime incident in j ∈ J is known, the number of police patrols is limited to p and a _ij takes value one if, and only if, a patrol located at i can cover a crime incident located at j. The model is called PPAC and is a particular case of (COV) obtained by defining $f_{i} = 0\ \forall i \in I$, h = p, $g_{\mathit{jk}} = -t_{j}\ \forall k$, $b_{j} = 0\ \forall j \in J$, and $e_{i} = 1\ \forall i \in I$.

Maximum Expected Covering Location Problem::

Several covering location models are based on probabilistic principles. One of the most important is the Maximum Expected Covering Location Problem (MECLP) (Daskin 1983), where each facility has a probability of 0 < q < 1 of being busy or failing, independently of any circumstance of the system. Therefore, a demand point covered by ℓ facilities has a probability 1 − q ^ℓ of receiving service. In this model, demands t _j associated to the demand points are also known, and the goal is to locate at most p facilities in such a way that the total expected demand (the sum of the demands of the points times their probability of being serviced) is maximized. Apart from PPAC, this is the first model considered here where all the w-variables really make sense, since it is necessary to know how many facilities are covering each demand point in a given feasible solution. When variable w _jk takes value one, this can be then be re-interpreted as demand point j is covered at least k times. Thus, in order to obtain the right total in the objective function (5.1), we define $g_{\mathit{jk}} = -t_{j}(1 - q)q^{k-1}\ \forall j \in J,\ \forall k \in K$. This way, we have that $\sum _{k=1}^{\ell}g_{\mathit{jk}} = -t_{j}(1 - q^{\ell})$ which is the correct contribution of j to objective function when j is covered by ℓ facilities and $w_{\mathit{jk}} \leq w_{j,k+1}\ \forall k$. But this last inequality is satisfied implicitly because q ^k ≥ q ^k+1 means that coefficients {g _jk } _k are sorted in increasing order for every demand point j. Finally, we define $f_{i} = 0\ \forall i \in I$ and $b_{j} = 0\ \forall j \in J$. It is also natural in this problem to assume that a site can host more than one facility because it could lead to better solutions which is why we define $e_{i} = p\ \forall i \in I$.

Some of the strong assumptions of this model (e.g., servers are independent, servers have the same failure probabilities) have been relaxed several times in the literature. See, for example, Batta et al. (1989) and Galvão et al. (2005).

Probabilistic Location Set Covering Problem::

In order to examine the relationships between the number of facilities being located and their reliability, ReVelle and Hogan (1989a) proposed a Probabilistic Location Set Covering Problem (PLSCP) whose main (and almost unique) difference with the SCP is that values b _j can be greater than one and they are obtained in such a way that the reliability of coverage of each point j ∈ J is guaranteed to be at least equal to a threshold value α. Particularly, b _j  is calculated as the minimum integer number such that

$$\displaystyle{ \left (\frac{F_{j}} {b_{j}} \right )^{b_{j} } \leq 1-\alpha, }$$

where F _j is an average busy fraction associated with point j. Optionally, in this model e _i  can take values greater than one since this can lead to better solutions.

Maximum Availability Location Problem::

Suppose now that a profit u _j associated with each demand point j ∈ J is obtained only if at least ℓ _j  facilities cover it. The total number of facilities is limited, a site can host more than one facility and there is no facility opening cost. The Maximum Availability Location Problem (MALP), first described in ReVelle and Hogan (1989b), is a particular case of (COV) obtained by defining $f_{i} = 0\ \forall i \in I$, $e_{i} = p\ \forall i \in I$, $b_{j} = 0\ \forall j \in J$, and $g_{\mathit{jk}} = 0\ \forall j \in J$, $\forall k\neq \ell_{j}$, whereas $g_{j\ell_{j}} = -u_{j}\ \forall j \in J$. Since now the g-values are not sorted in increasing order, constraints $w_{\mathit{jk}} \geq w_{j,k+1}\ \forall j \in J,\ \forall k < h,$ must be included.

Covering Problem::

The so-called Covering Problem (CP) in Kolen and Tamir (1990) is that of minimizing the costs of opening some facilities plus the penalty costs associated to uncovered demand points. It is obtained from (COV) by defining p = m, $e_{i} = 1\ \forall i \in I$, $b_{j} = 0\ \forall j \in J$, $g_{\mathit{jk}} = 0\ \forall j \in J$, $\forall k \geq 2$ and $g_{j1} = -u_{j}\ \forall j \in J$ where u _j  is the penalty for not covering demand point j. A constant $-\sum _{j\in J}g_{j1}$ must be added to the objective to get the right optimal value. This way, when variable w _j1 takes value one, j is covered and the penalty cost − g _j1 is removed from the objective function.

Minimum Cost Maximal Covering Problem (MCMCP)::

This is the name for the model introduced in Broin and Lowe (1986) whose only difference with regard to CP is that the total number of facilities is limited. They gave a dynamic programming algorithm for solving MCMCP in $O(p^{2}n\min \{m^{2},n^{2}\})$ time when the matrix A = (a _ij ) is totally balanced.

p-Median Problem::

Studied in detail in Chap. 2, the p-Median Problem (pMP) consists in, given a set of n demand points, choosing p of them to locate facilities and allocating each demand point to one of these facilities (which receive the name of medians) in such a way that the total cost be minimum, where the cost of allocating j to i is the distance d _ij between the two points (assuming $d_{\mathit{ii}} = 0\ \forall i$ and d _ij  > 0 in all other cases).

Instead of using the classical formulation for pMP, an artificial set J can be designed in order to get it as a particular case of (COV): for each demand point j, a vector $D_{j} = (D_{1j},\ldots,D_{G_{j}j})$ which is obtained by sorting in increasing order the values in $\{d_{1j},\ldots,d_{nj}\}$ (removing multiplicities):

$$\displaystyle{0 = D_{1j} < D_{2j} < \mathop{\ldots } < D_{G_{j}j} =\max _{1\leq i\leq n}\{d_{\mathit{ij}}\}.}$$

Then define $J =\{ (\ell,j):\ j \in \{ 1,\mathop{\ldots },n\},\ \ell\in \{ 2,\ldots,G_{j}\}\}$ and a _{i, (ℓ, j)} = 1 if and only if $d_{\mathit{ij}} < D_{\ell j}$. Besides, we set $f_{i} = 0\ \forall i \in I$, $e_{i} = 1\ \forall i \in I$, $b_{(j,\ell)} = 0\ \forall (\ell,j) \in J$, and h = p. Coefficients g _(ℓ, j)1 are defined with value $D_{\ell-1,j} - D_{\ell j}$ and $g_{(\ell,j)k} = 0\ \forall k \geq 2$.

With this approach, constraints (5.3) force variables $w_{(j,\ell)1}$ to take value zero if there is no open facility at a distance less than D _{ℓ j} from demand point j and the allocation cost of j is increased from D _ℓ−1, j to D _{ℓ j} , as desired. A constant $\sum _{j=1}^{n}D_{G_{j}j}$ must be added to the objective function to get the right optimal value. This formulation has been very successfully used in García et al. (2011), where a column-and-row generation algorithm is developed to solve very large instances.

Uncapacitated Facility Location Problem::

The problem considered in Chap. 3 (UFLP) and pMP differ in the number of centers which in UFLP is not fixed beforehand, but there is a fixed cost f _i for opening a facility at site i. Therefore, a straightforward modification of these parameters will allow to obtain UFLP as a particular case of (COV). This particular formulation was first proposed in Cornuéjols et al. (1980) and later in Kolen and Tamir (1990).

Table 5.1 summarizes the information about covering models in the literature which have been shown in this chapter to be particular cases of (COV).

Table 5.1 Covering location models derived from (COV)

3 Theoretical Results

The Set Covering Problem is an NP-hard model (Garey and Johnson 1979). As a consequence, much effort has been put into understanding better the structure of this model in order to develop solving algorithms (which are reviewed later in this chapter). This knowledge can be divided mainly into three categories: preprocessing, relation with other problems, and polyhedral analysis.

When solving SCP, all the setup costs f _i can be assumed to be positive because if f _i  ≤ 0 for a certain facility i, then we can fix y _i  = 1, remove this variable from the model and delete any inequality (5.6) that includes y _i . As explained in some early papers (Roth 1969; Lemke et al. 1971; Toregas and Revelle 1972, 1973), it is trivial that if a demand point j can be covered only by a certain facility i ₁ (that is, $\{i \in I\:\ a_{\mathit{ij}} = 1\} =\{ i_{1}\}$), then we can fix $y_{i_{1}} = 1$. We have also some dominance rules: constraint (5.6) for a demand point j ₁ can be removed if there is another demand point j ₂ such that $\{i \in I\:\ a_{\mathit{ij}_{2}} = 1\} \subset \{ i \in I\:\ a_{\mathit{ij}_{1}} = 1\}$, that is, if all the facilities covering demand point j ₂ can cover also j ₁. Similarly, a facility i ₁ which covers a set of demand points which can be all covered by a cheaper facility i ₂ will never be used: if $f_{i_{1}} \geq f_{i_{2}}$ and $\{j \in \ J\:\ a_{i_{1}j} =\ 1\} \subset \{ j \in J\:\ a_{i_{2}j} = 1\}$, then we can fix $y_{i_{1}} = 0$. Sometimes, it is possible to use several facilities to cover all the demand points covered by another facility (Lorena and Lopes 1994): if we assume that the y-columns are sorted in increasing order in cost (with those columns with equal cost sorted in decreasing order in the number of rows that they cover), and we define $\beta _{j} =\min \{ i \in I\:\ a_{\mathit{ij}} = 1\}\ \forall j$ and $H_{i} = \cup _{j\in J}\{\beta _{j}\:\ a_{\mathit{ij}} = 1\}\ \forall i$, then we can fix y _i  = 0 if $\sum _{\ell\in H_{i}}f_{\ell} < f_{i}$. Applying these tests cyclically (i.e., not just once) can lead to substantial reductions in the size of the formulation.

The SCP formulation can be further improved by studying the polyhedral structure of its polytope. Balas (1980) uses disjunctions based on conditional bounds to obtain strong cuts in the form of cover constraints. Particularly, the inequalities introduced in Bellmore and Ratliff (1971) are generalized. Given an inequality of the form $\sum _{j\in J}\alpha _{j}y_{j} \geq \beta$, with $\alpha _{j} \in \{ 0,1\}\ \forall j$ and β a positive integer, some necessary and sufficient conditions using the bipartite incidence graph of the matrix defining the SCP polytope are given in Cornuéjols and Sassano (1989) for this inequality to be a facet. Sassano (1989) studies the properties of this polytope and presents two sequential lifting procedures to obtain valid inequalities and facets. Particularly, it is shown that the SCP polytope is full dimensional if and only if every demand point can be covered by at least two different facilities. It is also characterized when an inequality of the form $\sum _{i\in J_{0}}y_{i} \geq 1$ with J ₀ ⊂ J is a facet. When the polytope is full-dimensional, then the trivial inequality y _j  ≤ 1 is shown to be always a facet, and the trivial inequality y _j  ≥ 0 is a facet if and only if every demand point can be covered by at least two different facilities different from j. Some deeper results on facets and lifting can be found in Nobili and Sassano (1989). Balas and Ng (1989a) characterize facet-defining inequalities for the SCP polytope with right-hand side 2 and coefficients 0, 1 or 2. In Balas and Ng (1989b) it is shown that each of these facets can be obtained using a lifting procedure from an inequality with only three non-zero coefficients that is valid in a lower dimensional polytope. Sánchez-García et al. (1998) do a similar study for the case of facets with coefficients in {0, 1, 2, 3} and right-hand side equal to 3.

The connection of SCP to other classical problems has also been studied in the literature. Balas and Padberg (1976) show how to turn a set partitioning problem into a set covering. In Krarup and Pruzan (1983) it is discussed how SCP can be transformed into a set packing, set partitioning or simple plant location problem. Reciprocal results are given to turn a set partitioning or simple plant location problem into a set covering problem.

Less theoretical results can be found for the Maximal Covering Location Problem, which is known to be NP-hard (Megiddo et al. 1983). In the literature, MCLP has been formulated using other classical models. For example, Church and ReVelle (1976) show the equivalence between MCLP and a certain p-median problem where the distances in this second problem are defined as

$$\displaystyle{d_{\mathit{ij}}' = \left \{\begin{array}{@{}l@{\quad }l@{}} 0,\quad &\mbox{ if }d_{\mathit{ij}} \leq s, \\ 1,\quad &\mbox{ if }d_{\mathit{ij}} > s, \end{array} \right.}$$

with d _ij the distances from the original problem and s is the maximum distance that a demand point can be from the facility that covers it. Another different reformulation is given in Klastorin (1979) where the problem is formulated as a generalized assignment problem by adding some artificial variables.

The Maximal Expected Coverage Location Problem and the Backup Coverage Location Problem are shown in Church and Weaver (1986) to be special cases of the vector assignment p-median problem. Techniques developed for this latter model are used to solve instances of the first two problems. The Capacitated Set Covering Problem and the Capacitated Maximal Covering Location Problem are formulated in Current and Storbeck (1988) as a capacitated plant location problem and a capacitated p-median problem, respectively.

Several technical results on covering problems with special emphasis on trees and matrices in standard greedy form can be found in Kolen and Tamir (1990).

4 Solution Methods

The first exact algorithms for the Set Covering Problem were almost purely enumerative: Lemke et al. (1971) develop a branch-and-bound method that exploits the structure of the SCP formulation and solutions. Later, Etcheberry (1977) uses a branch-and-bound strategy where the branching is done on constraints and not on variables. The lower bounds of the tree are calculated using Lagrangian relaxation instead of the simplex method.

Using cutting planes from conditional bounds, the algorithm proposed in Balas (1980) is exploited in Balas and Ho (1980). This method uses two sets of heuristics: one to find good upper bounds (primal heuristics) and another to obtain lower bounds and cutting planes (dual heuristics). Subgradient optimization is applied to find better lower bounds. This last technique is also used in Beasley (1987) where a branch-and-bound method is proposed whose main elements are a dual ascent procedure and subgradient optimization. This algorithm is improved in Beasley and Jørnsten (1992) by incorporating the heuristic published in Beasley (1990) along with some other enhancements.

Of special interest is Neebe (1988) which solves the problem of calculating for every possible maximum distance the minimum number of facilities that cover all the nodes (instead of solving the set covering problem for a single maximum distance). This approach uses a chain of linear programming relaxations and, after every linear model, some tests are used to obtain an integer solution. Although these tests do not guarantee that an optimal integer solution will be found, the author claims to solve to optimality almost all the instances he considers (up to 100 nodes). Each of the auxiliary problems is solved with a modification of the procedure suggested in Lemke et al. (1971).

Fisher and Kedia (1990) propose an algorithm for a model which includes both set covering and set partitioning constraints. It is an exact branch-and-bound algorithm that uses greedy and 3-opt heuristics applied to the dual problem. Exploiting the use of bounds, Mannino and Sassano (1995) propose a lower bounding procedure and a branch-and-bound scheme to solve set covering problems that appear in Steiner triple systems (a certain matrix structure). Balas and Carrera (1996) develop a procedure applied to a Lagrangian dual problem at each node that combines subgradient optimization with primal and dual heuristics which tighten the upper and lower bounds. These strengthened bounds allow to fix some variables. In general, Lagrangian methods are the most extended and effective methods in the literature. More recently, Avella et al. (2009) propose a cutting plane algorithm where the separation algorithm is solved in an exact way on a subproblem defined by a subset of the original constraints and variables of the set covering problem formulation.

On the contrary, not many exact algorithms have been developed for the Maximal Covering Location Problem. Downs and Camm (1996) obtain a primal solution using the greedy heuristic of Church and ReVelle (1974). They use complementary slackness conditions for the maximal covering problem formulation to obtain a dual feasible solution. This solution is the starting vector of multipliers for the Lagrangian dual problem of MCLP which is solved with subgradient optimization. If an integer solution is not obtained, branch-and-bound is used.

5 Approximate Solution Methods

As it happens with any hard optimization problem, there are more heuristic algorithms than exact methods in the literature. Roth (1969), the first paper to formulate the Set Covering Problem, already proposes a probabilistic heuristic. A random initial solution is selected and then refined using a set of predefined rules based on the concept of λ-optimal cover. This procedure is repeated many times with the hope of finding a good solution. Chvátal (1979) proposes a basic greedy heuristic that selects iteratively the facility with the largest number of nodes covered per unit cost. A bound is established for the worst value of the solution provided by the heuristic. Feo and Resende (1989) develop a probabilistic heuristic for set covering problems arising in Steiner triple systems. It is a non-deterministic variation of a previous deterministic heuristic where randomization is introduced to escape from local minima.

Many more different metaheuristic techniques have been used to approach SCP: surrogate relaxation (Lorena and Lopes 1994), simulated annealing (Jacobs and Brusco 1995; Brusco et al. 1999), genetic algorithms (Al-Sultan et al. 1996; Beasley and Chu 1996). However, as with the exact case, subgradient methods are the most effective. Ceria et al. (1998) use a primal-dual subgradient Lagrangian algorithm to provide information for a later greedy heuristic to decide which variables to fix to one. Caprara et al. (1999) use variable pricing to update the subset of columns that define a core problem in their subgradient optimization heuristic. This is a difference with respect to Ceria et al. (1998) where the core set is not modified. They also improve the way in which the step-size and ascent direction definitions are usually done in subgradient optimization in order to speed up convergence.

For the Maximal Covering Location Problem and similar problems, we can find several heuristics. Already in Church and ReVelle (1974) where the problem is introduced, a greedy heuristic is provided. Later, Daskin (1983) describes a heuristic for the Maximum Expected Covering Location Problem which finds good solutions for all values of q (the probability of a facility not working). It starts with all the facilities located at the node that covers the maximum demand and then considers single node substitutions. For each of the new solutions, it is analyzed if there is an interval where the current best solution is improved. By iterating this procedure, interval [0,1] is partitioned and a heuristic solution is given for each of the resulting subintervals. In MCLP, Galvão and ReVelle (1996) develop a Lagrangian heuristic that uses a vertex interchange heuristic to improve upper bounds. In Galvão et al. (2000), heuristics based on Lagrangian and surrogate relaxations are compared. Here, the relaxed surrogate problem is a binary knapsack problem whose linear relaxation is solved in the heuristic. The authors show that, when the initial set of multipliers is obtained using a dual descent procedure, the performance of the two methods is similar.

Eaton et al. (1986) deal with a hierarchical covering problem where sites with multiple cover are maximized while the number of vehicles is minimized in an application to ambulance deployment in Santo Domingo. Although they proposed two formulations, no solver was available at that moment in the Ministry of Health of Dominican Republic and they then developed a heuristic that minimizes the number of facilities, maximizes multiple coverage and minimizes response time. In their algorithm, they create a cover matrix, then order coverage zones in a list and remove dominated sites iteratively.

A further reason for using heuristics is that aggregation is used to reduce the size of the problem so that larger size instances can be tackled. Daskin et al. (1989) study the effect of node aggregation for MCLP. Three aggregation schemes are tested based on relative demands on the disaggregate nodes, distances between the disaggregate nodes and a mix of both. The first and the third methods are shown to perform much better than the second. In Current and Schilling (1990) three rules are proposed to reduce the aggregation error in SCP and MCLP.

6 Lagrangian Relaxation

Among the many different methods that have been developed in the literature for covering models, we highlight here Lagrangian Relaxation (LR) for several reasons. First, LR can be used as a heuristic method but can additionally provide good lower bounds which can be embedded into a branch-and-bound framework to develop an exact method. Second, as shown in Sects. 5.4 and 5.5, LR has been widely used in covering problems. Third, it can be designed for the general model (COV) and then used on any particular case without loss of accuracy. And, finally, LR usually produces very good results in a reasonable amount of computational time. Readers not familiarized with this technique are referred to Guignard (2003).

In what follows, we apply LR to model (COV) by making the natural choice of relaxing constraints (5.3). Since the non-relaxed linear constraints (5.2) and $y_{i} \leq e_{i}\ \forall i \in I$ give rise to a totally unimodular coefficients matrix, lower bounds produced by means of LR will not be greater than lower bounds produced by the usual linear relaxation. A Lagrangian multiplier $v_{j} \in \mathbb{R}$ associated to each constraint in (5.3), unrestricted in sign, will be used. So, a family of Lagrangian relaxed subproblems is obtained with objective functions

$$\displaystyle\begin{array}{rcl} & & \sum _{i\in I}f_{i}y_{i} +\sum _{j\in J}\sum _{k\in K}g_{\mathit{jk}}w_{\mathit{jk}} +\sum _{j\in J}v_{j}\left (\sum _{i\in I}a_{\mathit{ij}}y_{i} - b_{j} -\sum _{k\in K}w_{\mathit{jk}}\right ) = {}\\ & & \quad \sum _{i\in I}\left (f_{i} +\sum _{j\in J}v_{j}a_{\mathit{ij}}\right )y_{i} +\sum _{j\in J}\sum _{k\in K}\left (g_{\mathit{jk}} - v_{j}\right )w_{\mathit{jk}} -\sum _{j\in J}v_{j}b_{j}. {}\\ \end{array}$$

By solving

$$\displaystyle\begin{array}{rcl} & & (\mathrm{COVLR}(v))\ \min \sum _{i\in I}\left (f_{i} +\sum _{j\in J}v_{j}a_{\mathit{ij}}\right )y_{i} +\sum _{j\in J}\sum _{k\in K}\left (g_{\mathit{jk}} - v_{j}\right )w_{\mathit{jk}} {}\\ & & \qquad \qquad \qquad \mbox{ s.t. }\qquad \qquad \qquad \quad \mbox{ (5.2)},\mbox{ (5.4)},\mbox{ (5.5)}, {}\\ \end{array}$$

and then adding constant $-\sum _{j\in J}v_{j}b_{j}$, we will get a lower bound on the objective value of (COV) when the set of multipliers is $v = (v_{1},\ldots,v_{n})$.

Let now $(y^{{\ast}}(v),w^{{\ast}}(v))$ be an optimal solution to (COVLR(v)). Problem (COVLR(v)) splits into

$$\displaystyle\begin{array}{rcl} & & (\mathrm{COVLRy}(v))\ \min \sum _{i\in I}\left (f_{i} +\sum _{j\in J}v_{j}a_{\mathit{ij}}\right )y_{i} {}\\ & & \qquad \qquad \qquad \quad \mbox{ s.t. }\qquad \quad \mbox{ (5.2)},\mbox{ (5.4)}, {}\\ \end{array}$$

and

$$\displaystyle\begin{array}{rcl} & & (\mathrm{COVLRw}(v))\ \min \sum _{j\in J}\sum _{k\in K}\left (g_{\mathit{jk}} - v_{j}\right )w_{\mathit{jk}} {}\\ & & \qquad \qquad \qquad\quad\mbox{ s.t. } \qquad \qquad \mbox{ (5.5)}. {}\\ \end{array}$$

(COVLRw(v)) can be easily solved by inspection:

$$\displaystyle{w_{\mathit{jk}}^{{\ast}}(v) = 1\ \Leftrightarrow g_{\mathit{ jk}} \leq v_{j}\ \ \ \forall j \in J,\forall k \in K.}$$

If, as in most of the models that we considered, g _jk -values are sorted in increasing order for each j ∈ J, and assuming that $v_{j} \in (g_{j\ell_{j}},g_{j,\ell_{j}+1}]$, then the optimal solution to (COVLRw(v)) will look like as follows:

$$\displaystyle{w_{j1}^{{\ast}}(v) = \mathop{\ldots } = w_{ j\ell_{j}}^{{\ast}}(v) = 1,\ w_{ j,\ell_{j}+1}^{{\ast}}(v) = \mathop{\ldots } = w_{\mathit{ jh}}^{{\ast}}(v) = 0.}$$

The corresponding optimal value will be $v(\mathrm{COVLRw}(v)) =\sum _{j\in J}(\sum _{k=1}^{\ell_{j}}g_{\mathit{jk}} -\ell_{j}v_{j})$.

Regarding (COVLRy(v)), we define $f'_{i}:= f_{i} +\sum _{j\in J}v_{j}a_{\mathit{ij}}\ \forall i \in I$ and we sort these values in increasing order:

$$\displaystyle{f'_{(1)} \leq \mathop{\ldots } \leq f'_{(t)} \leq 0 \leq f'_{(t+1)} \leq \mathop{\ldots } \leq f'_{(n)}.}$$

An optimal solution to (COVLRy(v)) is recursively obtained by taking

$$\displaystyle{y_{(i)}^{{\ast}}(v) = \left \{\begin{array}{ll} e_{(i)} & \mbox{ if }\sum _{\ell=1}^{i-1}y_{ (\ell)}^{{\ast}}(v) \leq p - e_{ (i)}, \\ p -\sum _{\ell=1}^{i-1}y_{(\ell)}^{{\ast}}(v)&\mbox{ if }\sum _{\ell=1}^{i-1}y_{(\ell)}^{{\ast}}(v) > p - e_{(i)}, \end{array} \right.}$$

i = 1, …t, and $y_{(i)}^{{\ast}}(v) = 0,\ i = t + 1,\mathop{\ldots },n$. Assuming that $\sum _{\ell=1}^{i'}e_{(\ell)} \leq p <\sum _{ \ell=1}^{i'+1}e_{(\ell)}$, with i′ ≤ t, we then have that

$$\displaystyle\begin{array}{rcl} \mbox{ v(COVLRy($v$))}& =& \sum _{i=1}^{i'-1}e_{ (i)}\left (f_{(i)} +\sum _{j\in J}v_{j}a_{(i)j}\right ) {}\\ & & +\left (p -\sum _{i=1}^{i'}e_{ (i)}\right )\left (f_{(i')} +\sum _{j\in J}v_{j}a_{(i')j}\right ). {}\\ \end{array}$$

A suitable set of Lagrangian multipliers v must be chosen so that v(COVLR(v)) provides a good lower bound on the optimal value of (COV). This can be achieved by means of ascent procedures which iteratively modify v, like subgradient algorithms or tailored dual ascent algorithms. Good feasible solutions (and the corresponding upper bounds) can be generated from good sets of multipliers as follows. Consider any optimal solution to the relaxed problem given by $(y^{{\ast}}(v),w^{{\ast}}(v))$. We relax the notation by calling simply y ^∗ the optimal values of the y-variables. Once these have been determined, the best values which the w-variables can take are obtained by solving for each j ∈ J the subproblem

$$\displaystyle\begin{array}{rcl} \mbox{ (COV)$_{j}$ Minimize }& & \sum _{k\in K}g_{\mathit{jk}}w_{\mathit{jk}} {}\\ \mbox{ subject to }& & \sum _{k\in K}w_{\mathit{jk}} =\sum _{i\in I}a_{\mathit{ij}}y_{i}^{{\ast}}- b_{ j}, {}\\ & & w_{\mathit{jk}} \in \{ 0,1\}\qquad \forall k \in K. {}\\ \end{array}$$

If $\sum _{i\in I}a_{\mathit{ij}}y_{i}^{{\ast}}- b_{j} < 0$, the subproblem is infeasible. Otherwise, assuming that $\sum _{i\in I}a_{\mathit{ij}}y_{i}^{{\ast}}- b_{j} \leq h$ (note that in general h is taken large enough) and sorting g-values in increasing order, the optimal solution to (COV) _j can be obtained just by making the first $\sum _{i\in I}a_{\mathit{ij}}y_{i}^{{\ast}}- b_{j}$ w-variables equal to one, that is,

$$\displaystyle{\mbox{ v(COV)}_{j} =\sum _{ k=1}^{\sum _{i\in I}a_{\mathit{ij}}y_{i}^{{\ast}}-b_{ j}}g_{\mathit{jk}}.}$$

7 Continuous Covering Location Problems

When speaking about continuous covering, it means that the set of candidates where facilities can be located is not discrete but a whole (continuous) space. Because of the nature of these problems, most of them are in the plane or, if height/depth is relevant, in the 3D-space. Besides, most of the applications locate one single facility because these models are already difficult enough.

Analogous to the discrete Set Covering Problem, the continuous Minimal Covering Circle Problem (MCCP) consists in finding the smallest circle in the plane that contains all the points of a given set which need to be covered. The center of this circle is the optimal site. This is a very old problem which according to Plastria (2002) was studied in the nineteenth century, but may have been introduced even earlier. One of the main properties of the solution to MCCP is that there are always at least two demand points on the border of the minimal circle. Although several algorithms to solve this problem have been proposed over time, the best known is the method published in Elzinga and Hearn (1972) for the case of Euclidean distances.

When the radius of the circle is fixed, it may be not large enough to cover all the demand points and, as in the discrete Maximal Covering Location Problem, the objective is now to cover as much demand as possible. These maximal covering problems have usually multiple solutions, maybe even a region of optimal solutions, and this region may not even be convex (see Plastria 2002). However, it can be proved that there is an optimal solution which is either a demand point or an intersection point of two circles centered at demand points (see Drezner 1981 and Chazelle and Lee 1986 for details on algorithms). There is a similar property when the facilities can be located on any part of a network (Church and Meadows 1979). Church (1984) shows an analogous property for planar maximal covering problems with Euclidean or rectilinear distances.

More recently, Drezner et al. (2004) studied a gradual covering problem with Euclidean distances where a finite set of points needs to be covered with one single facility. If the facility can be located anywhere on the plane and the total cost of non-covered points is minimized, then the solution is in the convex hull of the demand points.

8 Conclusions

In this chapter we have provided an overview on covering problems with a special emphasis on discrete models. Instead of providing a list of the many covering models that can be found in the literature, we have focused on detailing those that are considered to be more relevant because of the attention received in the literature in the last decades. Moreover, we show that many of the models discussed in this review can be seen as particular cases of a general covering model that we introduce here. As far as we know, this is the first attempt to develop such a unified approach for the study of set covering problems.

Having set covering problems received so much attention in the literature, it seems that the number of theoretical results is too small. These results reduce basically to some preprocessing rules and to the study of some facets. And none of them has been used to develop an algorithm that can be considered to be a major breakthrough in the area. Therefore, future research should try to make better use of these results or obtain new theoretical properties for these problems. Particularly, developing exact methods for covering models that are not the SCP seems highly desirable.