Eight step procedures

Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany
Steward: Fengqi You

Introduction

The eight-step procedure is an approach in dynamic programming used to determine optimal solutions in mathematical optimization. Dynamic programming is used for problems requiring maximization or minimization of the objective function and can be solved by enumerating all the different possible solutions and finding the best one.

In the eight-step procedure, a problem can be broken down into subproblems to solve. Using the solutions from the subproblems in a recursive manner, the solution can be determined after all the solutions of the subproblems are calculated to find the optimal solution. Such a standard framework is used so that dynamic programming store the values of the subproblems to avoid recomputing, and thus, reduce time to solve the problem.

Theory, Methodology, and/or Algorithmic Discussion

Methodology

To solve a problem using the 8-step procedure, one must use the following steps:

Step 1: Specify the stages of the problem
The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable $n$.

Step 2: Specify the states for each stage
The states of a problem are defined as the knowledge necessary to make a decision, or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} . We set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} equal to the maximum value of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} .

Step 3: Specify the allowable actions for each state in each stage
This can be defined as:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \} }

Step 4: Describe the optimization function using an English-language description.
In this sentence, we describe the optimization function for each state, or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , and each stage, or Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . This can also be called Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n}(s)}

Step 5: Define the boundary conditions
This helps create a starting point to finding a solution to the problem. First, we set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n+1}(s) = 0} for all values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} . Here, we can note that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s=0,...,C }

Step 6: Define the recurrence relation
During this step, we make an allowable decision involving Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle j} items for the remaining capacity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} for items Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} . We can write this statement as:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n}(s)= \overset{max}{j=0,1,...,min\left \{ a[n],\left \lfloor \frac{s}{w[n]} \right \rfloor \right \}} \left \{ b[n,j]+ f^{*}_{n+1}(s-j*w[n]) \right \} }

Step 7: Compute the optimal value from the bottom-up
In this step, a table is made containing all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n}(s)} , and optimal values for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} variables. This step can be done manually or by using programming.

Step 8: Arrive at the optimal solution
Once the value for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n}(s)} is computed, we would look at the optimal decision that corresponds to the table entry for that value. We start with the optimal value for our first Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , calculate our remaining space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s} , and use that value to arrive at an optimal value for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

Numerical Example

Weight capacity of C=5 and N=2

Item types are stages: n=1,2

Remaining capacity s= 1,2,3,4,5

Boundary Conditions:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{n+1}(s) = 0} , s=0,1,2,3,4,5 C=5

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \} } = {0,1,2}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} } =

Unused Capacity s	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{1}(s)}	Type 1 opt Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U^{*}_{1}(s)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{2}(s)}	Type 2 opt Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U^{*}_{2}(s)}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f^{*}_{3}(s)}
5	9	0	9	2	0
4	9	0	9	2	0
3	4	0	4	1	0
2	4	0	4	1	0
1	0	0	0	0	0
0	0	0	0	0	0

Applications

The following are some applications where dynamic programming is used. The criteria for applying dynamic programming to an optimization problem are if the objective function involves maximization, minimization, or counting and if the problem is determined by finding all the solutions to find the optimal solution.

Shortest/ Longest Path Problem

In the shortest path problem, the path with the least amount of cost or value must be determined in a problem with multiple nodes in between the beginning node s to the final node e. Travelling from one node to another incurs a value or cost c(p, q), and the objective is to reach t with the smallest cost possible. The eight-step procedure can be used to determine the possible solutions which the optimal solution can be determined from.

Likewise, but in a maximization function, the longest path can be determined in a problem by determining the solution with the highest cost involved to travel from node s to node e.

Knapsack problem

The knapsack problem is an example of determining the distribution of effort or when there are limited resources to be shared with competing entities and the goal is to maximize the benefit of the distribution. Oftentimes dynamic programming is used when the increase in benefit in regard to increasing the quantity of resources is not linearly proportional.

Inventory planning problem