Covering Location Problems - Location Science - page 94

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 D 1 if the
response time or distance d ij from a center located at i 2 I when an emergency
happens at j 2 J is under a certain given threshold s (i.e., a ij D 1 if and only if
d ij s). There is no maximum number of centers to be located (i.e., p D m)and
all demand points must be covered at least once (b j D 1 8 j 2 J). The only costs
in the objective function are f i D 1 8 i 2 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 D m 1 and g jk D 0 for all j 2 J, k 2 K in (COV)). In the SCP, opening
more than one facility at the same site is not optimal. Thus, e i D 1 8 i 2 I.
Given the special importance of this model, its classical formulation is explicitly
shown:

(SCP) Minimize X
i2I

y i

subject to X
i2I

a ij y i 1 8 j 2 J; (5.6)

y i 2f 0;1 g i 2 I:

As an optimization problem, the SCP is a classical problem. The particular case
where I D J is the set of nodes of an undirected graph and a ij D 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 D 1 if and only if d ij s,
p D m, b j D 1 8 j 2 J (because the demand points must be covered at least