結合法則をみたす2項演算で経路の長さが定義された 最適経路問題

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

結合法則をみたす2項演算で経路の長さが定義された 最適経路問題

丸山, 幸宏

https://doi.org/10.11501/3166963

出版情報：Kyushu University, 1999, 博士（数理学）, 論文博士 バージョン：

権利関係：

Optimal Path Problems with Path Lengths Defined by Associative Binary Operations

Yukihiro Maruyama

Department of General Economics, Faculty of Economics

Nagasaki U ni versi ty

Contents

Chapter 1 Introduction 1

Chapter 2 Dynamic programming formulation for associative optimal

path problems 9

1 Introduction .^{. . . .. .}.^{. .}.^{.. . . . . . .. . . . . . . . . . . . . .. .. . .}.^{. . . .}.^{. .}.^{. . . . .} 2 Existence and uniqueness ^{. . . .. . . . . . . . .. . . . . . .}.^{. . . .}.^{. . .}..^..^..^.

9 11 3 Successive approximation method ^. . . . 19

Chapter 3 Bynamic programming formulation for associative optimal

path problems 26

1 Introduction ^{. . . . . .}.^{. . . . . .. . .}.^{. . .. . . . . . . . . . .}.^{. . . . . . ..}.^{. . . . . .. . . . .} 2 Existence and uniqueness ^..^{.. . .. . . . . . . . . . . .. . . . . .}.^{. . . . . . . . . .}.^. 3 Bidecision algorithm ^{. . . .. .}.^{. .}.^{. .. . . .. . . . . .}.^{. . . . . . . . .}.^{. . . . .}.^{. .}.^.

26 28 38

Chapter 4 On a negative-equivalency theorem in associative optimal

path problems 45

1 Introduction ^. . . . 45 2 Bitonic semigroup ^{. .. . . . . .. . . .}.^{. . . . . . .}.^{.. . . . . . .}..^{. . . . . . .. . . . . . .} 46 3 Problem and formulation ^. . . . 50 4 Negative-equivalency theorem

5 Discussion ^{. . . . . . .. . .. . . . . .. . . . . .. . . . . . .. . . . . . . . .. . . . . . . . .. . . . .. .} 53 59

Chapter 5 An invariant imbedding approach to associative shortest path

problems 62

1 Introduction ^..^{.. . . . . .. . . . . . . .. . . ..}.^{.. . . . . . . . . .. . . . . . . . . . . . . . . . . .} 62

2 Formulation and uniqueness

3 Recursive equations and separability 4 Successive approximation method Acknowledgements

11

64 67 71 77

Chapter 1. Introduction.

In the so-called shortest path problem, the objective is to find a path of minimum length fron1 an origin node 1 to a destination node Nin a directed network

G(V, A); V

and

A

are finite sets of nodes numbered _1, 2, ... , N and of directed arcs, respectively. The problem of finding the length of a path which is defined as the sum of its arc lengths is called additive (shortest path) problem. The methods for solving the shortest path problem are traditionally divided into two groups: label setting algorithms and label correcting ones.

The Dijkstra's algorithm (Dijkstra (1959)) is well-known as the label setting algorithm.

Moreover, many variants of Dijkstra's algorithm has been proposed (Dial (1969), Wagner (1976), Denardo and Fox (1979), Johnson (1982), Fredman and Tarjan (1984)). Label setting algorithms are applicable only to the shortest path problems with nonnegative arc lengths. On the other hand, label correcting algorithms can be applied to problems in­

cluding negative arc lengths. Ford (1956) outlined first the label correcting algorithms for the additive problem. Subsequently, Bellman (1958) has given the dynamic programming algorithm for the shortest path problem. Following Ford and Bellman, many authors have actively studied label correcting algorithms (Ford and Fulkerson (1962), Pape (1974, 1980), Glover, Klingman and Phillips (1985), Bertsekas (1993, 1996) among the others).

A good review of these works has been given in Ahuja, Magnanti and Orlin (1993).

The problem where the length of a path is the multiplication of its arc lengths was also considered by Moisil (1960), Carre (1971), Iwamoto (1987), Smith (1991) and Sniedovich (1992); this problem is called multiplicative problem. Furthermore, Peteanu (1969) and Sniedovich (1992) considered non-multiplicative type of problems with additive type. The problem with non-additive path length is called as non-additive problem. Ibaraki (1973) generalized the Dijkstra's algorithm and the Bellman's algorithm; the generalized algo­

rithms can be applied to several non-additive problems. After that, some researchers have proposed label setting algorithms and label correcting ones for solving non-additive problems (Frieze (1977), Dechter and Pearl (1985), Badadym (1990), Huckenbeck and Ruland (1991), Lengauer and Theune (1991a), Huckenbeck (1992, 1997)).

All the above methods of solution are based on dynamic programming proposed by Bellman (1957). In particular, for both additive and non-additive problems, the label correcting algorithms are methods for solving the single recursive equation in dynamic

programming. The recursive equation holds for the additive shortest path problem even if there exists a negative arc length in a given network. On the other hand, the non-additive problem does not necessarily admit the recursive equation. So, in order that the recur­

sive equation holds, one needs to restrict the arc length in the non-additive problem to some range. For example, the multiplicative problem has been solved under the restric­

tion that each arc length takes nonnegative values; this restriction implies monotonicity (nondecreasingness in the multiplication with respect to the second variable). In other non-additive problems, each arc length was also restricted to the range so that the binary operation, which defines a path length, is monotone; the monotonicity implies that the recursive equation holds for the non-additive problems.

In this thesis, we are concerned with a wide class of shortest path problems that contain various types of non-additive problems, where the monotonicity on the binary operation is not assumed. We also consider the longest path problem of finding a path of rnaximum length from an origin node to a destination node in a directed network. We assume that with each arc (

i

,

j

) ^E A an arc length

tij

is associated. Then, in the present paper, considering the length of a path p =

(1,j1,j2,

^{• • .}

,jz, N)

from

1

to

N,

