Geoscience Reference
In-Depth Information
and outgoing cuts induced by W as ı
.W/
Df
.i;j/
2
A
W
i
…
W; j
2
W
g
and
ı
C
.W/
Df
.i;j/
2
A
W
i
2
W; j
…
W
g
.
To formulate the problem, binary variables y
i
are considered to indicate if facility
i is open, as well as binary variables x
ij
to indicate if arc .i;j/ is used, as a Steiner
tree arc if .i;j/
2
A
S
, or to assign customer j to facility i if .i;j/
2
A
J
.The
cut-based model of Ljubi´c(
2007
) can then be written as:
Minimize
X
i2I
f
i
y
i
C
X
.i;j/2A
c
ij
x
ij
(20.7)
X
subject to
x
jk
y
i
W
S
nf
r
g
;i
2
W
\
F
¤;
; (20.8)
.j;k/2ı
.W/
X
x
ij
D
1
j
2
J; (20.9)
iW.i;j/2A
J
x
ij
y
i
.i;j/
2
A
J
; (20.10)
y
r
D
1
(20.11)
x
ij
2f
0;1
g
.i;j/
2
A; (20.12)
y
i
2f
0;1
g
i
2
I: (20.13)
Cut constraints (
20.8
) impose that there is an arc entering any subset containing an
open facility but not containing the root. Together, these constraints ensure that a
path exists from the root to any open facility. Constraints (
20.9
) ensure that each
customer is linked to one of the facilities, while constraints (
20.10
) force to assign
customers to open facilities only. The root is always open by constraint (
20.11
).
Finally, constraints (
20.12
)and(
20.13
) ensure that the variables are binary.
20.3.2
The Capacitated Connected Facility Location Problem
Recently, Gollowitzer et al. (
2013
) extended ConFL by considering that each facility
i
2
I has a fixed capacity q
i
, and the sum of customers' demands assigned to facility
i cannot exceed such value. Moreover, each facility has a demand b
i
that must be
sent from the root. Each arc .i;j/
2
A
S
has a capacity
u
ij
, and the flows routed in the
Steiner tree to satisfy the demands of the facilities cannot exceed these capacities.
Note that this problem is a generalization of both ConFL and the Concentrator
Location Problem. One way to formulate the problem is to explicitly introduce
