Covering Location Problems - Location Science - page 100

5.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 D 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 1 (that
is, f i 2 I W a ij D 1 gDf i 1 g ), then we can fix y i 1 D 1.Wehavealsosome
dominance rules: constraint ( 5.6 ) for a demand point j 1 can be removed if there is
another demand point j 2 such that f i 2 I W a ij 2 D 1 gf i 2 I W a ij 1 D 1 g ,thatis,
if all the facilities covering demand point j 2 can cover also j 1 . Similarly, a facility i 1
which covers a set of demand points which can be all covered by a cheaper facility i 2
will never be used: if f i 1 f i 2 and f j 2 J W a i 1 j D 1 gf j 2 J W a i 2 j D 1 g ,
then we can fix y i 1 D 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 LJ j D min f i 2 I W a ij D 1 g8 j and H i D[ j2J f LJ j W a ij D 1 g8 i,

then we can fix y i D 0 if P `2H i f ` <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 P j2J Ǜ j y j LJ, with Ǜ j 2f 0;1 g8 j and LJ 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 P i2J 0 y i 1 with J 0 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