which is given as follows:

where

o

^{: R1 x R1 --4} R1 is an associative binary operation:

(

^x

o y) o z

= ^x

o (yo z).

So, we solve the problem:

Opt[t1j1

o tilh

^{o · · ·}

o tizN],

p

where Opt denotes either Max or min, optimizer. Here we note that optimization above is taken for all paths from 1 to

N.

We call this problem

associative optimal path problem.

In case the binary operation

o

is additive, the problem reduces to the additive problem. If the operation is multiplicative, then the problem is the multiplicative one. Moreover, the minimum problem and the maximum problem is the case ^{o =} 1\, V, respectively, where for any real numbers

a

and

b

a

^1\

b

=min(

a, b), a

^V

b

=Max(

a, b).

The associative optimal path problem contains other types of non-additive problems: for example, the operation

o

is defined by the following:

a o b

⁼

a+ b- ab, a o b

=

t::b, ^a

^o

^b

⁼

1+(1-a)(l-b) ab ·

2

In order that the non-additive problem admits the single recursive equation in dynamic programming, the monotonicity on the binary operation:

a<b

==>

aoc'5:boc

has been assumed so far. In Chapter 2, first we give a necessary and sufficient condition for the single recurcive equation to hold or have a solution in the non-additive problem without the monotonicity condition. Next, we show the uniqueness of a solution of the equation if it exists. Moreover, we solve the associative shortest path problem satisfying the necessary and sufficient condition by a successive approximation method, which is considered to be a label correcting algorithm; the sequence constructed in the method is shown to converge to the unique solution of th recursive equation in case it exists.

In Chapter

3,

We consider the associative optimal path problems on a semigroup

(

_S,

o):

_S is a non empty subset of R1 and

o

satisfies that

o

: S ^x S ^---* S. The optimal path problems involve non-additive problems which do not admit the single recursive equation.

Up to this time, many authors have applied several algebraic structures, for example, semigroup

(

Moisil

(1960),

Tomescu

(1968),

Peteanu

(1969)),

semiring

(

Robert and Ferland

(1968),

Yoeli

(1969),

Carre

(1971))

and dioid

(

Pan and Reif

(1987, 1989),

Rote

(1990),

Lengauer

(1991b),

Jungnickel

(1994)).

These structures are applicaple to several types of path-finding problems; shortest path problems, critical

(

longest

)

path and scheduling problems and so on. However, the algebraic structures have monotonicity with respect to binary operations, which is used for defining path costs. In this chapter, we consider the associative optimal path problem with a more generalized mono tonicity

( bitonicity)

on the associative operation o, where the bitonicity means either nondecreasingness or nonincreasingness in the operation with respect to the second variable. We derive a system of two interrelated recursive equations in place of the single one. Solving the system, we find both shortest and longest path lengths. Nemhauser

(1966)

originally obtained the system of recursive equations for a multiplicative problem with negative rewards. Further, Iwamoto

(1993)

has proposed bynamic programming, which includes dynamic programming as a special case. He showed that a sequential decision process with a recursive reward system under a bitonicity condition can be solved by a system of two recursive equations. Though he applied the sequential optimization method to optimization problems with two types of objective functions: multiplicative type and 1nultiplicatively additive type, he did not deal with the optimal

path proble1n

itself. In this

chapter, according to the bynamic progran1ming, we solve the associative optimal path problems, which contain different types of problems from those considered in Iwamoto (1993). Moreover, we will propose bidecision algorithm for solving the system of recursive equations; it is regarded as a label-correcting algorithm.

In Chapter 4, we relate a given semigroup

(S,

o

)

with bitonicity to the other semigroup

(S,

_•

)

_{, where}

S

₌ c-

S,

a _•

b

₌ c-

(

c- a

)

o

(

c-

b)

for a given number ^c. First, we

investigate relations between the two semigroups. According to the relations between the two semigroups, we will propose a new optimal path problem called negative-equivalent problem for each optimal path problem called primal problem; the negative-equivalent problem constructed from a primal problem is son1etimes easier to solve than the primal problem. Further, we will derive the relation (negative-equivalency theorem) between the primal problem and the negative-equivalent one and propose a method based on the negative-equivalency theorem in order to solve the primal optimal path problem.

In Chapter 5, we consider the associative shortest path problem on the semigroup which is not imposed the bitonicity condition; If the problem does not satisfy the bitonicity condition, then it does not satisfy the monotonicity condition either. We will solve the problem through an invariant imbedding method. The invariant imbedding method has been introduced by Ambarzumian (1943, 1958) and studied extensively by Lee (1968), Bellman and Denman (1971) and others. Recently, Iwamoto (1996) has solved finite-stage stochastic dynamic programs with associative reward systems by using this method. In this chapter, first we derive a parametrized recursive equation (functional equation) for the problem, adding one-dimensional parameter at the front of path length. Next we solve the associative shortest path problem on the semigroup without the bitonicity condition, constructing a sequence which converges to the solution of the parametrized recursive equation.

References

Ahuja, R.K., Magnanti, T.L. and Orlin, J.B., (1993), Network flows, Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, New Jersey.

A1nbarzumian, V.A., (1943), Diffuse reflection of light by a foggy medium, Compt. Rend.

Acad. Sci. U.R.S.S., 38, p.229.

Ambarzumian, V.A., (1958), Theoretical Astrophysics, Pergamon Press, Oxford.

Badadym, V.A., (1990), Minimax paths and minimal spanning trees, Kibernetika (Kiev), no.2, 122.

Bellman, R.E., (1957), Dynamic progran11ning, Princeton Univ. Press, Princeton, New Jersey.

Belln1an, R.E., (1958), On a routing problem, Quart. Applied Mathematics, 16, pp.

87-90.

Bellman, R.E. and Denman, E. D., (1971), Invariant imbedding, Lecture Notes in Op­

eration Research and Mathematical Systems, Vol. 52, Springer-Verlag, Berlin.

Bertsekas, D.P., (1993), A simple and fast label-correcting algorith1n for shortest paths, Networks, 23, pp. 703-709.

