Dynamic Programming: A Computational Tool

Front Cover
Springer Science & Business Media, Oct 9, 2006 - Computers - 379 pages
0 Reviews
Dynamic programming has long been applied to numerous areas in mat- matics, science, engineering, business, medicine, information systems, b- mathematics, arti?cial 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 com- 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 ?rst formulate large classes of discrete optimization problems in dynamic programming terms, speci?cally by deriving the dynamic progr- 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 speci?cation language, not a conventional procedural computer programming language, but which can be used to obtain numerical solutions. (2)Wethende?neandexaminepropertiesofBellmannets,aclassofPetri 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)Wealsodescribethedesign,implementation,anduseofasoftwaretool, calledDP2PN2Solver, for solving DPFEs. DP2PN2Solver may be regarded as a program generator, whose input is a DPFE, expressed in the input spec- 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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction to Dynamic Programming
3
11 Principles of Dynamic Programming
5
111 Sequential Decision Processes
6
112 Dynamic Programming Functional Equations
9
113 The Elements of Dynamic Programming
11
Linear Search
12
115 Problem Formulation and Solution
14
116 State Transition Graph Model
17
437 gDPS source for REPLACE
186
438 gDPS source for SCP
187
439 gDPS source for SEEK
189
440 gDPS source for SEGLINE
190
441 gDPS source for SEGPAGE
192
442 gDPS source for SELECT
193
443 gDPS source for SPA
194
444 gDPS source for SPC
196

