Dynamic Stochastic Optimal Path A Useful Tool From Probability Theory Rasteiro, Deolinda D. M. L Departamento de F´ isica Matem´ atica Instituto Super

Dynamic Stochastic Optimal Path
A Useful Tool From Probability Theory
Rasteiro, Deolinda D. M. L

Departamento de F´ isica Matem´ atica
Instituto Superior de Engenharia de Coimbra
Coimbra - Portugal
dml@mail.isec.pt


Anjo, Ant´ onio J. B.
Departamento de Matem´ atica - Universidade de Aveiro
Aveiro - Portugal
batel@ua.pt
March 10, 2005
Abstract
In this paper we prove a theorem that become very useful to design
algorithms for solving the dynamic stochastic optimal path.
We also prove that the solution for the deterministic shortest path
is always an upper bound for the dynamic stochastic optimal path.
Keywords: Probability Networks, Expected Value of an Op-
timal Path, Expected value of the minimum of two real random
variables, Dynamic paths
AMS Subject Classi?cation: 90B15
1 Introduction
Suppose we want to obtain de optimal route in a directed random network,
where the parameters associated to the arcs are real random variables fol-
lowing discrete distributions. The criteria that has been chosen by us to
decide which route is optimal is the one that minimizes the expected value
of an utility function over the considered network.
This methodology can be used in di?erent applications, as energy net-
work or data network, where real on time optimal solutions are necessary.
1

2 PROBLEM 2
For the special case of acyclic networks Cheung and Muralidharan [1]
developed a polynomial time algorithm (in terms of the number of realiza-
tions per arc cost and the number of emerging arcs per node) to compute
the expected cost of the dynamic stochastic shortest path.
In this paper we de?ne the problem of which consists in obtaining the
loopless path that minimizes the expected value of an utility function over a
dynamic probabilistic network with discrete real random variables (param-
eters) associated to each emerging arc. Then we prove a theorem, which is
useful tool from probability theory, used to design the algorithm that solves
the problem referred above.
We also prove that the optimal value of the deterministic shortest path,
obtained using the expected values of the real random variables, is always
an upper bound to the dynamic stochastic shortest path.
2 Problem
In the stochastic shortest path problem a directed probabilistic network
(N,A) is given where each arc (i, j) ? A is associated with the real random
variable X ij which is called the random parameter of the arc (i, j) ? A. We
assume that the real random variables X ij have discrete distributions and
are independent. The variables X ij are sometimes referred as cost, time or
distance.
1 2 r
The set of outcomes of X ij will be denoted by S X ij= d ij, d ij, . . . , d ij .
We will assume that the dimension of S X ij, i.e, r is always a ?nite value.
l l
The probability of X ij assume the value d ij is denoted by p ij.
If an appropriate utility is assigned to each possible consequence and
the expected utility of each alternative is calculated, then the best action is
to consider the alternative with the highest expected utility (which can be
the smallest expected value). Di?erent axioms that imply the existence of
utilities with the property that expected utility is an appropriate guide to
consistent decision making are presented in [6, 5, 3, 4, 2]. The choice of the
adequate utility function for a speci?c type of problem can be taken using
direct methods presented in Keeney and Rai?a’s book.
The utility of arc (i, j) ? A to be present in the optimal loopless path is
measured calculating the minimum of the real random variables X iwwhere
1
w is such that the arc (i,w) ? A, i.e, w belongs to the forward star of i.
1
The forward star of node i is the set formed by the terminal nodes of its outgoing
arcs.

2 PROBLEM 3
Thus U((i, j)) = min X iw.
w?F(i)
Associated to the path p, we de?ne the real random variable
X p = min X iw representing the random parameter of the loopless
w?F(i)
(i,j)?p
path p ? P.
With the objective of determine the optimal path, we consider a real
function U : P -? IR, called utility function, such that for each loopless
path p, U(p) depends on the random variables associated to the arcs of p
and is de?ned as
? ?
U(p) = E? min X iw?.
w?F(i)
(i,j)?p
In the dynamic stochastic shortest path, we want to determine the loop-
?
less path p ? P that minimizes the expected value of the utility function.
?
The loopless path p is called optimal solution of the referred problem.
The problem can then be mathematically de?ned as
? ?
minU(p) = min E? min X iw?
p?P p?P w?F(i)
(i,j)?A
? ?
= min E? min X iw?Y ij (1)
w?F(i)
(i,j)?A
s.t
?
1 , i = s
?
Y ij- Y ji = 0 , i / ? {s, t}
?
(i,j)?A -1 , i = t
Y ij ? {0, 1}
Since the constraint matrix is totally unimodular, by the integrality prop-
erty, the solution of the previous problem is equal to the solution of its linear
relaxation.
Example 2.1 In order to exemplify the problem consider the following net-
work