Bertsekas, D.P., Guerrierc, ^F. and Musmann, ^R., (1996), Parallel asynchronous Label­

correcting methods for shortest paths, J. Optim. Theory Appl., 88 no.2, pp. 297- 320.

Carre, B.A., (1971), An algebra for network routing problems, J. Inst. Maths. Applies., 7' pp. 273-294.

Dechter, R. and Pearl, J., (1985), Generalized best-first search strategies and the opti­

mality of A*, J. Assoc. Com put. Mach., 32, pp. 505-536.

Denardo, E.V. and Fox, B.L., (1979), Shortest-route methods:l. Reaching, pruning and buckets, Operations Research, 27, pp. 161-186.

Dial, R., (1969), Algorithm 360: Shortest path forest with topological ordering, Com­

munications of ACM, 12, pp. 632-633.

Dijkstra, E.W., (1959), A note on two problems in connection with graphs, Numeriche Mathematics, 1, pp. 269-271.

Ford, L.R.Jr, (1956), Network flow theory, Report P-923, RAND Corp., Santa Monica, CA.

Ford, L.R.Jr and Fulkerson, D.R., (1962), Flows in Networks, Princeton University Press, Princeton, NJ.

Fredman, M.L. and Tarjan, R.E., (1984), F ibonacci heaps and their uses in improved network optimization algorithms, Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, pp. 338-346 (Full paper in Journal of ACM, 34, (1987)' pp. 596-615).

Frieze, A., (1977), Minimal paths in directed graphs, Opr. Res. Quart., 28, pp. 339-346.

Glover, F ., Klingman, D. and Phillips, N., (1985), A new polynomially bounded shortest path algorithm, Operations Research, 33, pp. 65-73.

Huckenbeck, U. and Ruland, D., (1991), A generalized best-first search method in graphs, In: Mohring ( ed.), Proceedings of the 16th International Workshop on Graph­

Theoretic Concepts in Computer Science (WG'90)(Berlin, 1990), Lecture Notes in Comput. Sci., 484, pp. 41-60, Springer, Berlin, Heidelberg.

Huckenbeck, U., (1992), On a generalization of the Bellman-Ford-Algorithm for acyclic graphs, Wurzburg University, Report no.41, Wurzburg.

Huckenbeck, U., (1997), Extremal Paths in Graphs, Academie Verlag.

Ibaraki, T., (1973), Solvable classes of discrete dynamic programming, J. Math. Anal.

Appl., 43, pp. 642-693.

Iwamoto, S., (1987), Theory of dynamic programs (in Japanese), Kyushu University Press.

Iwamoto, S., (1993), From dynamic programming to bynarnic programming, J. Math.

Anal. Appl., 177, pp. 56-74.

Iwamoto, S., (1996), Associative dynamic programs, J. Math. Anal. Appl., 201, pp.

195-211.

Johnson, D.B., (1982), A priority queue in which initialization and queue operations take O(log log

D)

time, Mathematical Systems Theory, 15, pp. 295-309.

Jungnickel, D., (1994), Graphen, Netzwerke und Algorithmen, 3rd edition, BI Wis­

senschaftsverlag, Mannheim, Wien, Zurich.

Lee, E.S., (1968), Quasilinearization and invariant imbedding, Academic Press.

6

Lengauer, T. and Theune, D., (1991a), Efficient algorithms for path problems with general cost criteria, In: Albert, J.L., Monien, B., Artalejo, M.R. (eds), Proceedings of the 18th International Colloquium on Automata, Languages and Programming (ICALP'91)(Madrid, 1991), Lecture Notes in Comput. Sci., 510, pp. 314-326, Springer, Berlin, Heidelberg, New York.

Lengauer, T. and Theune, D., (1991b), Unstructured path problems and the making of semirings, In: Dehne, F., Sack, J.R., Santoro (eds.), Proceedings of the 2nd Workshop on Algorithms and Data Structures (WADS'91)(0ttawa, Canada, 1991), Lecture Notes in Comput. Sci., 519, pp. 189-200, Springer, Berlin, Heidelberg, New York.

Moisil, G.C., (1960), A supra unor reprezenUiri ale grafelor ce intervin in probleme de economia transporturilor, Communidirile Acad. Republicii Populare Romine, 10, pp. 647-652.

Nemhauser, G.L., (1966) Introduction to dynamic programming, Wiley, New York.

Pan, V. and Reif, J., (1987), Fast and efficient solution of path algebra problems, Tech­

nical Report 87-3, State University of New York at Albany (SUNY), Computer Science Department.

Pan, V. and Reif, J., (1989), Fast and efficient solution of path algebra problems, J.

Comput. System Sci., 38, no.3, pp. 494-510.

Pape, U., ( 197 4), Implementation and efficiency of Moore-algorithms for the shortest route problem, Math. Prog. 7, pp. 212-222.

Pape, U., (1980), Algorithm 562: shortest path lengths, ACM Trans. Math. Software 6, pp. 450-455.

Peteanu, V., (1969), Optimal paths in networks and generalizations(!), Mathematica, 11, pp. 311-327.

Robert, P. and Ferland, J., (1968), Generalisation de l'algorithme de Warshall, Rev.

Francaise d'informatique et de recherche operationelle, 7, pp. 71-85.

Rote, G., (1990), Path problems in graphs, Comput. Suppl., 7, pp. 155-189.

Smith, D.K., (1991), Dy namic programming, Ellis Horwood Limited.

Sniedovich, M. (1992), Dy namic progrmnming, Marcel Dekker, New York.

Tomescu, I., (1968), Sur l'algoritme matricel de B. Roy, R.I. R. 0., 7, pp. 87-91.

Wagner, R.A., (1976), A shortest path algorithm for edge-sparse graphs, Journal of ACM, 23, pp. 50-57.

Yoeli, M., (1961), A note on a generalization of Boolean matrix theory, American Math.

Monthly, 68, pp. 552-557.

8

Chapter 2. Dynamic programming formulation for as­

sociative optimal path problems.

We consider a wide class of shortest path problen1s in acyclic digraphs. In the problems, the length of a path is defined by using an associative binary operation. We derive recursive equations in dynamic progra1nming for the problems, which involve additive, multiplicative, multiplicative-additive, mini1num and fractional shortest path proble1ns.

A necessary and sufficient condition and two sufficient conditions for the recursive equation to have a solution are given because for all problems the recurcive equation does not hold.

In case the equation has a solution, a sequence which converges to the solution is proposed.

1 Introduction

In this chapter, we are concerned with the problem of finding a path of minimum or maximum length from a single origin node to a few destination nodes in a directed network G(V,

A),

where V is a finite set of nodes and A is a finite set of directed arcs. Let node

1

be the origin node and let st be the set of the destination nodes: st ⁼

{i*

^E VID(i*) ⁼

0},

where D(i) ⁼

{j

^E

Vl(i,j)

^E

A}.

W ith each arc

(i,j)

^E A and each destination node

i*

^{E st} we associate

arc length (or cost)

^{tij E R} and

terminal reward k( i*)

^{E R,}

respectively. A path p from

i

to

i*

^E St is denoted by

where

A length of the path pis defined by

where

o

^: R ^x R ^� R is an associative binary operation:

(

^x

o y) o

^{z = x}

o (yo

^z

)

^.

The objective is to find a path of minimum or maximum length which starts at the node 1 and ends at some

i*

^E St:

(1)

where Opt denotes either Max or min, optimizer and pis a path from 1 to

i* E St:

Here we note that optimization in

( 1)

is taken for all paths from 1 to some

i* E St.

We call this problem

associative shortest path problem

and denote it by (ASP).

Throughout this paper, we suppose that network

G

(

N, A)

contains no cycles and that every node

i E

^V is connected to all destination nodes with a path.

If

st

is a single node set:

st

= {

N},

then the terminal reward

k( i*)

is meaningless.

So, in this case, we consider the following problem:

where

p =

(1,j1,j2, ... ,jk, N).

Let

R(

^o

)

denote a real number satisfying that

toR( o)

=

t

for all

t E

^T,

where T =

{tij o

^{· · ·}

o t ⁿ i ^• i

(

i

,

j

, ... , n,

i*):

path,

i* ESt, i tf_ St}.

Then this problem are also obtained by putting

k(i*)

=

R( o)

in the problem (ASP).

(2)

In case the binary operation

o

in (1) is additive, the problem (ASP) reduces to the well­

known problem, which we call the

additive (shortest path) problem.

In many monographs and papers, the additive problem has been effectively solved by dynanlic programming (see, for example Bellman, Esogubue and Nabeshima (1982), Dreyfus (1969)).

On the other hand, in case the operation is multiplicative, Iwamoto (1987), Smith (1991) and Sniedovich (1992) derived the recursive equation to solve the shortest path problem. Moreover, Iwamoto (1987) and Sniedovich (1992) also studied the case

o

= 1\, V, where for any real numbers ^a and

b

a 1\

b

=min(

a, b),

^{a V}

b

=Max( a,

b).

Recently, Maruyama (1996) solved a wide class of shortest path problems which contains the additive and rnultiplicative problems, but does not contain the case ^o = 1\, V.

The problem (ASP) in this paper involves not only the additive, multiplicative, nlini­

mum and maximum problems but also many other problems, for example, multiplicative­

additive and fractional ones. We will derive the recursive equations for the problem (ASP).

It is noted that the recursive equation does not necessarily hold without conditions.

10

So, in Section 2, we give a necessary and sufficient condition and two sufficient condi­

tions for the recurcive equation in (ASP) to have a solution. Furthermore, we show the uniqueness of a solution of the equation if it exists. In Section

3,

we give a sequence which converges to the unique solution in case it exists.

2 Existence and U niquness

To solve the problem (ASP), we imbed it into the following family of problems:

.*

_st

z E '

where optimization in

(3)

is taken for all path p from

i

to

i*

E

St;

(3)

In case ^o =+and st ⁼

{N},

it is well known that

{hli

E

V}

is a solution of the recursive equation

9i = Opt

[tij

+

gj] i -1- N,

9N = 0.

jED(i)

On the other hand, for all associative operation,

{hli

E V} does not satisfy the following recursive equation (see Example

5):

(4)

Theorem

¹

(necessary and sufficient condition). The set of the optimal values { fi, i

E

V} defined by (3) is a solution of

(

4) if and only if the problem

(ASP)

satisfies the following condition:

<

where - denotes

_�

and

_�

zn case

Opt = min

and

Opt = Max,

respec tively, Aj

⁼

>

{tjk

^{o · · · o}

^tni•

^o

k(i*)j(j, k,

^... ^{, n,}

i*) : path, i*

E

St} for j tj: St and

Ai. ⁼

{k(i*)} for

i*

E st.

Proof.

It suffices to show only the case Opt ⁼ min. Similarly, the case Opt ⁼ Max _is proved. We assun1e that the problem (ASP) satisfies the condition < R1 >. _Let

i rf_ st

be given but arbitrary. Let

( i, j,

k, ^{· · ·} , n,

i*)

be any path from

i

_to

i* E St.

_Then

tij o (tjk o

^{· · ·}

o tni• o k(i*))

_�

min{tij o alaE A.7}.

Further, from the condition < R1 >, _{we have}

for all

j E D(i).

It follows from (5) and

(6)

_that

fi

_2:

jED(i)

_min

[ t i1

^·

o /1·].

On the other hand, it is easily proved that

Hence from

(7),

_{we get}

fi::; jED(i) J

min

[ti· of·] J

fi

⁼

jED(i)

_min

[ti1· o /1·].

(5)

(6)

(7)

Conversely, suppose that < R1 > does not hold: there exist

i' rf_ St

_and

j' E D ( i')

such that

.i �ff, )[ti'.i o f.i]

> _min

{ t

ⁱ

'j' o alaE A.i' }.

From this and the inequality

we get

min

[ti'J. o !1·]

>

fi'.

jED(i')

Consequently,

fi'

does not satisfy

( 4).

^D

Corollary

1

(Sufficient condition). Let the problem

_(ASP)

satisfy the following con­

dition:

<R2>

ti.iof.i � Opt{ti.ioalaEAj} VjED(i), Virf_St.

Then {Jili E V} is a solution of(4).

Proof.

The condition < R2 > _implies < R1 >.

12

D

Corollary

²

(Sufficient condition). Suppose that the problem

(ASP)

satisfie s the fol­

lowing condition:

Then {fili

E

V} is a solution of (4).

Proof.

Let

i tf

St, j E ^D (

i)

be given but arbitrary. Then it holds that

fj 5

a for allaEAj.

Hence it follows from the condition ^<

R3

^> that

From this, we get

thus, ^<

R3

^> implies ^<

R2

^{>. D}

Remark

^1. In case ^{st =} { N}, we imbed the problem (ASP) into the following family of problems in place of

(3):

JN R(o).

i =IN,

So, in this case we obtain the following recursive equation instead of

(4):

Ji

⁼ Opt

[ ti

j

o jj]

jED(i) (8)

Remark

^2. If the associative operation

o

is monotone on Rat each

a

E R: ^b, c E ^{R, b <}

c ===?

a o b :::; a o

c, then the problem (ASP) satisfies the condition ^< R3 ^>. Hence in this

case, from Corollary ² in this chapter, we see that {!iii E V} is a solution of

(4).

For example, addition is monotone on ^R at each

a

^{E R.} Therefore the recursive equation

( 4)

holds for the additive problem.

Remark

^3. The implication is

It should be noted that a gap exists between these conditions.

Example

¹

(Minimum problem). We consider the case o =

^1\.

Since this operation is monotone on R at each a

E

R, we have

Put

fi = Opt [tij

^1\

fj]

jED(i)

R(l\) = Max{tijJi,j

E V,

(i,j)

E

A}.

Then R(/\) satisfies (2). Hence in case st = {N}, from (8) we obtain i # N, fN = R(l\).

(9)

(10)

On the other hand, replacing

^1\

by

^V

yields Maximum problem. Similarly, the results corresponding to (9) and (10) holds for this problem, where R(l\) in (10) are replaced with

R(V) = min{tijJi,j

E V,

(i,j)

E

A}.

Example

²

(Multiplicative-additive problem). In this example, we consider the fol­

lowing associative operation: a o b

=

ab +a+ b. We suppose that

tij +

¹

�

^o

Vi, j rf st. ( 11)

Then the problem (ASP) satisfies the condition

<

R3

>.

Hence from Corollary 2, we have fi = Opt [(tij + 1)(fj + 1)- 1]

jED(i)

For 0(= R(o)), (2) holds. Hence in case

^st

= {N}, from (8), we obtain fi = Opt [(tij + 1)(fj + 1)- 1],

jED(i) i # N, !N = 0.

(12)

(13)

Rem,ark

4. Iwamoto (1996) has introduced the operation : aob = ab+a+b in associative dynamic programs. Now let us propose the following one pararneter associative operation:

a o b = f ( s; a, b) = ab + s (a + b + s - 1).

Then the operation

:

a o b = ab +a+ b and the multiplication are unified into it. If we suppose

we obtain recursive equations with the parameters which are similar to (12), (13).

Example

3

(Fractional problem). Let us consider the following asssociative opera­

tion: a o b

⁼

(a+ b)l(1 + ab). We assume that

{ ^k(i*) _t··

_{t] -}^2: _>

⁰ ₀

1

^> -

t·.

t] -^>

0

for i* E

St

}

for i tf_

St,,

j E

D

( i), for j tf_

st.

Then the problem (ASP) satisfies the condition

^<

R3 >. Hence fron1 Corollary 2, we get

For 0(= R(o)), (2) holds. So, in case

St =

{N}, from (8), we have fi = Opt [ ^{tij + fj} ]

jED(i) 1+tijjj

(14)

(15)

Remark 5. One paran1eter associative operation which contains the operation: a

^o

b = (a + b) I ( 1 + ab) is as follows:

b

^_

( . b)

^_

a + b + (

^{s -}

2) ab a

⁰

-

g 8'

a' -

1

+

(

^{s -}

1) ab

^·

Klir and Folger (1988) and Butnariu and Klement (1993) referred to this operation in their monographs. Under some condition on tij we have recursive equations with one parameter

^s

which are similar to (14) , (15).

In all examples stated above, {fili E V} is a solution of the recursive equation ( 4). In what follows, we illustrate some examples in which (ASP) does not satisfy the condition

<

R1 >;hence it follows from Theorem 1 that {fili E V} is not a solution of (4) .

Example

4.

In this example we show that the problem (ASP) with the sa1ne network satisfies or does not satisfy the condition

^<

R1 >, depending on the choice of optin1izer.

Let us consider the fractional shortest path proble1n (

^a o

b = (a+ b) I (1 + ab), Opt =min) on a network given in Fig.l.

We have

Hence we get

(1

^0-0

1 0)

(\

(1

⁰

2

0

0)

(\

(1

0

2

0

0) = 1,

2

(1

⁰

2

0

0)

(\

(1

0

2

0

0)

(\

( -

1 0

3

⁰

0) = 1.

2

min{t13 o alaE A3} = (2

o

1)

1\

(2

o

1)

1\

(2

o

�) = 17

^<

1

⁼

min [t1j o jj],

5 19 jED(l)

2

2

1

1

2 1

2

1

2

2

3

Figure

1:

directed network thus, this problem does not satisfy the condition <

R1

>.

k(7)

^{= 0}

k(8)

^{= 0}

On the other hand, if we consider the fractional

longest

path problen1

(a o b

=

(a

⁺

b)/(1

⁺

ab),

Opt =

Max)

on the network given in Fig.1, then the problem satisfies the condition <

R1

>

.

In fact, we have

Hence we get

Therefore,

/2 =

1

^v

1

^{v 1} =

1' 7 7

/3=1V1V-=-.

5 5

7 17

Max [t11 o j1]

=

[2 o 1]

^V

[2 o -]

=

1

V- =

1.

jED(1)

⁵

₁₉

Similarly, we can show that

Jf-J-(�)[tij o fj] _2:: Max{tih o alaE Aj1}

^{for all}

j1 E D(i), i /= 1,

thus, this problem satisfies the condition <

R1

>.

16

In view of Example 4, we introduce the following notation: As(min) and As(Max) denote all problems satisfying the condition < R1 > in case Opt = rnin and Opt = Max, respectively.

If the problem (ASP) satisfies the condition < R3 > , then it belongs to both As (min) and As(Max) ((ASP)

E

As(rnin) n As(Max)). Therefore, all the problems which we considered in Examples 1 ^rv

3

belong to both. On the other hand, the problern in Example

4

belongs to As(Max) but does not belong to As(rnin). Similarly, we can Lake an example of the problern satisfying that (ASP) E As(rnin) and (ASP) tf_ As(Max). Further, in the following example, we illustrate a problem which belongs to neither As(min) nor As(Max).

Example 5. Let us replace only the arc length t24 with

�

in the network given in Fig.l.

Then we consider the fractional problem:

a o b

⁼

(a+ b)/

( 1

+ ab)

on the changed network.

If Opt ⁼ min, then we obtain

Hence we have

1 1 4 4

(- 0-

)

_{1\ (1 0}

2)

_{1\ (1 0}

2)

₌

-

1\ 1/\ 1 = -,

2 2

_{5 5}

1 7

(1 0

2)

_{1\ (1 0}

2)

_{1\ (}

-

₀

3)

= 1/\ 1/\- = 1.

2

₅

. 7 17

m1n{t13

o alaE

A3} =

(2 o

1) 1\

(2 o -

_{) =- < 1 = min}

[t1j o jj],

5 19

jED(l)

thus, this problern does not satisfy the condition < R1 > in case Opt = min. Conse­

quently, it does not belong to As (min).

Similarly we can show that this problem does not satisfy the condition <

R1

> in case Opt= Max, thus, it does not belong to As(Max).

From now on, we consider only the problern which belongs to As(Max) or As(rnin);

hence we do not touch on such a problem as stated in Exarnple 5. With this in mind, we will next discuss the existence and uniqueness of the solution of (

4).

Lemma 1. Let

{aj}JEJ, {bj}jEJ, {cj}jEJ

C Rand put d ⁼

OptjEJ[aj o bj],

e

=

OptjEJ[aj o Cj],

where

o

is an associative operator and J is a finite indexing set. Then there exists an index j

E

J such that

ld-el

< _-

la·ob·-a·oc·l

_{] ] J ] '}

(16)

Moreover, if

bj # cj,

then there exists a positive number

aj

satisfying that

(17)

Proof. Take

k

and

l

satisfying

(18) Then we have

(19) From (18) and

(19),

we obtain

This leads us to

(20)

Take

j

satisfying that

Then

(16)

follows.

Furthermore if

bJ f CJ,

^then

lbJ - CJ I

^{> 0.} Hence there exists a sufficiently large, positive number

aJ

satisfying that

Ia· ob·- a· oc-1

J J J J ^<

a·lb·- c·l

J J J •

Combining this with

(16),

we obtain the inequality (17). D

Theorem

²

(Existence and uniquness).

Let the problem (ASP) belong to As(min) or

As(Max).

Then there exists a unique solution of (

4),

where optimizer in (

4)

is min and Max _{in case (ASP)} E

As(min)

^{and (ASP) E}

As(Max),

respectively.

Proof. F irst, from the assumption and Theorem

1,

it follows that

{fili

^E V} defined by

(3)

is one solution of (

4),

where all optimizers are min and

Max

^if

(ASP)

^E

As

(min) and

As(Max),

respectively.

Second let us show that there can not be two different solutions of

(4).

We suppose that

{!iii

^{E V} and}

{gili

^E V} are two solutions of

(4).

Let

i tf_

^st be an arbitrary but fixed node and put

Then it follows from Lemma 1 that there exists j

E

^D (

i)

such that (

i,

j)

E A

and

(21) Suppose that

j1 =/= 91.

Then j tj_ St. From this and (

16)

in Lemma

1,

we obtain

If

fk

⁼

gk,

then from this inequality, it follows that

fj

⁼

gj,

which contradicts the assumption. Hence

fk =/= 9k·

So it follows fron1 (17) that there exists

ak

^{> 0} such that

By continuing in the Saine manner, we obtain

(22)

where (j, k, l,

.

^.

. , n)

is a path,

ft =/= 9l, ... , fn =/= 9n,

and at, . .

. , an

^{> 0.} Since

G(V, A)

contains no cycles,

nEst

for a finite number of repetHions. Hence

fn

=

9n

⁼ k(n), which contradicts (22). Therefore we conclude that

fj

⁼

9]·

From this and (21), it follows that

fi

⁼

9i·

Since

i

is arbitrary node of

V,

the two solutions are in fact identical, which

completes the proof. 0

Through the recursive equation ( 4), we can define the minin1um (maxi1nun1) decision function 1r as follows:

n(

i

) ⁼ the node j

E V

which attains the mjnimum(Inaximum) of r.h.s. of ( 4).

Hence, optimal decision function n

(

^·

)

generate a shortest (longest) path (

i,), k, ... , m, n); n E st

^as follows:

3 Successive approximation method

In this section we generate a sequence which converges to the solution of the recursive equation ( 4); the solution found by using the sequence gives us the desired 1ninimal or

maximal path lengths for the reason that the optimal path lengths comprise a solution of

( 4)

and the solution of it is unique.

The sequence

{ fi(k) (

^·

^)}, k

^{= 0,}

^{1, 2,} ..

. , which converges to the solution of

( 4)

can be described as follows:

where

D(i)

=

{j E Vl( ^i,j) E ^A}.

i* E St, ^fi(k)

^{= Opt}

[tij

^o

^J ) ^k- l ⁾ ] jED( i)

(23)

(24)

Theorem

³

(Successive approximation). Suppose that the problem (ASP) belongs to As(min) or As(Max). Let {Ji(k) }, k

^{= 0,}

1, 2, ... , be the sequence generated by (23), (24).

Then the sequence converges to the unique solution of ( 4), where opti1nizer in ( 4) ^{and (24)} is

min

and

Max

in case (ASP) E As(min) and (ASP) E ^As(Max), respectively.

Proof.

Let

i tf_ St

be given but arbitrary. Let

ki

denote maximum of the nu1nber of arcs used when we move along paths from

i

to the destination nodes and

k

be fixed but arbitrary number such that

ki :::; k.

Then in the same way as in the proof of Theorem

2,

we can show that for each

i ¢ st

there exists a path

such that

where

D ^j( - )

^{> 0.}

p =

(i,j(1),j(2), ... ,j(l))

lf ..

•

^ck) _ _f.

•

ck-l)l

<

I tij(l)

⁰

1ck-l) ^j(l) - tij(l)

