123
Art Lew
Holger Mauch
Dynamic Programming
A Computational Tool
With 55 Figures and 5 Tables
I
SS
N electronic edition: 1860-
9
503
This work is subject to copyright. All rights are
reserved, whether the whole or part of the mate-
rial is concerned, specifically the rights of tran
jpygg
jpygg
slation, reprinting, reuse
o
f
i
ll
ustrations, recita
-
p
tion, broadcasting, reproduction on microfilm or in any other way, and storage in data banks.
pygpyg
pgg
Duplication of this publication
gp
gp
or parts thereof is permitted on
y
y
ly under the provisions of the
yg
yg
German Copyright Law of Septem
pp
p
ber 9, 1965, in its current version, and permission for use
pp
p
yp
p
must always be obtained from Springer-Verlag. Violations are liable to prosecution under the
py g ppy g
p
p
G
erman Cop
y
ri
gh
t Law.
y
Springer is a part of Springer Science+Business Media
springer.com
The use of general descriptive names, registered
names, trademarks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from
gp g
gp g
p
p
the relevant protective laws and regulations and therefore free for general use.
py p
py p
5 4
3
2
1
0
C
over
d
esi
g
n:
d
e
bl
i
k
, Ber
l
in
ISSN print e
d
ition: 1860-949X
Typesetting by the authors and SPi
g
8
9/SP
i
Library of Congress Control Number: 2006930743
ISBN-10 3-540-37013-7 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-37013-0 Springer Berlin Heidelberg New York
Printedddd on acid-ffree paper SPIN: 11550860
Prof. Art Lew
Computer Sciences
Department of Information
University of Hawaii at Manoa
96822 Honolulu, HI
USA
E-mail:
artlew@hawaii.edu
Dr. Holger Mauch
Department of Computer Science
Natural Sciences Collegium
Eckerd College
USA
33711 Saint Petersburg, FL
E-mail:
mauchh@eckerd.edu
©© Springer-Verlag Berlin Heidelberg 2007pgggg
and
4200, 54th Ave. S.
1680 East-West Road
To the Bellman Continuum, in memory of Richard Bellman. A.L.
To my family. H.M.
Preface
Dynamic programming has long been applied to numerous areas in mathe-
matics, science, engineering, business, medicine, information systems, bio-
mathematics, artificial intelligence, among others. Applications of dynamic
programming have increased as recent advances have been made in areas such
as neural networks, data mining, soft computing, and other areas of compu-
tational intelligence. The value of dynamic programming formulations and
means to obtain their computational solutions has never been greater.
This book describes the use of dynamic programming as a computational
tool to solve discrete optimization problems.
(1) We first formulate large classes of discrete optimization problems in
dynamic programming terms, specifically by deriving the dynamic program-
ming functional equations (DPFEs) that solve these problems. A text-based
language, gDPS, for expressing these DPFEs is introduced. gDPS may be
regarded as a high-level specification language, not a conventional procedural
computer programming language, but which can be used to obtain numerical
solutions.
(2) We then define and examine properties of Bellman nets, a class of Petri
nets that serves both as a formal theoretical model of dynamic programming
problems, and as an internal computer data structure representation of the
DPFEs that solve these problems.
(3) We also describe the design, implementation, and use of a software tool,
called DP2PN2Solver, for solving DPFEs. DP2PN2Solver may be regarded as
a program generator, whose input is a DPFE, expressed in the input specifi-
cation language gDPS and internally represented as a Bellman net, and whose
output is its numerical solution that is produced indirectly by the generation
of “solver” code, which when executed yields the desired solution.
This book should be of value to different classes of readers: students, in-
structors, practitioners, and researchers. We first provide a tutorial intro-
duction to dynamic programming and to Petri nets. For those interested in
dynamic programming, we provide a useful software tool that allows them to
obtain numerical solutions. For researchers having an interest in the fields of
VIII Preface
dynamic programming and Petri nets, unlike most past work which applies
dynamic programming to solve Petri net problems, we suggest ways to apply
Petri nets to solve dynamic programming problems.
For students and instructors of courses in which dynamic programming
is taught, usually as one of many other problem-solving methods, this book
provides a wealth of examples that show how discrete optimization problems
can be formulated in dynamic programming terms. Dynamic programming
has been and continues to be taught as an “art”, where how to use it must
be learned by example, there being no mechanical way to apply knowledge
of the general principles (e.g., the principle of optimality) to new unfamiliar
problems. Experience has shown that the greater the number and variety
of problems presented, the easier it is for students to apply general concepts.
Thus, one objective of this book is to include many and more diverse examples.
A further distinguishing feature of this book is that, for all of these examples,
we not only formulate the DP equations but also show their computational
solutions, exhibiting computer programs (in our specification language) as well
as providing as output numerical answers (as produced by the automatically
generated solver code).
In addition, we provide students and instructors with a software tool
(DP2PN2Solver) that enables them to obtain numerical solutions of dynamic
programming problems without requiring them to have much computer pro-
gramming knowledge and experience. This software tool can be downloaded
from either of the following websites:
http://natsci.eckerd.edu/∼mauchh/Research/DP2PN2Solver
http://www2.hawaii.edu/∼icl/DP2PN2Solver
Further information is given in Appendix B. Having such software support
allows them to focus on dynamic programming rather than on computer pro-
gramming. Since many problems can be solved by different dynamic program-
ming formulations, the availability of such a computational tool, that makes it
easier for readers to experiment with their own formulations, is a useful aid
to learning.
The DP2PN2Solver tool also enables practitioners to obtain numerical
solutions of dynamic programming problems of interest to them without
requiring them to write conventional computer programs. Their time, of
course, is better spent on problem formulation and analysis than on program
design and debugging. This tool allows them to verify that their formulations
are correct, and to revise them as may be necessary in their problem solving
efforts. The main limitation of this (and any) dynamic programming tool for
many practical problems is the size of the state space. Even in this event,
the tool may prove useful in the formulation stage to initially test ideas on
simplified scaled-down problems.
As a program generator, DP2PN2Solver is flexible, permitting alternate
front-ends and back-ends. Inputs other than in the gDPS language are possi-
ble. Alternative DPFE specifications can be translated into gDPS or directly
