Geoscience Reference
In-Depth Information
the flow originated at i and destination j transits via a first hub node k and a second
hub node m. The UHLPSA can be stated as follows (Skorin-Kapov et al.
1997
):
minimize
X
k2N
f
k
z
kk
C
X
i;j;k;m2N
F
ijkm
x
ijkm
subject to
(
12.4
)-(
12.6
)
X
x
ijkm
D
z
ik
i;j;k
2
N
(12.7)
m2N
X
x
ijkm
D
z
jm
i;j;m
2
N
(12.8)
k2N
x
ijkm
0
i;j;k;m
2
N:
(12.9)
Constraints (
12.7
) state that if node i is assigned to hub k then all the flow from
node i to any other node j must go through some other hub m. Constraints (
12.8
)
have a similar interpretation relative to the flow arriving to a node j assigned to hub
m from some node i. There is no need to explicitly state the integrality on the x
ijkm
variables because there always exists an optimal solution of (
12.4
)-(
12.8
)inwhich
all x
ijkm
variables are integer. One of the attractive features of this formulation is that
it usually provides tight
Linear Programming
(LP) relaxation bounds, at the expense
of requiring O.n
4
/ variables and O.n
3
/ constraints. Saito et al. (
2009
) study the
polyhedral structure of the quadratic semi-assignment polytope, a relaxation of this
formulation, and provides strong valid inequalities to further improve its LP bound.
It is possible to project out the path-based variables x
ijkm
to obtain a formulation
with fewer variables (see Labbé and Yaman
2004
; Labbé et al.
2005
). We define
continuous variables y
km
, k;m
2
N, equal to the amount of flow routed on hub arc
.k;m/. The UHLPSA can be formulated as:
minimize
X
k2N
f
k
Z
k
C
X
i;k2N
.O
i
C
ıD
i
/d
ik
z
ik
C
X
k;m2N
Ǜd
km
y
km
subject to
(
12.4
)-(
12.6
)
y
km
X
.i;j/2K
W
ij
z
ik
C
z
jm
1
k;m
2
N;K
N
N (12.10)
y
km
0
;m
2
N:
(12.11)
For each arc .k;m/, constraints (
12.10
)and(
12.11
)imply
X
W
ij
z
ik
C
z
jm
1
D
X
.i;j/2K
km
W
ij
z
ik
C
z
jm
1
;
y
km
D
max
KNN
.i;j/2K
where K
km
is the set of all demands which are routed on hub arc .k;m/.This
formulation contains only O.n
2
/ variables but an exponential number of constraints.
Labbé and Yaman (
2004
) show that constraints (
12.10
) are a particular case of