⁰

1ck-2)l ^j(l) I ^{f(k-l) 1ck-l-l)} I

<

Dj(2)Dj(3)

^{· · ·}

Dj(l) j(l) - j(l) '

If

j(l) ESt,

then from

(25),

we obtain

f(k)

't ₌

f(k-l)

't ^•

In case j

(l) tf_ st,

take

l

=

ki - ^1.

Then since

D(j (l))

^c

st,

^{we have}

f(k-l) - f(k-l-l)

j(l) - j(l)

- - _jED(j(l))

^{0 pt}

- [ ^tij

⁰

k( .)]

^{J -}

- ^tij•

⁰

_k ^(j•)·

20

(25)

(26)

Hence, from (25) we see that (26) holds even if j (l) tf_ St. Consequently, for each i tf_ st (27)

Hence, for each i tf_ st the sequence {fi(k)} converges to the real number fi(ki-1). Put

M

a xi

i1^St

ki

=

k. Then from (27) we obtain

[ _(k-1)] - [ _(k)]

Opt tij

o

Jj - _{Opt tij}

o

fj

jED(i) jED(i)

k(i*)

Therefore, {Ji(k)li

^E

V} is the solution of (4).

D

Remark

6.

Let k be the same nun1ber

^as

in the proof in Theorem 3 and

