Geoscience Reference
In-Depth Information
This construction can be implemented for problems of small to medium size
dimension using the open source software
barvinok
, see Verdoolaege (
2008
).
9.4.3
Determining Supported Pareto-Optimal Solutions
In some situations it suffices to generate the set of supported Pareto-optimal points.
It is well-known that the set of supported Pareto-optimal solutions to a problem can
be obtained by solving the scalarized problem for all possible values of the scalar
weights in the standard Q-dimensional simplex
Q
Df
2
Q
W
P
qD1
q
D
R
1;
q
0;
8
q
D
1;:::;Q
g
:
In order to describe how to obtain these solutions in Problem (
9.6
)-(
9.10
)we
need to introduce some additional notation. We den
ote
by B any feasible basis of
the linear relaxation of Problem (
9.6
)-(
9.10
); and by N all the columns that are not
in B. Also, abusing notation, as u
su
al in linear programming, we shall refer to the
indices determining the basis B (N) in the variables and the objective function by
.x;y/
B
(.x;y/
N
)andc
B
(c
N
), respectively.
For any
2
Q
, we shall denote by c./
D
.c
ij
.//
ij
,wherec
ij
./
D
P
qD1
q
c
ij
.
For each feasible basis B, consider the subdivision of the space
Q
induced by
the hyperplanes:
q
c
B
B
1
N
q
c
q
N
D
0; q
2
Q
:
let
B
2
Q
Next,
be
a
parameter such
that
it
belongs to
the
rela-
tive
interio
r
of
one of
the
elements
in
the
above subdivision and
satisfies
c
B
.
Q
/B
1
N
c
N
.
Q
/
0. This choice of
Q
ensures that the problem:
X
M
X
N
c
ij
.
B
/x
ij
Minimize
(9.11)
iD1
jD1
X
N
x
ij
D
1; i
2
I;
subject to
(9.12)
jD1
x
ij
y
j
; i
2
I; j
2
J;
(9.13)
X
N
y
j
D
p;
(9.14)
jD1
x
ij
0; y
j
0; i
2
I; j
2
J
I
(9.15)
