Geoscience Reference
In-Depth Information
X
x
ije
z
k
i;j;k
2
N
(12.15)
e2EWk2e
x
ije
0
i;j;k
2
N
(12.16)
Z
i
2f
0;1
g
i
2
N:
(12.17)
Constraints (
12.14
) guarantee that there is a single path connecting the origin and
destination nodes of every commodity. Constraints (
12.15
) prohibit commodities
from being routed via a non-hub node. As in UHLPSA, there is no need to
explicitly state the integrality on the x
ije
variables because there always exists an
optimal solution of (
12.14
)-(
12.17
) in which all x
ije
variables are integer. This
formulation has O.n
4
/ variables and O.n
3
/ constraints and usually provides tight
LP bounds. Hamacher et al. (
2004
)andMarín(
2005a
) independently prove that
constraints (
12.15
) are indeed facet-defining inequalities. Marín (
2005a
) provide
other classes of inequalities associated with the set-packing polytope which also
define facets.
The number of routing variables x
ije
can be further reduced by defining a set
of candidate hub arcs for each O/D pair (see Contreras et al.
2011b
). This is done
by using the property that no flow will be routed through a hub arc containing two
different hubs whenever it is cheaper to route it through only one of them (Boland
et al.
2004
;Marín
2005a
).
In HLPs with multiple assignments it is also possible to completely eliminate
the undirected routing variables x
ije
by exploiting the supermodular properties
presented in Sect.
12.2.2
. We define binary hub arc location variables y
e
, e
2
E,
equal to 1 if and only if a hub arc is located at e. For each i;j
2
N,weorderthe
elements of E by non-decreasing values of their coefficients F
ije
, and we denote
e
rk
to the r-th element according to that ordering. That is, F
ije
1
F
ije
2
F
ije
jEj
k
F
e
ij
jEjC1
,whereF
e
ij
jEjC1
D
F
ij
e
is the cost for the fictitious edge
e
such that .i/ F
e
k
> max
e2E
F
ek
,forallk
2
K;and.
ii
/
P
k2K
F
ek
>
max
e2E
.f
e
C
P
k2K
F
ek
/. This assumption guarantees that at least one hub variable
y
e
is at value one in any optimal solution. The UHLPMA can be stated as the
following MIP (see Contreras and Fernández
2014
):
minimize
X
k2N
f
k
Z
k
C
X
i;j2N
ij
subject to
ij
F
ije
r
C
X
e2E
.F
ije
F
ije
r
/
N
y
e
r
D
1;:::;
j
E
jC
1; i;j
2
N
(12.18)
y
e
z
k
e
D
.k;m/
2
E
(12.19)
y
e
z
m
e
D
.k;m/
2
E
(12.20)
y
e
;
z
i
2f
0;1
g
e
2
E;i
2
N;
(12.21)