N

be potency of the set V. Then since k ::::;

N

-

_1,

the sequence generated by (23), (24) converges in at 1nost

N

-

₁

steps.

Corollary

3.

Let the problem (ASP) satisfy the assumption of Theorem

3.

Let {fi(k)} be the sequence generated by (24) and the following:

.* st

z E '

fi

(0) ⁼

Opt tij

jED(i) (28)

Then the sequence converges to the unique solution of ( 4) , where optimizer in ( 4), (24) and (28) is min and

Max

in case (ASP)

^E

As(min) and (ASP)

^E

As(Max), respectively.

Proof. Since for i tf_ st' _fi(O)

=

OptjED(i) tij

^E

R, it follows from Theorem 3 that the sequence generated by (24) and (28) converges to the solution of ( 4).

D

Corollary

4.

Let the problem (ASP) satisfy the following condition:

(a) k(i*)

=

R(

o

) i*

E

st

₎

(b) each tij and R(

o

) belong to a set A' such that (A',

o

) zs a semigroup(, that is,

o

: A'

^x

A'

^�

A' , associative operation),

(c) the associative operation is monotone on A'

c

Rat each tij, i, j tf_ St:

a, b

^E

A', a ::::;

b ^===?

tij

o

a � tij

o b.

Then the meaning of fi(n) generated by (28) and (24) is as follows:

fi(n)

⁼

the length of the shortest(longest) path from node i to reachable node or to i*

E

st when

ⁿ + 1

or fewer arcs are used) respectively) (29)

