Geoscience Reference
In-Depth Information
well integrated within a branch-and-price scheme. For this reason, the next section
studies the pricing problem for generating columns for SPSFLP, which is the main
component of an exact branch-and-price algorithm for the SFLP based on this
formulation (Díaz and Fernández
2002
).
3.3.2
The Pricing Problem for SPSFLP
Suppose we have solved t
he
LP r
ela
xation of the subproblem of SPSFLP associated
with a subset of columns K
D
.K
i
/
i2I
.Let,and denote the optimal values of
the dual variables associated with constraints (
3.20
)and(
3.21
), respectively. Then
in order to know whether there exists a
z
variable of the overall formulation that, if
added to the current set of columns, would improve the current LP solution, we must
find the column of the coefficient matrix of
SPSFLP
with the smallest reduced cost.
The reduced cost of variable
z
ki
, i
2
I;k
2
K
i
,isgivenbyr
ki
D
p
ki
P
j2J
j
a
ijk
i
. Thus, in order to find the column that yields the smallest reduced cost we must
solve the following pricing problem:
r
ki
D
p
ki
X
j2J
.
PP
/
min
i2I;k2K
i
j
a
ijk
i
:
Since p
ki
D
f
i
C
P
j2T
k
c
ij
,thenr
ki
D
f
i
C
P
j2J
c
ij
j
a
ijk
i
.Note
also that feasible columns
a
ik
, k
2
K
i
;i
2
I, are characterized by the condition
P
j2J
d
j
a
ijk
q
i
. Thus, the solution to
PP
can be obtained by solving a series of
independent problems, one for each i
2
I. Since, for a given i
2
I,thevaluef
i
i
is fixed, then the corresponding problem reduces to
minimize
X
j2J
c
ij
j
a
ijk
PP
i
subject to
X
j2J
d
j
a
ijk
q
i
a
ijk
2f
0;1
g
j
2
J:
3.4
The Uncapacitated Facility Location Problem
An important particular case of the FLP arises under the assumption that the
capacity of any open facility is sufficient to satisfy the demand of all customers,
i.e. q
i
P
j2J
d
j
, i
2
I, so that the capacity constraints (
3.3
) are not needed. This
particular case is known as the
Uncapacitated Facility Location Problem
(UFLP)
and has received a considerable amount of attention. Next we focus on the UFLP
