Information Technology Reference
In-Depth Information
j
)of
the dilution/mixing tree of height
d
to be determined. Next, a set
Q
is formed with all
the elements of
W
[
i,j
]
.w
j
of fluid
A
i
,ifitisatlevel(
d
−
and corresponds to the contribution
except the elements of the row for
D
. The optimal dilution/mixing
tree can be constructed by selecting some of the elements as a set
R
from
Q
(i.e.,
R
W
Q
) and using some extra amount of
D
(if needed). While finding
R
from
Q
following parameters are computed: (a) the total weight of all the elements in
R
as
V
=
∀x, x∈R
w
j
, (b) the sum of all the elements in
R
as
T
=
∀x, x∈R
x
, i.e.,
the target
CF
becomes
T
⊂
2
d
, and (c) the height of the underlying dilution/mixing tree as
d
=
max
(
j
) such that for all
i,j
,
[
i,j
] is selected in
R
(hence, 0
<d
≤
W
d
).
Algorithm 1.
GDA
,
C
A
,
d
1:
Set
b
N
+1
=0(for buffer solution,
D
)and
b
1
,b
2
,...,b
N
T
=
ʦ
.
B
i
T
2
d
,where
B
i
sand
T
are positive real
2:
Represent
b
i
as
2
d
(for all
i
)and
C
A
as
numbers.
3:
for
i
=1to
N
+1
do
4:
[
i
][0] =
B
i
.
5:
Construct
W
Set
1
2
W
by (
d
+1) G.P. terms with
W
[
i
][0] as the first term and
as the
common ratio.
6:
Obtain set
Q
with all the numbers (integers or reals) of
except the (
N
+1)
th
W
row.
7:
For each number
x ∈ Q
, associate an weight
w
x
=
2
j
,if
x
is
j
th
G.P. term in
W
.
8:
Find
R
from
Q
,where
R
Q
(Subset-Sum Problem), by using the pseudo-
polynomial time dynamic programming approach [16]. A solution to this problem
is a binary matrix
⊂
X
(i.e.,
R
) denoting the selection of numbers from
W
(i.e.,
Q
),
<
0
.
5,where
T
=
∀x, x∈R
T
|
such that
|
T
−
x
. More than one solutions can be
obtained.
9:
for all
the solutions
do
10:
Compute
V
=
∀x, x∈R
w
x
.
1
then
12:
The solution is valid.
13:
for all
the valid solutions
do
14:
if
V
≤
11:
Compute
d
=
max
(
j
)
s.t.
X
[
i
][
j
]=1
,
∀
i,j
.
+
ʲ
d
(
D
)=
1
,where
[
N
+1]=
1
Compute
m
=
|
R
|
∀i,j
X
[
i,j
]
−
X
−
15:
i
=0
X
[
i
]
and
ʲ
d
(
D
)=
N
∀j
X
[
N
+1][
j
],as
X
[
i
] is the binary fraction denoting
for fluid
A
i
.
selection of numbers from
W
16:
Compute
M
lb
.
17:
Keep the optimal solution(s) depending on the optimality criteria.
18:
Keep the binary matrix
X
for any one of the optimal solution(s).
19:
Construct
T
from
X
using
Min-Mix
[6].