Proof.

We will show only the case Opt ⁼ n1in. In the san1e manner, the case Opt ⁼ Max is proved. Fro1n

(28)

and

(

^a

)

^,

(29)

holds for ^{n =} 0. Assu1ne

(29)

is true for ^{n =} k- 1.

Then We will show the san1e for ^{n =} k.

Suppose that there exists a path

( i, J1, j2, ... , jz, Jt+d,

l

:s;

k such that

(30) where in case l ^< k, then

Jl+l

E St. It follows from

(24)

that

t·. _'L]l 0

f�k-1)

_]l >

- f�k)

t . (31)

Hence from (30), we have

Therefore it follows from

(b),

(c) and the inductive assumption that

where in case

l

^< k, then

JL+l

^E St. This contradicts the assumption of

J};-l).

Conse­

quently, we get

(32)

where p ⁼

(i, j1, J2, ... , Jz, Jt+d.

On the other hand, the reverse inequality to (32) follows frorn the definition of

fi(k)

and the inductive assumption. Consequently,

(29)

also holds for ⁿ = k, which completes the proof.

Let

the node

j

E V which attains the minin1um(maximum) of r.h.s.

of the second equation in

(24).

D

(33)

Then in the same way as in Section 2, optimal decision function

1r(k)

( ⁰

)

generates the shortest (longest) path from node

i

to reachable node or to destination node when

k

_{+ 1} or fewer arcs are used, respectively.

Example 6 (a ^o b = (a+ b)/(1 + ab), Opt= min). We consider an example of a network given in Figo2. T he sequence

{fi(k)}, ^k

⁼ 0, 1, 2, 0 0 0, can be computed successively as shown in Table 1. Since

J?)

