Geoscience Reference
In-Depth Information
If we apply the definition of a Pareto location to these two subedges, we get that
a point
f
v
j
;v
l
g
;t
;t
2
Œt
r
;t
rC1
is dominated by some point .
f
v
k
;v
m
g
;s/;s
2
Œs
p
;s
pC1
,
b
p
C
m
p
s
b
r
C
m
r
t for all q
2
Q
;
where at least one inequality is strict. Now we define the polyhedron
WD
n
.s;t/
W
m
r
t
m
p
s
b
p
b
r
;
8
q
2
o
\
Œs
p
;s
pC1
Œt
r
;t
rC1
:
F
Q
D;
,then
f
v
j
;v
l
g
;Œt
r
;t
rC1
contains no point which is
We have two cases: If
F
dominated by a point from
f
v
k
;v
m
g
;Œs
p
;s
pC1
.Otherwise,
F
6D;
is taken as a
feasible solution of the two 2-variable linear programs
LB
D
min
f
t
W
.s;t/
2
F
g
; UB
D
max
f
t
W
.s;t/
2
F
g
:
Let s
LB
and s
UB
be the optimal values for s corresponding to LB and UB,
respectively. Now we still have to check if one inequality is strict: If b
p
C
m
p
s
LB
D
b
r
C
m
r
LB and b
p
C
m
p
s
UB
D
b
r
C
m
r
UB for all q
2
Q
, then there is no dominance.
X
par
.e
l
/
n
f
v
j
;v
l
g
;ŒLB; UB/
: Note that this procedure
works also if t
r
D
t
rC1
or s
p
D
s
pC1
(in this case, we are testing a single point).
Algorithm 9.6 (Combining Local Pareto Location in the
Q
-Criteria Case)
X
par
.e
l
/
WD
Otherwise
Input:
Network as in Algorithm
9.4
X
par
WD
S
e2E
X
par
.e/
X
par
.e/
for all
e
2
E
and set
Step 1.
Determine
Compare all
v
i
and all edges, where all
f
q
;q
2
Step 2.
Q
are constant
Step 3. For all Pareto linear subedges do a pairwise comparison as described
above and reduce
X
par
accordingly.
X
par
The complexity of this algorithm is O.
j
E
j
2
j
V
j
2
Q/.
Output:
9.3.1.4
Multicriteria Median Problems on a Tree
Many difficult problems on general networks become easier to solve if the under-
lying graph has a tree structure. We will show that this is also true for multicriteria
problems. We relate our results with the research that has previously been done on
trees and end up with a generalization of Goldman's algorithm (see Goldman
1971
).
The major concept which makes the analysis easier on trees is convexity. We first
introduce this concept based on Dearing et al. (
1976
).
