Dynamic programming. A computational tool. (Q852477): Difference between revisions

The book is devoted to dynamic programming, emphasizing the design and use of computational tools. It discusses numerous examples of optimization problems and explains how to solve them using Bellman's Principle of Optimality. At the same time the book provides a software tool that is used for numerically solving the discussed problems. The first chapter offers an introduction to the basic principles of dynamic programming and illustrates the computational solution for specific problems. In the second chapter the following optimization problems are discussed from the point of view of dynamic programming: Optimal Allotment Problem, All-Pairs Shortest Paths Problem, Optimal Alphabetic Radix-Code Tree Problem, Assembly Line Balancing, Optimal Assignment Problem, Optimal Binary Search Tree Problem, Optimal Covering Problem, Deadline Scheduling Problem, Discounted Profits Problem, Edit Distance Problem, Fibonacci Recurrence Relation, Flow Shop Problem, Tower of Hanoi Problem, Integer Linear Programming, Integer Knapsack, Interval Scheduling Problem, Inventory Problem, Optimal Investment Problem, Winning in Las Vegas Problem, Longest Common Subsequence, Optimal Linear Search Problem, Lot Size Problem, Longest Simple Path Problem, Matrix Chain Multiplication Problem, Minimum Maximum Problem, Minimum Weight Spanning Tree Problem, The Game of NIM, Optimal Distribution Problem, Optimal Permutation Problem, Jug-Pouring Problem, Optimal Production Problem, Reject Allowances Problem, Reliability Design Problem, Replacement Problem, Stagecoach Problem, Seek Disk Scheduling Problem, Segmented Curve Fitting Problem, Program Segmentation Problem, Optimal Selection Problem, Shortest Path Problem'', Process Scheduling Problem, Transportation Problem, Traveling Salesman Problem. Chapter 3 describes a text-based specification language for dynamic programming problems. In Chapter 4, the authors present a set of computer programs for solving the problems given in Chapter 2. Chapter 5 discusses fundamental Petri net concepts and introduces Bellman nets as a very specialized class of Petri nets that can be associated with dynamic programming. Chapter 6 represents the problems from Chapter 2 as Bellman nets. Chapter 7 gives an overview of a software tool that enables to obtain numerical solutions of dynamic programming problems. Appendix B gives the instructions of downloading and using the developed software. Chapter 8 describes the design, implementation, and test of the compiler's modules. Chapter 9 describes software components that produce a solver code. Computational results are presented in Chapters 10, 11. Appendix A provides program listings.