“Dynamic Programming = Recursive Formulation & Non-Recursive Implementation”

On-Line Solvers

Work Force Problem Solver finds all optimal work force plans over a given number of periods and known deterministic demand that has to be satisfied. Costs involve hiring new workers, severance and excess. See the solver for the detailed problem specification.

Inventory Problem Solver finds all optimal periodic review inventory plans over a given number of periods and known deterministic demand. Costs involve fixed setup, unit cost, holding and stockout. See the solver for the detailed problem specification.

DP Engine - Java Version

The engine contains the general algorithm common to all applications. It solves the optimization problem by the backward procedure and retrieves all optimal plans. The results are supplied by the result object that contains the status of the first stage, the optimal objective value, and all optimal plans in a 2-dimensional array. Features specific for the particular application are included as methods of the class Application. The engine requires methods that return the following:

• Set of states for a given stage

• Set of decisions for a given stage-state pair

• Transition - the status of the next stage for a given stage-state pair and a given decision

• The return value for a given stage-state pair and a given decision

• The result of combining a given return and an optimal objective of the next stage (here and in most cases just their sum)

• The objective associated with the transition generated by the last stage that is needed to solve the last stage. For the work force problem this value is 0.

Compared with the engine the methods are very simple. For example the work force problem application requires about 50 lines of code to program all methods.

Data that define the particular instance of the problem are stored in variables of the class Application. A particular solver applet writes these data before calling the engine.

Downloads

Applets are not very useful for practical use of the Dynamic Programming solvers. As disk is not accessible the problem data cannot be saved and loaded. In some browsers and some settings it is even impossible to copy the data and the results to the clipboard. That's why next to applets, applications (in Java sense) have also been written and made freely available. Please e-mail me first something about yourself and about your use of Dynamic Programming. Then I shall send you the downloading details.

Back to Top

Towers of Hanoi

Learn how Dynamic Programming can be used to analyze the famous game called Tower(s) of Hanoi. Moshe Sniedovich used Dynamic Programming to find the length of the shortest and the longest solutions. Here we find the total number of different solutions with surprising results.

Back to Top

The Author

In case of any problems do not hesitate to contact me:

Web: http://staff.um.edu.mt/jskl1/

Back to Top

This article is translated to Azerbaijanian language by Amir Abbasov.

This article is translated to Croatian language by Milica Novak.