=

fi(k), ^{k 2::}

3, i = 1 ^rv 8, we obtain

/i

⁼

J?),

i = 1 ^rv 8. We remark that since this problern satisfies the assumptions of Corollary 4, each

fi(k)

has such meaning as in (29)0 For each

i

_{the node}

1f(k)(i)

is presented in Table 20 Using the optimal decision function

1f(k)(·),

we can determine the shortest path (1, 2,

5, 7)0

l

2 1

4 1

3 1 l

3 1

2

l

1

3

Figure 2: directed network

k(7)

= 0

k(8)

= 0

Table 1:

Node

fi(O) fP) !?)

⁼

^{]i fi(3)}

1 l .]___ II II

2

r �3 _{� �}

3

i � � �

4 3 3 3

4 2 2 2 2

5

2

^I

2

^I

2

¹

2

¹

6 3 3 3 3

7 0 0 0 0

8 0 0 0 0

Table 2:

Node

1f(l)(i) 1f(2)(i)

1 2 2

2 5 5

3 5 5

4 7 7

5 7 7

6 8 8

References

Bellman, R., Esogbue, A.O. and Nabeshima, I., (1982), Mathematical Aspects of Schedul­

ing and Applications, Pergamon Press, New York.

Butnariu, D. and Klement, E.P., (1993), 'Itiangular norm-based n1easures and games w ith fuzzy coalitions, Kluwer Academic Publishers.

