Geoscience Reference
In-Depth Information
Then, a set partitioning formulation for the SFLP is
minimize
X
i2I
X
SPSFLP
p
ki
z
ki
(3.19)
k2K
i
subject to
X
i2I
X
a
ijk
z
ki
D
1j
2
J
(3.20)
k2K
i
X
z
ki
D
y
i
i
2
I
(3.21)
k2K
i
y
i
2f
0;1
g
i
2
I
(3.22)
z
ki
2f
0;1
g
i
2
I; k
2
K
i
:
(3.23)
Constraints (
3.20
) ensure that each customer is assigned to exactly one facility.
Constraints (
3.21
) guarantee that no assignment is selected for a non-open facility
and also that one feasible assignment is selected for each open facility. Observe
that, because of (
3.20
), constraints (
3.21
) can be written as
inequalities and will
still be satisfied as equalities. Constraints (
3.22
)and(
3.23
) define the domain of the
decision variables. The above a formulation will be referred to as SPSFLP.
A set partitioning formulation for the multiple allocation case can be obtained
from the above formulation by simple relaxing the integrality conditions on the
z
variables to 0
z
ki
1, i
2
I;k
2
K
i
. It is now necessary to use the
expression
for constraints (
3.21
), since optimal solutions may exist with some open facility
only serving fractions of demand of the allocated customers. This formulation will
be referred to as SPMFLP.
The large number of variables both in SPSFLP and in SPMFLP make these
formulations suitable for column generation.
3.3
Solution Algorithms for Fixed-Charge Facility Location
In this section we overview solution methods for FLPs. Several heuristic and
exact algorithms have been proposed for FLPs and an exhaustive survey on the
related literature is outside the scope of this chapter. Branch-and-bound methods
proposed in the early papers (Sá
1969
; Davis and Ray
1969
; Ellwein and Gray
1977
; Akinc and Khumawala
1977
;Nauss
1978
; Neebe and Rao
1983
)were
followed by many algorithms based on Lagrangean relaxation (Geoffrion and
McBride
1978
; Christofides and Beasley
1983
; Guignard and Kim
1983
; Barceló
and Casanovas
1984
; Klincewicz and Luss
1986
; Pirkul
1987
; Beasley
1988
;
Guignard and Opaswongkarn
1990
; Barceló et al.
1990
,
1991
; Cornuéjols et al.
1991
; Beasley
1993
; Sridharan
1993
,
1995
;Holmbergetal.
1999
). Some of the
first works on approximation algorithms are those of Shetty (
1990
), Shmoys et al.
(
1997
) and Chudak and Shmoys (
1999
). Algorithms based on Benders and cross
