Geoscience Reference
In-Depth Information
Fig. 20.2
An example of solution to the connected facility location problem
Early work on ConFL concentrated on approximation algorithms, such as the
primal-dual procedures proposed by Swamy and Kumar (
2004
). The currently best-
known constant approximation ratio is given by the 4-approximation algorithm of
Eisenbrand et al. (
2010
). Heuristic approaches have been proposed by Ljubi
´
c(
2007
)
and Bardossy and Raghavan (
2010
).
Different MIP models for ConFL were proposed and compared (both theoreti-
cally and empirically) by Gollowitzer and Ljubi
´
c(
2011
). As directed formulations
for problems with tree topologies usually outperform undirected formulations, the
problem is first converted to a directed instance by replacing each edge e
Df
i;j
g2
E between two Steiner nodes i;j
2
S by two directed arcs .i;j/ and .j;i/ with
costs c
ij
D
c
ji
D
c
e
, and each edge e
Df
i;j
g
between a customer j
2
J and a
facility i
2
I by a directed arc .i;j/ with cost c
ij
D
c
e
. If the problem is unrooted,
an artificial root r is added to V with cost f
r
D
0.Arcs.r;i/ are added for all
facilities i
2
I with c
ri
D
0 and the number of arcs emanating from the root r is
limited to 1. The resulting set of arcs is denoted by A.
According to the results reported by Gollowitzer and Ljubi
´
c(
2011
), the most
effective formulation for solving this problem with a branch-and-cut algorithm is
the cut-based formulation, proposed by Ljubi
´
c(
2007
), and described below. We use
the following notation: A
J
Df
.i;j/
2
A
W
i
2
I; j
2
J
g
is the set of arcs
connecting customers to facilities, while A
S
Df
.i;j/
2
A
W
i;j
2
S
g
is the set of
arcs connecting Steiner nodes. Moreover, for any W
V , we denote the incoming