Dreyfus, S.E., (1969), An appraisal of some shortest-path algorithms, Oper. Res., 17, pp.395-412.

Iwamoto, S., (1987), Theory of Dynamic Programs (in Japanese), Kyushu University Press.

Iwamoto, S., (1996), Associative dynamic programs, J. Math. Anal. Appl., 201, pp.195- 211.

Klir, G.J. and Folger, T.A., (1988), Fuzzy sets, uncertainty and information, Prentice Hall.

24

Maruyama, Y., (1996), Shortest and longest path problems, Optimization, 38, pp.287- 299.

Smith, D.K., (1991), Dynamic Progran1ming, Ellis Horwood Limited.

Sniedovich, M., (1992), Dynamic Programming, Marcel Dekker.

Chapter 3. Bynamic programming formulation for as­

sociative optimal path problems.

In this chapter we consider a wide class of shortest path problems where the length of a path is defined through various associative binary operations. Solving a system of two interrelated recursive equations, we sin1ultaneously find both shortest and longest path lengths. We show the existence and uniqueness of the solution of the system. Further, we propose an algorithm which solves the class of shortest path problems.

1 Introduction

In the so-called shortest path problem, the objective is to find a path of n1inimum length from an origin node 1 to a destination node

N

^{in a network}

G(V, A); V

and A are finite sets of nodes numbered 1, 2,

.

^{.. , N} and of directed arcs, resp ctively. With each arc

(i,j)

^{E A} an arc length (or cost,

..

^.

) tij

is associated. Many authors have studied the problem in which the length of a path is the sum of its arc lengths (Dreyfus (1969), Belhnan, Esogbue and Nabeshima (1982)):

additive problem.

They solved the additive problem by using the recursive equation

where

Ji

⁼

jED(i)

^min

[ti1·

⁺

!1·], i # N, !N

⁼

0,

fi

^{= min}

[

^{tij +}

t

^{jk + · · · +}

tmNJ,

^{p =}

(i,j,

^k, ... ^{, m,}

N), ^D(i)

⁼

^{j

^E

^Vl(i,j)

^E

A}.

p

(1)

Since the addition + satisfies the monotonicity conditjon (nondecreasingness with respect to the second variable) on R1, the recursive equation (1) holds even if

tij

1nay be negative.

Some authors considered the problem where the length of a path is the multiplication of its arc lengths (Iwamoto (1987), Smith (1991), Sniedovich (1992)):

1nultiplicative problem.

They have solved the multiplicative problem under the restriction that each arc length takes the nonnegative value

(

^ti

j 2:: 0).

Since the restriction i1nplies the monotonicity in the operation o = x, the n1ultiplicative problem can be also solved by the single recursive equation

fi

⁼

jED(i)

^min

[ t i1·

^x

!1·], i # N, !N

^{= 1.}

(2)

where

fi

= ^In_p in

[

tⁱj ^X tjk ^{X ··· X} tmN

]

, p =

(i,j,

^k,

.

.

.

^{, m,}

N).

But for the case son1e tij ^< 0, the equation (2) does not necessarily hold (see Ren1ark in Section 2). Recently, Iwamoto (1993) has proposed bynamic programming which contains the multiplicative programming and the multiplicatively additive one. So, through the bynamic programming, Maruyama (1996) has solved the multiplicatively additive shortest path problen1, where a pair of arc length and discount rate is associated with each arc. The shortest path problem involves the multiplicative shortest path problem with a negative arc length as a speial case. However, these papers (Iwamoto (1993), Maruyan1a (1996)) treated only the optimization problems for objective functions with the multiplicatively additive value and the multiplicative one.

In this chapter, we consider a wide class of shortest path problems (called associative shortest path problem (ASP) ) with the length

(3)

for a path p =

(

i,j, k, ... , m,

N)

where

o: R

^x

R----*

^R is an associative binary operation:

(

^x

o y) o

^z = ^x

o (yo

^z

)

^. The problem (ASP) includes not only the 1nultiplicative proble1n with a negative arc length but also many other problems, for example, 111aximum problen1, multiplicative-additive problem, fractional problem and so on, which were not studied in Iwamoto (1993) or Maruyama (1996). On the other hand, Frieze (1977) considered a wider class of shortest path problems where path length is defined as a real valued function defined on paths; the class contains the additive problem, the n1aximum problem and problem with time dependent arc lengths. Under certain 1nonotonicity condition, the class of problems was solved by using some single recursive equation. Further, in Maruya1na (1997), we derived a necessary and sufficient condition for the associative shortest path problem (ASP) to admit the single recursive equation

(4)

where

and

R( o)

is a right identity: a

o R( o)

= a Va E S and solved the problem (ASP) by the Ford's procedure under the necessary and sufficient condition; of course, (

4)

does not hold for (ASP) which does not satisfy the condition, (see Remark and Examples in Section 2).