This page contains an applet that demonstrates the use of a general engine that can be used for fast generation of Dynamic Programming (DP) applications. The engine performs the backward procedure of DP with discrete states and discrete decisions when all is deterministic (if this sounds alien to you, no problem, just use the applet).
There is a certain number of planning periods (typically months or weeks) for which we know the required work force - numbers of workers. Initial number available is also known. Requirements must be satisfied, but it is possible to keep more in which case we pay a known excess per worker. If a worker is fired, she/he is paid a known severance. To hire workers we pay a known fixed amount that can be zero or possibly even negative plus a known fee per hired worker. All these figures are generally different in each period. We want to find the numbers of workers kept at all periods that would minimize the total cost. Wages of required work force and severance paid at the end of the project can be ignored in the decision making because they are constant. In the last period we obviously keep only the required work force.
First of all your browser must be able to run Java applets. If the box underneath is filled in, it is. There are two text areas. The first contains the problem data in table form, the second contains the results. Note that there is a default instance of the problem. Press the button Solve and you are supposed to obtain the result similar to the following one:
DP Solver v1 start: Wed Nov 30 14:45:02 CET 2005 Total time taken : 0 ms Number of stages : 5 Initial status : 0 Optimal objective : 33.0 Optimal plans : 1 5 8 8 6 6
Compare the optimal plan with the required work force and note that in two periods it is cheaper to keep an extra worker even if there is no severance. The button Generate Default Data copies the entered costs into all periods, the demand is generated randomly in the given range with equal probabilities. Press the button Edit to start the editing session in a window similar to the following one:
Use the buttons Move to Next and Previous to display data from the next/previous table entry. The button Copy to Next copies data from the current to the next table entry. Enter the period number and press the button Show Period to move fast in the table. Press Update to change the table entry according to the data entered in the text fields. All changes are shown in the data text area, all validation is performed and reported in self-explaining way.
You may skip this section if you are not interested in DP and Java. 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 given by the particular application, here the work force problem, 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 this application together about 50 lines of code. As an example here is the method that computes the return where t is the stage number, yt is the status (number of workers from the previous period) and xt is the decision (number of workers kept at this period).
// freturn(t,yt,xt) returns the cost (return) of decision xt at (t,yt)
public static double freturn(int t,int yt,int xt) {
double rt = 0.0;
if (xt > yt) {
rt = fixedCost[t] + (xt-yt)*unitCost[t]; // hiring cost
}
else if (xt < yt) {
rt = (yt-xt)*severance[t]; // firing cost
}
if (xt > demand[t]) {
rt = rt + (xt-demand[t])*excess[t]; // excess kept cost
}
return rt;
}
Data that define the particular instance of the problem are stored in variables of the class Application. The solver writes these data before calling the engine. The following is the method called after pressing the button Solve where result is the text area in the applet window and solverResult is the object to store the result (common to all applications). Names of variables are self-explaining.
void callSolver() { // Prepare data and call solver
Application.T = T;
Application.demand = demand;
Application.initial = initial;
Application.fixedCost = fixedCost;
Application.unitCost = unitCost;
Application.excess = excess;
Application.severance = severance;
dpEngine1 engine = new dpEngine1();
solverResult = engine.solve();
result.setText(solverResult.toString());
}
An engine version in Matlab is also available. The purpose of the engine is to support fast, relatively easy implementation of DP solutions manageable by students who are not experienced programmers.