Geoscience Reference
In-Depth Information
We conclude that we have no node dominance and that even on edges with
endnodes not in
X
par
.
Since we do not have node dominance in the undirected case, we have to
explicitly solve a multicriteria global optimization problem. First we will identify
local Pareto locations with respect to an edge e
Df
v
i
;v
j
g
for all edges of the
network. In a second step we will compare all local Pareto locations to get
X
par
.V/ we can find elements of
X
par
.
Due to the limited space and a possible overload of technicalities, we will describe
the main ideas which allow the reader to understand the final algorithm. For the
technical details and the proofs the reader is referred to Hamacher et al. (
1999
).
9.3.1.2
Bi-criteria Case
We will first deal with the bi-criteria case, since here we can derive a geometrical
solution method. The main property of the objective functions we are using is the
concavity on an edge e
Df
v
i
;v
j
g
. In addition we have also piecewise linearity
but this is not really needed. Suppose that f.v
i
/>f.v
j
/ or f.v
j
/>f.v
i
/.In
the first situation we say that v
j
dominates v
i
and in the latter v
i
dominates v
j
.
Both situations do not allow any location on the edge, which is not dominated by an
endnode due to concavity.
Now assume that for an edge e
Df
v
i
;v
j
g
with v
i
and v
j
not dominating each
other one of the functions f
1
or f
2
is constant. It is easy to see that this is only
the case if f.v
i
/
D
f.v
j
/. If for an edge e only one of the objective functions
is constant then
X
par
.e/
Df
v
i
g[f
v
j
g
. If both objective functions are constant
X
par
.e/
D
f
v
i
;v
j
g
;Œ0;1
. Again this is due to the concavity of the objective
functions and can be seen in Fig.
9.15
.
Now we have only one situation left (the most typical one), where the endnodes
do not dominate each other and none of the two objective functions is constant.
Without loss of generality we can assume f
1
.v
i
/>f
1
.v
j
/ and f
2
.v
i
/<f
2
.v
j
/
(otherwise exchange the roles of v
i
and v
j
). The behaviour of the objective functions
can be seen in Fig.
9.16
. First, both objectives functions are increasing (maybe for
a small or zero interval only) and all points are dominated by the left endnode.
then
Fig. 9.15
Concavity on an
edge with one objective
function constant
