Covering Location Problems - Location Science - page 101

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 f 0;1;2;3 g
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
d ij D ( 0; if d ij s;
1; if d ij >s;

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 ).

5.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 )usesa
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: