The objective function and constraints comprise the mathematical programming statement of the allocation of scarce resources problem. Since the decisions are required to assume integer values, neither linear nor nonlinear programming is an appropriate solution technique. An enumerative solution procedure such as integer programming or dynamic programming must be used. Dynamic programming is very general with regard to the functional form the objective terms and constraint terms. Linearity is not required. Although most problems that can be solved by dynamic programming can also be solved with integer programming, the integer programming model will usually be quite large and complex if nonlinear functions are part of the situation.

Dynamic Programming Model

To formulate this problem for dynamic programming, a solution must be described as a sequence of states and decisions. The sequence of decisions is easily obtained by arbitrarily ordering the investment opportunities. Thus the first decision is the level of investment in opportunity 1, the second decision is the level for opportunity 2 and so on. To complete the model we must define each of the model components listed below. Many variations in the problem statement can be accommodated by minor variations in the model.

In the following we describe the mathematical formulation of the model together with the Excel implementation. The add-in constructs a number of named ranges on a worksheet defining the model. All the ranges are prefixed with the worksheet name, DP1_, for this example. This allows a workbook to hold a number of dynamic programming models, each with a unique name. In our descriptions we will use the prefix DP1_ to explain the features of the model, however, that prefix will differ for problems with other names.

Options

The program is governed by a number of parameters that identify the type, dimensions and optimization criterion of the model, control the solution strategy, and specify the material that is displayed during and after a run. The program constructs two named ranges, DP1_Param and DP1_Strategy, to hold this information. They are indicated in yellow in the figure. The first four entries in the Params range are set during the problem definition. The other entries in the two arrays can be changed by choosing the Options menu item from the Teach menu.

States

The dynamic process starts in an initial state. After each decision the process moves to a different state. Finally the process is finished when a final state is reached. The state vector identifies the states of the process.

Mathematical Description

Excel Definition

The Excel model uses the worksheet region from row 9 to row 19 to hold state information. The definitions of the states are in rows 16 through 18. The number of rows will expand to accept the number of state variables. The array named DP1_StateVector is used during the solution process to hold values of the state variables.

Decisions

Mathematical Description

The vector of feasible decisions is defined by lower and upper bounds on the decision variables. For the knapsack problem, the decision is how many of an item to bring, so the vector has only one component.

Excel Definition

The decision vector and its bounds start at row 20 of the worksheet. In row 23, we see the named range DP1_StateDecVector. During computation this range will be set equal to the values in the DP1_StateVector range defined above. We do this because the feasibility conditions for a decision might depend on the state definition. Formulas implementing such a relationship can point to cells in the DP1_StateDecVector range. Similar arrangements will be noted for other components of the formulation.

The decision value is in row 25. If the decision were a vector with more than one element, cells are provided for each component. Below the decision value are cells for the minimum, maximum and step size for each decision variable (rows 27 through 29). During the solution process the decision is taken through each possibility for every state. The limits allow the values 0, 1, and 2 for the decision variable.

Excel Formulas

Row 26 holds equations that determine the feasibility of the decision. Cell C26 contains a Boolean formula that returns True if the first decision variable is between its bounds. Cell D26 is true if all the decision variables are feasible. The formulas that accomplish these computations are shown in the Excel Formula view below. The formulas in both C26 and D26 use the AND Boolean function. In the latter case the statement AND(DP1_DecLogic) is TRUE if all the cells in the range DP1_DecLogic are TRUE.

We see in cells C23, C24, C25 the formulas that make these cells equal to the cells in the DP1_StateVector range. These formulas are added by the solution procedure, and need not be a concern of the user.

Formulas in yellow cells are added by the computer when necessary for the solution process. The formula in C25 accomplishes the process of enumerating the set of decisions. The program refers to DP1_DecInd, a number in cell B31. As that number ranges from 0 to 3, the decision value in C25 ranges from 0 to 3. This isn't very exciting for this small case, but the procedure is very powerful for enumerating all feasible decisions for a decision vector with more than one variable. The contents of cells C30, C31 and B31 are also used by the program.

The important formulas for the user trying to implement a different problem are those in C26 and D26. These can be any Boolean functions or combinations of functions available to Excel. Very complex feasibility conditions can be constructed.

Forward Transition Equations

The forward transition equations compute the state that is reached by taking decision d while in state s. For the knapsack problem the decision moves to the next opportunity and increases the amounts used of each resource by an amount that depends on the decision.

Mathematical Description

Excel Definition

We see below the Excel worksheet area implementing the forward transition functions. The ranges DP1_StateForVector and DP1_DecForVector copy the state and decision information from the ranges in the upper part of the worksheet that hold the state and decision vectors.

The range circled in red holds the next state. Although in this case the program has filled this range with formulas appropriate to the knapsack problem, the user can provide his or her own formulas to implement any desired transition functions.

Excel Formulas

The specific formulas for the knapsack problem are in row 43 in the figure below. The formula in C43 simply adds 1 to the contents of C39. C39 holds the index of the opportunity, so cell C43 computes the index of the next opportunity.

Cells D43 and E43 compute the amount of resources for the next state. The references to DP1_Res refers to the range holding the resource usage amounts. The INDEX function is helpful in that it chooses a number from a range for a given row and column. Note that the unit resource is multiplied by C40, and that cell holds the decision value.

Again, here is the place where the user will put new formulas to describe the transition equations for different problems.

Backward Transition Equations

The backward transition equations are used to find the previous state in a sequence of decisions. In this implementation of the DP add-in we use these equations only for the recovery of a solution after the Reaching procedure. If the Reaching procedure is not used these functions can be left empty.

Mathematical Description

Excel Definition

The region implementing the backward transition functions looks much like that of the forward transition functions. In fact in many cases these functions are the inverse of each others. If they are not procedure the Reaching procedure will not work.

Excel Formulas

For the example the backward transition functions are implemented in row 53. The previous state variable sp1, cell C53, is simply one less than the state s1. The other functions reduce the amounts of resources used and depend on the decision vector.

Decision Objective and Recursive Equations

Mathematical Description

These functions comprise the objective function of dynamic programming. The contribution of a decision d taken while in state s is computed by the decision objective. This can be a function of s, d, and s' (the next state reached).

The backward recursive equation shows how the contribution of a decision is combined with the results of the optimal decisions starting from state s'. This is a recursive equation because the value of f(s) depends on the value of f(s').

The forward recursive equation shows how the contribution of a decision is combined with the results of the optimal decisions made up to the previous state. This equation is only used during the solution phase of the Reaching procedure. If the Reaching procedure is not used, this function need not be defined.

Excel Definition

The three quantities to be computed are scalar quantities and are each computed in a single cell of the worksheet. The decision objective in cell F64, the backward recursive equation in cell C64 and the forward recursive equation in cell I67.

Excel Formulas

The decision objective for the example is in cell F64. The unit benefits for the items are stored in DP1_Ben, and the function multiplies the decision value times the unit benefit.

The recursive equations are very simple in this case. The Backward Recursive equation in C64 adds DP1_DecValue (cell F64) to DP1_NextStateValue (cell I64). During the solution process the computer puts appropriate values into DP1_NextStateValue to solve the recursive equation.

In a similar manner the Forward Recursive Equation depends on the cell DP1_BackStateValue. The computer controls the content of this cell.

Initial States

The sequential decision problem can begin at one or more initial states. When more than one is specified, the program selects the one with the best objective.

Mathematical Description

For the knapsack, we consider only one starting state (1, 0, 0). That is, we start with opportunity 1 and no resources used.

Excel Definition

The structure on the worksheet allows a number of feasible initial states to be defined. In the present case, because the minimum and maximum limits are equal, only one state, (1,0,0), is an initial state.

Excel Formulas

The important formulas in this case are those that determine the Boolean value in cell F75. If this cell is True, the state in row 74 is an initial state, while if the cell is False the state is not an initial state. For this example, the state is judged initial if its components lie within the bounds.

Final States

The decision process ends in a final state. Again, we use sets to identify final states. For knapsack problem, a final state has the first state variable equal to one greater than the number of items.

Mathematical Description

Excel Definition

The structure for Final states looks very much like that for initial states. The state of cell F87 determines if a given state (in row 86) is a final state.

Excel Formulas

State Feasibility

Dynamic programming solution algorithms need only consider states that will lead to feasible final states. Infeasible states are those that do not. The definition of feasible states is important because the number of computations in a DP solution is important to the number of states considered. If some states can be eliminated because they are infeasible, computational effort will be reduced.

Mathematical Description

Although in general quite complex conditions can be used to define feasible states, in the example we use simple bounds. The validity of these bounds depend on the fact that all the resource usage coefficients are nonnegative.

Excel Definition

The feasibility conditions start in row 94. They are very similar to the structures for initial and final states, except the minimum and maximum limits are different. In addition to the primarily function of identifying feasible states in the solution process, the structure below is used by the exhaustive enumeration procedure for state generation. When the DP1_FeasStateInd is assigned all the integer values in the range 0 to 5225, all the states will have been generated. Formulas placed in row 98 determine the state values from the enumeration index.

Excel Formulas

State and Decision Variable Names

Excel Definition

This area on the worksheet is not necessary for the DP solution process, but it is very useful for presenting the results of the DP solution in terms of actions. The cell labeled DP1_Action is to hold a phrase that explains the current state and decision. This cell is a concatenation of the red bordered cells above. The latter cells have formulas that generate string expressions.

Excel Formulas