Fixed-Charge Facility Location Problems - Location Science - page 65

3.5 Polyhedral Analysis of the UFLP

This section concentrates on the polyhedral analysis of the UFLP. We assume the
reader is familiar with the basic polyhedral concepts (an exposition can be found, for
instance in Nemhauser and Wolsey 1988 ). Although any UFLP formulation can be
analyzed from a polyhedral perspective, we focus on the set packing formulation for
the UFLP, because it is the one that has received more attention from a polyhedral
point of view. An alternative analysis to the one we develop next, based on a set
partitioning UFLP formulation, can be found in Guignard ( 1980 ).
As indicated in Sect. 3.2 facility location problems can also be modeled as
maximization problems in which the expression of the objective function is ( 3.17 ).
In the case of the UFLP such a formulation can be easily transformed into a set
packing one by doing the change of variables N y i D 1 y i , i 2 I;i.e. N y i D 1
if and only if facility i is not opened. The objective function can be rewritten in
terms of the new variables as P i2I f i C P i2I f i N y i C P i2I P j2J p ij x ij , whose

maximization reduces to maximizing the objective P i2I f i N y i C P i2I P j2J p ij x ij
within the appropriate domain. Hence, a set packing formulation for the UFLP is
. KUFLP / maximize z D X
i2I

f i N y i C X
i2I

X

p ij x ij (3.62)

j2J

subject to X
i2I

x ij 1j 2 J (3.63)

x ij C y i 1i 2 I; 8 j 2 J (3.64)

x ij 2f 0;1 g i 2 I; 8 j 2 J (3.65)

y i 2f 0;1 g i 2 I: (3.66)

Formulation KUFLP can be viewed as a set packing formulation and thus its set
packing properties are inherited. For this we will consider the intersection graph,
that we denote by G.m;n/, with a node for each variable of KUFLP and with an
edge for each pair of variables sharing a constraint in KUFLP.
In the following P mn and F mn denote the convex hull of the feasible solutions
of KUFLP and its LP relaxation, LKUFLP, respectively. For m m and n n,
we call m n adjacency matrix S to any m n , 0-1 matrix with no zero row
and no zero column. Given an adjacency matrix S and two ordered sets I S I
and J S J,wedenotebyG S D .V S ;E S / the subgraph of G.m;n/ given by
V S Df x ij W i 2 I S ;j 2 J S ;s ij ¤ 0 g[f y i W i 2 I S g , E S Df .x ij ;x kj / W i;k 2
I S ;i <k;j 2 J S ;s ij D s kj D 1 g[f . N y i ;x ij / W i 2 I S ;j 2 J S ;s ij D 1 g . Finally,
Ǜ.G/ denotes the independence number of graph G; i.e., the maximal cardinality of
a packing of nodes in G,andB denotes a cyclic matrix of type .k;t/, i.e. its size is
k k and its rows are 0-1 vectors with t adjacent 1's, which move one position to
the right in each row.