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

Some relevant contributions on the polyhedral analysis of KUFLP are (in
chronological order): Cornuéjols et al. ( 1977 ), Guignard ( 1980 ), Cornuéjols and
Thizy ( 1982 ), Cho et al. ( 1983a , b ), Myung and Tcha ( 1996 ), Cánovas et al. ( 2000 ,
2001 , 2002 , 2003 ), Baiou and Barahona ( 2009a ) and Chen et al. ( 2012 ). New trends
in this area relate to the study of how to adapt the known polyhedral properties of
the UFLP to problems generalizing it. Nice examples are the papers by Hamacher
et al. ( 2004 ) and by Baiou and Barahona ( 2009b ). In both cases the authors give
results allowing to directly adapt any valid inequality of the UFLP to the Hub
Location Problem and the Two-Level Facility Location Problem, respectively. Next
we summarize the main results in this area.
First of all, P mn is full-dimensional, i.e., dim.P mn / D mn C p. Thus, two
different facets of P mn always define two different sets of feasible solutions for

KUFLP.
Cho et al. ( 1983a ) have proven that for m 2 or n 2 the coefficients matrix
of KUFLP is totally unimodular, so the polyhedral analysis is of little interest. They
have also given a complete description of the facets of P mn when m D 3 or n D 3.
Recently, Baiou and Barahona ( 2009a ) and Chen et al. ( 2012 ) have presented new
conditions for F mn to be integral, i.e., to have all its extreme points integral. Both
papers define a particular type of odd cycles in the intersection graph of KUFLP
without which the extreme points of the polyhedron F mn are integral.
The remainder of this section is divided in three parts: extreme points of F mn ,
valid inequalities and facets of P mn , and lifting procedures.

3.5.1 Extreme Points

We are aware of two papers dealing with the characterization of the fractional
extreme points. Cornuéjols et al. ( 1977 ) give a characterization for the extreme
points of F mn : Let I f Df i 2 I W 0< N y i <1 g ;J 0 Df j 2 J W x ij 2f 0;1 y i g
for all i and x ij non-integer for some i g and let U be the j I f jj J 0 j matrix whose
elements are

u ij D 1 if x ij >0;
0 if x ij D 0:

Theorem 3.3 (Cornuéjols et al. 1977 ) The fractional feasible solution .x;y/ of
LKUFLP is an extreme point of F mn if and only if

(a) 1 y i D max j f x ij g for all i 2 I f ;
(b) for each j 2 J; there is at most one i with 0<x ij <1 y i ;
(c) the rank of U equals j I f j :
Cánovas et al. ( 2001 ) have later provided a characterization for the extreme points
of a more general polyhedron and proved that condition (a) of Theorem 3.3 follows
from conditions (b) and (c). Cho et al. ( 1983a ) make use of this characterization