Geoscience Reference
In-Depth Information
The model can be further strengthened by adding constraints (
20.8
) and cut set
inequalities that ensure connectivity between the root and every customer:
X
x
ij
1
W
V
nf
r
g
;W
\
J
¤;
:
.i;j/2ı
.W/
Gollowitzer et al. (
2013
) also proposed additional valid inequalities based on
the combination of known inequalities from the literature on the facility location
and network design. They study the separation problems associated to all these
inequalities and show that the combination of all valid inequalities in a branch-
and-cut algorithm provides an effective algorithm for solving large size, realistic
instances.
20.3.3
Other Variants of the Connected Facility Location
Problem
The Connected Facility Location problem is still getting much attention, and many
extensions have been studied. Bardossy and Raghavan (
2013
) proposed a robust
version of the problem based on the framework introduced by Bertsimas and Sim
(
2003
). In particular, they proposed a heuristic based on the dual-ascent based local
search for the basic ConFL problem proposed in the latter paper.
Leitner et al. (
2013
) proposed a model and a branch-and-cut algorithm for the
Connected Facility Location with Two Architectures problem. This is an extension
of the ConFL problem for networks that mix two architectures in a combined
deployment (e.g., FFTH and FFTC/FFTB). Two types of facilities (one for each
architecture) exist in the network. Central offices in the network are nodes where
switching between the two architectures is possible. Each open facility must be
connected by a path to an open central office. In addition, a certain fraction of
customers (determined according to minimum coverage rates) must be served by
each architecture.
Related to ConFL, Contreras et al. (
2010
) studied the Tree of Hubs Location
Problem where exactly p hubs (facilities) must be opened, connected by a spanning
tree. The major differences with ConFL lie in the fixed number of facilities to open,
and the cost structure that considers routing costs explicitly. Moreover, there are
no Steiner nodes in this problem. A four index formulation was also proposed in
Contreras et al. (
2009
), leading to better lower bounds. However, this improvement
comes at the price of a considerable increase in the computational time used to solve
the linear relaxation of the problem. The authors therefore suggested a Lagrangian
relaxation method leading to an efficient decomposition method.