117 Staged Decisions
19
118 PathStates
21
119 Relaxation
22
1110 Shortest Path Problems
23
1111 AllPairs Shortest Paths
29
1112 State Space Generation
30
1113 Complexity
31
1114 Greedy Algorithms
32
1116 Nonoptimization Problems
33
1117 Concluding Remarks
34
121 Solution by Conventional Programming
35
122 The StateDecisionRewardTransformation Table
36
123 Code Generation
38
SPA
40
126 Concluding Remarks
42
Applications of Dynamic Programming
44
21 Optimal Allotment Problem ALLOT
49
22 AllPairs Shortest Paths Problem APSP
50
23 Optimal Alphabetic RadixCode Tree Problem ARC
51
24 Assembly Line Balancing ASMBAL
52
25 Optimal Assignment Problem ASSIGN
54
26 Optimal Binary Search Tree Problem BST
55
27 Optimal Covering Problem COV
57
29 Discounted Profits Problem DPP
58
210 Edit Distance Problem EDP
59
211 Fibonacci Recurrence Relation FIB
60
212 Flowshop Problem FLOWSHOP
61
213 Tower of Hanoi Problem HANOI
62
214 Integer Linear Programming ILP
63
215 Integer Knapsack as ILP Problem ILPKNAP
64
217 Inventory Problem INVENT
66
218 Optimal Investment Problem INVEST
67
Winning in Las Vegas Problem INVESTWLV
68
220 01 Knapsack Problem KS01
69
221 COV as KSINT Problem KSCOV
70
223 Longest Common Subsequence LCS
71
224 Optimal Linear Search Problem LINSRC
73
226 Longest Simple Path Problem LSP
74
227 Matrix Chain Multiplication Problem MCM
75
229 Minimum Weight Spanning Tree Problem MWST
77
230 The Game of NIM NIM
78
231 Optimal Distribution Problem ODP
80
232 Optimal Permutation Problem PERM
81
233 JugPouring Problem POUR
82
234 Optimal Production Problem PROD
83
Reject Allowances Problem PRODRAP
84
237 Replacement Problem REPLACE
85
238 Stagecoach Problem SCP
86
239 Seek Disk Scheduling Problem SEEK
87
240 Segmented Curve Fitting Problem SEGLINE
88
241 Program Segmentation Problem SEGPAGE
91
242 Optimal Selection Problem SELECT
94
243 Shortest Path in an Acyclic Graph SPA
95
245 Process Scheduling Problem SPT
97
246 Transportation Problem TRANSPO
98
247 Traveling Salesman Problem TSP
99
Modeling of DP Problems
101
The DP Specification Language gDPS
103
32 Design Principles of gDPS
105
33 Detailed Description of the gDPS Sections
106
333 Set Variables Section
108
334 General Functions Section
109
335 State Type Section
110
337 Decision Space Section
111
339 DPFE Base Section
112
3310 DPFE Section
113
3311 CostReward Function Section
115
3313 Transition Weight Section
116
34 BNF Grammar of the gDPS language
117
DP Problem Specifications in gDPS
124
42 gDPS source for APSP
128
43 gDPS source for ARC
131
44 gDPS source for ASMBAL
132
45 gDPS source for ASSIGN
135
46 gDPS source for BST
136
47 gDPS source for COV
138
48 gDPS source for DEADLINE
139
49 gDPS source for DPP
140
410 gDPS source for EDP
141
411 gDPS source for FIB
144
413 gDPS source for HANOI
145
414 gDPS source for ILP
146
415 gDPS source for ILPKNAP
148
416 gDPS source for INTVL
150
417 gDPS source for INVENT
154
418 gDPS source for INVEST
156
419 gDPS source for INVESTWLV
157
420 gDPS source for KS01
158
421 gDPS source for KSCOV
159
422 gDPS source for KSINT
160
423 gDPS source for LCS
161
424 gDPS source for LINSRC
165
425 gDPS source for LOT
167
426 gDPS source for LSP
168
427 gDPS source for MCM
170
428 gDPS source for MINMAX
171
429 gDPS source for MWST
173
430 gDPS source for NIM
176
432 gDPS source for PERM
178
433 gDPS source for POUR
179
434 gDPS source for PROD
181
435 gDPS source for PRODRAP
182
436 gDPS source for RDP
184
445 gDPS source for SPT
199
446 gDPS source for TRANSPO
200
447 gDPS source for TSP
201
Bellman Nets A Class of Petri Nets
205
512 Highlevel Petri Nets
207
513 Colored Petri Nets
208
514 Petri Net Properties
209
515 Petri Net Software
210
53 The LowLevel Bellman Net Model
212
532 The Role of Transitions in the LowLevel Bellman Net Model
213
534 The Role of Markings in the LowLevel Bellman Net Model
214
55 The HighLevel Bellman Net Model
215
56 HighLevel Bellman Net Properties
219
Bellman Net Representations of DP Problems
221
61 Graphical Representation of LowLevel Bellman Net Examples
222
613 LowLevel Bellman Net for MCM
224
615 LowLevel Bellman Net for PERM
227
616 LowLevel Bellman Net for SPA
228
621 HighLevel Bellman Net for EDP
230
623 HighLevel Bellman Net for KS01
231
625 HighLevel Bellman Net for LINSRC
234
626 HighLevel Bellman Net for LSP
235
627 HighLevel Bellman Net for MCM
236
628 HighLevel Bellman Net for RDP
238
6210 HighLevel Bellman Net for SPA
240
6211 HighLevel Bellman Net for SPC
242
Design and Implementation of DP Tool
245
DP2PN2Solver Tool
246
72 Internal Representation of Bellman Nets
251
73 Compiling and Executing DP Programs
252
74 The ILP2gDPS Preprocessor Module
255
DP2PN Parser and Builder
259
82 Implementation of the DP2PN modules
260
83 The Module LINSRCSMain
263
84 Error Detection in DP2PN
268
The PN2Solver Modules
270
92 The PN2Java Module
273
921 Java Solver Code Calculation Objects
274
922 Java Solver Code for LINSRCS
276
923 Java Solver Code for LSP
278
925 Java Solver Code for SPA
280
93 The PN2Spreadsheet Module
281
931 PN2Spreadsheet Solver Code for LINSRCS
282
932 PN2Spreadsheet Solver Code for Other Examples
284
941 Petri Net Solver Code for LINSRCS
285
942 Petri Net Solver Code for SPA
288
95 Conclusion
289
Computational Results
290
Java Solver Results of DP Problems
291
102 APSP Java Solver Output
294
103 ARC Java Solver Output
296
105 ASSIGN Java Solver Output
297
107 COV Java Solver Output
298
109 DPP Java Solver Output
299
1012 FLOWSHOP Java Solver Output
300
1014 ILP Java Solver Output
301
1016 INTVL Java Solver Output
302
1017 INVENT Java Solver Output
303
1018 INVEST Java Solver Output
304
1020 KS01 Java Solver Output
305
1021 KSCOV Java Solver Output
306
1024 LINSRC Java Solver Output
307
1025 LOT Java Solver Output
308
1028 MINMAX Java Solver Output
309
1031 ODP Java Solver Output
312
1034 PROD Java Solver Output
313
1035 PRODRAP Java Solver Output
314
1037 REPLACE Java Solver Output
315
1040 SEGLINE Java Solver Output
316
1042 SELECT Java Solver Output
317
1044 SPC Java Solver Output
318
1046 TRANSPO Java Solver Output
319
Other Solver Results
321
1112 PN2Spreadsheet Solver Code for LSP
322
1114 PN2Spreadsheet Solver Code for SPA
323
112 PN2XML Solver Code Output
324
1121 PN2XML Simulation Output for LINSRCS
325
Conclusions
329
122 The DP2PN2Solver Tool
330
123 Research Directions
332
1231 User Functionality
333
1232 Reduction of Dimensionality
334
1233 Petri Net Modeling
335
124 Summary
336
Supplementary Material
338
A12 State Class for LINSRCS
342
A13 Decision Class
343
A14 DPInstanceTableEntry Class
344
A16 BellmanNet Class
349
A2 DP2PN System Files
353
A3 Output from PN2XML
356
User Guide for DP2PN2Solver
359
B2 Obtaining DP2PN2Solver
360
B4 Running DP2PN2Solver
361
B42 The PN2Solver Module Preparations
363
B5 Creation of the gDPS Source File
365
B6 Debugging gDPS Code
366
B62 Common Mistakes Space Before Minus
367
B7 Error Messages of DP2PN2Solver
368
References
371
Index
375
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information