2 PROBLEM 4
Figure 1: Network Example
The solution for the referred example is
Figure 2: Example Solution
which means that the dynamic stochastic optimal loopless path is the
following < 1, (1, 2), 2, (2, 3), 3 > with value 5.5.
Theorem 2.1 Let X and Y be two random variables with ?nite mean value.
Then the following inequality holds E(min(X, Y )) = min(E(X),E(Y )).
Proof: Suppose that X and Y have the following set of outcomes S X=
{x 1, . . . , x n}, S Y = {y 1, . . . , ym}, respectively with P(X = x i) = p i, ?i =
1, . . . , n and P(Y = y j) = q j, ?j = 1, . . . ,m. The expected value of the
minimum between X and Y is given by

2 PROBLEM 5
n m
E(min(X, Y )) = min(x i, y j)p iq j
i=1 j=1
n mx i+ y j- |x i- y j|
= p iq j
2
i=1 j=1
n mx ip iq j+ y jp iq j- |x ip iq j- y jp iq j|
=
2
i=1 j=1
? ?
n m n m
= min? x ip iq j, y jq jp i?
i=1 j=1 i=1 j=1
= min (E(X),E(Y ))
From this theorem it follows a very important result which is
Theorem 2.2 The optimal value of the shortest deterministic path using
the expectations of the real random variables associated to the network arcs
is an upper bound to the optimal value of the dynamic stochastic shortest
path.
Proof: Consider the problem de?ned in section 2, (DSSP), and the let (SP)
be the problem of determining the optimal deterministic shortest loopless
path when we consider associated to each arc the parameter µ ij = E(X ij).
Assume that the optimal solutions of problems (SP) and (DSSP) are the
? ? ? ?
paths p , with value µ , and the path p , with value µ , respectively. We
1 1
? ?
will prove that µ = µ , ? p ? P.
1
By de?nition we obtain,
? ?
?
µ 1 = minE? min X iw?
p?P w?F(i)
(i,j)?p
= min E min X iw
p?P w?F(i)
(i,j)?p
If the set F(i) has only two elements, w 1 and w 2, then it follows that
?
µ 1 = min min E(X iw) (2)
p?P w?F(i)
(i,j)?p
= min min(µ iw 1 , µ iw 2 )
p?P
(i,j)?p

REFERENCES 6
only one of the arcs (i,w 1), (i,w 2) belongs to the path p ? P, i.e, j = w 1 or
j = w 2, thus
?
µ 1 = min min(µ iw 1 , µ iw 2 )
p?P
(i,j)?p
= min µ ij
p?P
(i,j)?p
?
= µ
which is the desired result. If the set F(i) has more than two elements then,
the same conclusion can be obtain by induction in the step (2).
References
[1] R. K. Cheung and B. Muralidharan, Dynamic routing of priority ship-
ments on a less-thantruckload service network, Tech. report, Department
of Industrial and Manufacturing Systems Engineering, Iowa State Uni-
versity, 1995.
[2] P. C Fishburn, Utility theory for decision making, Wiley, New York,
1970.
[3] R. D. Luce and H. Rai?a, Games and decisions, Wiley, New York, 1957.
[4] J. W. Pratt, H. Rai?a, and R. O. Schlaifer, Introduction to statistical
decision theory, McGraw-Hill, New York, 1965.
[5] L. J. Savage, The foundations of statistics, Wiley, New York, 1954.
[6] J. von Neumann and O. Mogenstern, Theory of games and economic
behavior, Princeton University Press, Princeton, N.J., 1947.