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

decomposition have been respectively proposed in Wentges ( 1996 )andVanRoy
( 1986 ), whereas branch-and-price has been applied by Díaz and Fernández ( 2002 )
and Klose and Görtz ( 2007 ). Some recent works are Barahona and Chudak ( 2005 ),
Sankaran ( 2007 ), Sharma and Berry ( 2007 ), Ghiani et al. ( 2012 ), and Zhen et al.
( 2012 ). For an overview of heuristics for FLPs the interested reader is addressed
to Jacobsen ( 1983 ), Filho and Galvão ( 1998 ), Delmaire et al. ( 1999a , b ), Hindi and
Pienkosz ( 1999 ), Cortinhal and Captivo ( 2003 ), Ahuja et al. ( 2004 ) and references
therein.
The most obvious strategy for solving an FLP instance to optimality is to use
a standard mixed integer programming (MIP) solver with formulation SFLP or
MFLP, depending on the case. This approach may, however, fail on large instances,
especially for the single source case. Some alternatives are presented below, which
somehow exploit the structure of the problem and lead either to an exact algorithm
or to methods that can be embedded within an exact algorithm. First we study
Lagrangean relaxation, which has been used by a number of authors both for the
single and multiple allocation cases. Then we address the pricing problem for the
set partitioning formulation SPSFLP, which is one of the main ingredients of the
branch-and-price algorithm of Díaz and Fernández ( 2002 ).

3.3.1 Lagrangean Relaxation

We next present a Lagrangean relaxation of model SFLP in which the assignment
constraints ( 3.2 ) are relaxed. This relaxation has been used by a number of authors
(see, for instance, Pirkul 1987 ; Barceló et al. 1990 , 1991 ; Beasley 1993 ;Holmberg
et al. 1999 ). The Lagrangean subproblem associated with a given set of multipliers
2 R n ,is

0
@ f i y i C X
j2J

1
A C X
j2J

1 X
i2I

! (3.24)

L SFLP ./ D minimize X
i2I

c ij x ij u j x ij

subject to X
j2J

d j x ij q i y i i 2 I (3.25)

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

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

After rearranging its terms the objective function can be rewritten as

0
@ f i y i C X
j2J

1

X

j C min X
i2I

c ij j x ij

A :

j2J