Eight step procedures: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
 
(23 intermediate revisions by 3 users not shown)
Line 1: Line 1:
Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany </br>
Author: Satyasri Ventrapragada (sv353), John-Anthony Gonzales (jg2533), Salina Tekele (st2257)
Steward: Fengqi You
 
Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu


=Introduction=
=Introduction=
The eight-step procedures are a simplified, multi-stage approach for determining optimal solutions in mathematical optimization. Dynamic programming, developed by Richard Bellman in the 1950s<ref>Bellman, Richard. “The Theory of Dynamic Programming.” Bulletin of American Mathematical Society, vol. 60, 1954, pp 503–515, https://www.ams.org/journals/bull/1954-60-06/S0002-9904-1954-09848-8/S0002-9904-1954-09848-8.pdf. 18 Nov 2020.</ref>, is used to solve for the maximization or minimization of the objective function by transforming the problem into smaller steps and enumerating all the different possible solutions and finding the optimal solution.
In an attempt to innovate new ways for solving the world’s issues, scientists and mathematicians came together years ago to push forward with new ideas. After some time and iteration, dynamic programming (DP) was born –– a complex mathematical optimization method that aims to solve a wide range of problems. Dynamic programming is best used when the problem can be divided into subproblems that are solved until a globally optimal solution is reached. This comes with a small caveat from Sean Eddy claiming, dynamic programming is “guaranteed to give you a mathematically optimal (highest scoring) solution,” but it matters most how the data is scored<ref>Eddy, S. (2004, July). What is dynamic programming?. Nature Biotechnology. <nowiki>https://doi.org/10.1038/nbt0704-909</nowiki>. </ref>. Considering all of this, it is important to highlight that Richard Bellman pushed hard for advancements in the early stages and can be credited with the development of dynamic programming.
 
As mentioned, Richard Bellman – a well renowned Stanford professor that was contracting for a non-profit research institution at the time – founded monumental principles on dynamic programming beginning in the 1950s when he started publishing formal work on the topic. In his first publishing, Bellman was forced to strategically name the new computational method due to political condemnation. To avoid using words like “research” and “mathematical,” Bellman sought to emphasize the time-varying and incremental aspects of using the algorithm; therefore, he eventually chose “dynamic programming” to effectively summarize the intent of the steps he was creating <ref>Dreyfus, S. (2002, February). Richard Bellman on the Birth of Dynamic Programming, pp. 48-51.</ref>.
 
After learning more about the principles and mechanics of dynamic programming, it is intended to aid in decision-making challenges that have the specific circumstantial opportunities for its use. In particular, anything similar to the applications that are discussed later are concrete examples of where and how dynamic programming can be implemented. As these examples will show, the main objectives are to show the ease of dynamic programming in practice, exactly how this takes place, and what some of the drawbacks and limitations might be. Having this tool widely available, easily deployable, and readily adaptable for any fitting situation has changed the way that optimization can occur for the better.
 
=Algorithm Discussion=
 
When tackling a dynamic programming problem, there are generally a number of key steps to follow. The first and most crucial step is determining whether dynamic programming is the right approach. A key indicator of this is whether the problem can be broken down into smaller, overlapping subproblems. Problems that involve minimizing or maximizing a quantity, or those that require counting possible arrangements, are often strong candidates for dynamic programming solutions.<ref name=":0">Benjaminson, E. (2023, January). A Framework for Solving Dynamic Programming Problems. Github.io. sassafras13.github.io/SolvingDPProblems/. </ref> For example, in the Fibonacci sequence:
 
F(n)=F(n−1)+F(n−2),F(0)=0,F(1)=1
 
Dynamic programming reduces the time complexity by reusing previously computed solutions.
 
Next, identify the key variables that change between subproblems, as they are crucial for breaking the problem down. listing a few subproblems and comparing their parameters helps which variables vary.
 
The third step is to define the recurrence relation, which expresses how the solution to a larger subproblem can be constructed from solutions to smaller subproblems. The recurrence relation serves as the core of the dynamic programming approach, describing how to combine the results of smaller subproblems to build up the final solution.<ref>Luu, H. (2020, November). Dissecting Dynamic Programming – Top down & Bottom Up. Medium. hien-luu.medium.com/dissecting-dynamic-programming-top-down-bottom-up-3d3a1d62fbd7. </ref> For example, in the Fibonacci number calculation the recurrence relation is given by
 
F(n)=F(n−1)+F(n−2)
 
Once this is done, the next step is to identify the base cases which represent the simplest, smallest possible inputs for which the solution is trivial or already known.<ref name=":0" />  The base cases for the Fibonacci sequence are defined as:


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 best solution, which demonstrates the principle of optimality: Any optimal policy has the property that, whatever the current state and current decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the current decision.<ref>Bradley, Stephen P. Applied Mathematical Programming. Addison-Wesley. 1 February 1977. 320-342. 18 Nov 2020</ref> 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.<sup>3</sup>
F(0)=0,F(1)=1


=Theory, Methodology, and/or Algorithmic Discussion=
Base cases are essential because they serve as the foundation for building up solutions to more complex subproblems. They also act as stopping conditions for the recursion or termination conditions for the iterative approach, ensuring that the algorithm does not run indefinitely.


===Methodology===
The following decision is whether to use a recursive (top-down, memoization) or iterative (bottom-up, tabulation) approach. The top-down approach uses recursion and caches results to avoid redundant calculations, but can lead to stack overflow with deep recursions. The bottom-up approach solves subproblems iteratively, saving space but being harder to understand initially. Both achieve the same goal.  
To solve a problem using the 8-step procedure, one must use the following steps:<ref>You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.</ref><br />
<br />


'''Step 1: Specify the stages of the problem''' <br />
Next, implement memoization (top-down) or tabulation (bottom-up). Memoization stores results of expensive function calls in a table or dictionary, returning the stored result for repeated subproblems to avoid redundant calculations. <ref name=":0" /> Letting f(x) represent the solution to a subproblem, the first time f(x) is computed the results are stored in a table or cache T. For subsequent calls with the same input, the result is retrieved from the cache, T(x).  
The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable <math>n</math>. <br />
<br />


'''Step 2: Specify the states for each stage''' <br />
f(x) = { compute and store result in T(x)  if f(x) is not already cached     
The states of a problem are defined as the knowledge necessary to make a decision. This is often denoted by <math>s</math>, with <math>C</math> being set equal to the maximum value of <math>s</math>. <br />
<br />


'''Step 3: Specify the allowable actions for each state in each stage''' <br />
f(x) = { T(x)  if f(x) is cached }
This stage varies greatly based on the problem presented. <br />
<br />


'''Step 4: Describe the optimization function using an English-language description.''' <br />
This approach avoids redundant calculations, improving performance, especially for problems with overlapping subproblems.  
<br />


'''Step 5: Define the boundary conditions''' <br />
Finally, the time complexity depends on the number of unique subproblems ''N'' and the time to solve each, T(x). The number of subproblems is determined by the distinct states defined by the changing parameters, and the complexity per subproblem depends on the work required to compute each solution.  
This helps create a starting point to finding a solution to the problem. <br />
<br />


'''Step 6: Define the recurrence relation''' <br />
Thus the total time complexity is:
This is often denoted with a function. <br />
<br />


'''Step 7: Compute the optimal value from the bottom-up''' <br />
T<sub>total</sub> = N x T(x)
This step can be done manually or by using programming. <br />
<br />


'''Step 8: Arrive at the optimal solution''' <br />
Dynamic programming often reduces time complexity from exponential to polynomial time, making otherwise intractable problems solvable.  
This is the final step. <br />


=Numerical Example=
=Numerical Examples=
Weight capacity of C=5 and N=2


Item types are stages: n=1,2
=== '''''Example 1: Knapsack Problem''''' ===
''The Smiths are trying to replicate a delicious Christmas fruitcake recipe, and the recipe calls for berries with a total of up to 11 lbs of berries packed into the fruitcake. The Smiths purchased 4 boxes of strawberries and 4 boxes of blueberries during their Christmas grocery shopping trip last weekend but are unsure of how many boxes of strawberries and blueberries to include in their fruitcake. Each box of strawberries weighs 2 lbs and each box of blueberries weighs 3 lbs. To make the choice easier, they spent all day researching how different amounts of strawberries and blueberries impact the taste of the fruitcake and made a benefit table listing the value each box of berries adds to the overall taste of the fruitcake. The benefit table is shown below in Table 1. Please use Dynamic Programming to help the Smiths choose the optimal number of boxes of strawberries and blueberries to include in their delicious Christmas fruitcake this year!''


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


Boundary Conditions:
Table 1. Availability and weights of the berries.
{| class="wikitable"
|'''Type of berry'''
|'''Availability (number of boxes)'''
|'''Weight per box (lb)'''
|-
|Strawberries
|4
|2
|-
|Blueberries
|4
|3
|}


<math>f^{*}_{n+1}(s) = 0</math>,    ''s=0,1,2,3,4,5''     ''C=5''
 
Table 2. Benefit table for number of boxes of berries.
{| class="wikitable"
|'''Number of boxes of berries in fruitcake'''
|0
|1
|2
|3
|4
|-
|'''Strawberries'''
|0
|2
|3
|5
|7
|-
|'''Blueberries'''
|0
|1
|2
|4
|5
|}
 
 
To solve the Smiths’ fruitcake problem, we will be using dynamic programming through the following 8 steps:
 
 
'''Step 1: What are the stages?'''
 
The different types of items are the stages. For this problem, there are 2 stages: a box of strawberries or a box of blueberries, and the decision made in that stage is to specify the number of boxes of each berry to include in the fruitcake.
 
 
'''Step 2: What are the states?'''
 
The states correspond to the remaining number of boxes of berries we can include in the fruitcake. For example, if we had already made a decision to include 1 box of strawberries and 1 box of blueberries in the previous states, the current state would be 1 since the recipe requires only 3 total boxes of berries.
 
 
'''Step 3: What actions may be taken at each state in each stage?'''
 
If we are in stage n with availability a[n] and remaining capacity s, we can pack j items of type n into the fruitcake:


<math>  
<math>  
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
j = 0, 1, \dots, \min\{a[n], \lfloor sw[n] \rfloor\}
</math>= '''{0,1,2}'''
</math>
 
 
'''Step 4: What is the English-language description of the optimization function for each state s in stage n?'''
 
<math>
f_n^*(s)
</math> is the value of the maximum benefit possible with items of type n (or greater) while fitting into the remaining capacity s.                               
 
'''Step 5: What are the boundary conditions?''' 
 
The benefit is 0 when there are no more types of berries to use even though there is remaining capacity.
 
<math>f^{*}_{n+1}(s) = 0</math>, where N is the number of unique berries (N = 2) in this problem. Therefore, <math>f^{*}_{3}(s) = 0</math> since there is no third type of berry.
 
 
'''Step 6: What is the recurrence relation?'''
 
We will construct a benefit function corresponding to each remaining capacity s for each of the items n, . . . , N to use j number of boxes of type n berries in the fruitcake.
 
<math> f_n^*(s) = \max_{j = 0, 1, \dots, \min \{a[n], \lfloor sw[n] \rfloor \}} \{b[n,j] + f_{n+1}^*(s - jw[n])\}
</math>
 
 
'''Step 7: Compute optimal values in a bottom up fashion.'''
 
Let <math>U_n^*(s)
</math> be the optimal number of boxes of berry type n where n=1 corresponds to strawberries and n=2 corresponds to blueberries.


<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
{| class="wikitable"
|+
|'''Unused capacity s'''
!Unused Capacity s
 
!<math>f^{*}_{1}(s)</math>
'''(lbs of berries left to put into fruitcake)'''
!Type 1 opt <math>U^{*}_{1}(s)</math>
|'''<math>f_1^*(s)
!<math>f^{*}_{2}(s)</math>
</math>'''
!Type 2 opt <math>U^{*}_{2}(s)</math>
 
!<math>f^{*}_{3}(s)</math>
'''(maximum benefit function for strawberries)'''
|'''Type 1 opt'''
 
'''<math>U_1^*(s)
</math>'''
 
'''(optimal number of boxes of strawberries)'''
|'''<math>f_2^*(s)
</math>'''
 
'''(maximum benefit function for blueberries)'''
|'''Type 2 opt'''
 
'''<math>U_2^*(s)
</math>'''
 
'''(optimal number of boxes of blueberries)'''
|'''<math>f_3^*(s)
</math>'''
|-
|11
|
|
|
|
|0
|-
|10
|
|
|
|
|0
|-
|9
|
|
|
|
|0
|-
|8
|
|
|
|
|0
|-
|7
|
|
|
|
|0
|-
|6
|
|
|
|
|0
|-
|-
|5
|5
|
|
|
|
|0
|-
|4
|
|
|
|
|0
|-
|3
|
|
|
|
|0
|-
|2
|
|
|
|
|0
|-
|1
|
|
|
|
|0
|-
|0
|
|
|
|
|0
|}
Let’s start with our first state, s=11, where there are 11 lbs of berries left to add to the fruitcake.
<math>U_1(11) = \{0, 1, \dots, \min \{a[2], \left\lfloor \frac{11}{w[2]} \right\rfloor\}\}
</math>
<math>U_2(11) = \{0, 1, 2, 3\} \quad \text{since } a[2] = 4 \text{ and } \left\lfloor \frac{11}{3} \right\rfloor = 3.
</math>
Recall from Step 6:
<math> f_n^*(s) = \max_{j = 0, 1, \dots, \min \{a[n], \lfloor s w[n] \rfloor\}} \left\{ b[n,j] + f_{n+1}^*(s - j w[n]) \right\}
</math>
<math>f_2^*(s) = \max_{j \in U_2(11)} \left\{ b[2,j] + f_3^*(s - j w[2]) \right\}
</math>
Recall from Step 5 that <math>
f_3^*(s)
</math> is simply for a boundary condition and <math>
f_3^*(s)
</math> = 0.
Therefore, <math> f_2^*(s) = \max_{j \in U_2(11)} \left\{ b[2,j] \right\}
</math>
Recall from Table 1 that the maximum benefit occurs when j = 3 where <math>f_2^*(s)</math> = 6. We can now fill in the first 3 rows of our table for n = 2 (blueberries) since the equation for U,<math> U_2(s) = \{0, 1, \dots, \min \{a[2], \lfloor s w[2] \rfloor\}\}
</math>,
will not change for when s = 11, 10, and 9 and will remain as <math> U_2(s) = \{0, 1, 2, 3\}
</math>. Similarly, when s = 8, 7, or 6, <math> U_2(s) = \{0, 1, 2\}
</math>, when s = 5, 4, or 3,  <math> U_2(s) = \{0, 1\}
</math>, and when s = 2, 1, or 0,  <math> U_2(s) = \{0\}
</math>. Since a greater number of boxes of blueberries results in a greater benefit function value as shown in Table 2, the j that will give us the most benefit for n = 2 would be the maximum value of the set <math> U_2(s)
</math> for a given state, s. The populated values for n = 2 can be seen below.
{| class="wikitable"
|'''Unused capacity s'''
'''(lbs of berries left to put into fruitcake)'''
|'''<math>f_1^*(s)
</math>'''
'''(maximum benefit function for strawberries)'''
|'''Type 1 opt'''
'''<math>U_1^*(s)
</math>'''
'''(optimal number of boxes of strawberries)'''
|'''<math>f_2^*(s)
</math>'''
'''(maximum benefit function for blueberries)'''
|'''Type 2 opt'''
'''<math>U_2^*(s)
</math>'''
'''(optimal number of boxes of blueberries)'''
|'''<math>f_3^*(s)
</math>'''
|-
|11
|
|
|4
|3
|0
|-
|10
|
|
|4
|3
|0
|-
|9
|9
|
|
|4
|3
|0
|-
|8
|
|
|2
|2
|0
|-
|7
|
|
|2
|2
|0
|-
|6
|
|
|2
|2
|0
|-
|5
|
|
|1
|1
|0
|-
|4
|
|
|1
|1
|0
|-
|3
|
|
|1
|1
|0
|0
|9
|-
|2
|2
|
|
|0
|0
|0
|0
|-
|-
|1
|
|
|0
|0
|0
|-
|0
|
|
|0
|0
|0
|}
What is the physical meaning of each row? For example, for the row when s = 7 lbs, 2 boxes of blueberries can be added into the fruitcake for maximum benefit ('''<math>f_2^*(s)
</math>''' = 5) since each box of blueberries weighs 3 lbs and the greater the number of boxes of blueberries, the more the benefit as seen in Table 2.
Now, we want to fill in the strawberries section of our table, or n=1. To do this, we repeat Step 7:
Let’s start with our first state, s=11, where there are 11 lbs of berries left to add to the fruitcake.
<math>U_1(11) = \{0, 1, \dots, \min \{a[1], \left\lfloor \frac{11}{w[1]} \right\rfloor\}\}
</math>
<math>U_1(11) = \{0, 1, 2, 3, 4\}
</math> since a[1] = 4 and <math>\left\lfloor \frac{11}{2} \right\rfloor
</math> = 5.
Recall from Step 6:
<math>f_n^*(s) = \max_{j = 0, 1, \dots, \min \{a[n], \lfloor s w[n] \rfloor\}} \left\{ b[n,j] + f_{n+1}^*(s - j w[n]) \right\}
</math>
<math>f_1^*(s) = \max_{j \in U_1(11)} \left\{ b[1,j] + f_2^*(s - j w[1]) \right\}
</math>
<math>f_1^*(s) = \max_{j \in U_1(11)} \left\{ b[1,j] + f_2^*(s - 2j) \right\}
</math>
Unlike before for n=1, the second term, <math>f_{n+1}^*(s - j w[n])
</math>, is not equal to 0. Therefore, we must calculate <math>f_1(s)
</math> for each j in <math>U_1(s)
</math> to find the optimal number of boxes of strawberries, <math>U_1^*(s)
</math>, that corresponds to the maximum benefit, <math>f_1^*(s)
</math>, for any given s. Let’s construct a table for s=11 just for clarity:
{| class="wikitable"
|j in <math>U_1(11)
</math>
|<math>f_1(11) = \left\{ b[1,j] + f_2^*(s - 2j) \right\}
</math>
|-
|0
|= 0 +<math>f_2^{*}(11)
</math> = 0 + 4 = 4
|-
|1
|= 2 + <math>f_2^{*}(9)
</math> = 2 + 4 = 6
|-
|2
|= 3 + <math>f_2^{*}(7)
</math> = 3 + 2 = 5
|-
|3
|= 5 + <math>f_2^{*}(5)
</math> = 5 + 1 = 6
|-
|'''4'''
|'''= 7 + <math>f_2^{*}(3)
</math> = 6 + 1 = 8'''
|}
As seen above, the maximum <math>f_1(11)
</math>, <math>f_1^*(11)
</math> , occurs when <math>U_1^*(11)
</math> = 4 . This means that the maximum benefit with respect to n=1 occurs when 4 boxes of strawberries are packed into the fruitcake when s=11. We will repeat this process for the rest of the states, s = 10, 9, …, 0, and the populated table is shown below.
{| class="wikitable"
|'''Unused capacity s'''
'''(lbs of berries left to put into fruitcake)'''
|'''<math>f_1^*(s)
</math>'''
'''(maximum benefit function for strawberries)'''
|'''Type 1 opt'''
'''<math>U_1^*(s)
</math>'''
'''(optimal number of boxes of strawberries)'''
|'''<math>f_2^*(s)
</math>'''
'''(maximum benefit function for blueberries)'''
|'''Type 2 opt'''
'''<math>U_2^*(s)
</math>'''
'''(optimal number of boxes of blueberries)'''
|'''<math>f_3^*(s)
</math>'''
|-
|'''11'''
|'''8'''
|'''4'''
|5
|3
|0
|-
|10
|7
|4
|4
|5
|3
|0
|-
|9
|9
|7
|4
|5
|3
|0
|-
|8
|7
|4
|2
|2
|0
|-
|7
|5
|3
|2
|2
|0
|0
|9
|-
|6
|5
|3
|2
|2
|2
|0
|0
|-
|-
|5
|3
|3
|4
|2, 1
|1
|1
|0
|0
|-
|4
|4
|3
|2
|1
|1
|1
|0
|0
|-
|-
|'''3'''
|2
|2
|4
|1
|1
|'''1'''
|0
|0
|4
|-
|2
|2
|1
|1
|0
|0
|0
|0
|-
|-
Line 111: Line 630:
|}
|}


=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'''
'''Step 8: Find the optimal solution by looking at the table'''
 
The maximum benefit possible is 8, with 4 boxes of strawberries and 1 box of blueberries added to the fruitcake. Here are the steps after constructing the table to get to that final answer:
 
# Where does the maximum benefit occur? The maximum value for the benefit is 8, and this occurs at s = 11 where <math>f_1^*(11)
 
</math> = 8 .
# How many boxes of strawberries does <math>f_1^*(11)
 
</math> = 8 correspond to? <math>U_1^*(s)
</math> = 4 when <math>f_1^*(11)
 
</math> = 8 as seen in the table, so 4 boxes of strawberries.
# How many lbs of fruit remain to add into the fruitcake? The total capacity is 11 lbs, and 4 boxes of strawberries each weighing 2 lbs were already added, so <math>11 - (4 \times 2) = 3
</math>. 3 lbs of fruit remain to add into the fruitcake.
# What is the optimal number of boxes of blueberries that should be added according to the table? Find s = 3, and find <math>U_2^*(3)
</math>. <math>U_2^*(3)
</math> = 1, so 1 box of blueberries should be added.


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.<sup>5</sup>
'''Final Answer: The Smiths should add 4 boxes of strawberries and 1 box of blueberries to their fruitcake.'''


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''.
===  '''''Example 2: Layered Graphs''''' ===
''Find the shortest path in this layered graph using the concepts of dynamic programming.''
[[File:Layered Graph for dynamic programming.jpg|center|thumb|405x405px|Layered graph to find shortest path using dynamic programming.]]
We can partition the nodes into layers where the first layer is s, the second layer is A, B, and C, the third layer is D and E, the fourth layer is F and G, and the fifth layer is t. We will make a decision of the path to take at each layer, and each decision will correspond to a stage of the dynamic programming problem.
[[File:Layered graph with layers.jpg|center|thumb|401x401px|Layered graph with each stage, or layer.]]
To solve this shortest path problem, we will be using the previously explained 8 steps to solve the dynamic programming problem.


'''Knapsack Problem'''
# What are the stages?
#* The stages are the different layers. There are 5 stages.
# What are the states?
#* The states are nodes in each layer.
# What actions may be taken at each state in each stage?
#* At each state in each stage, we will have to make a decision for which edge to pick. For example, in stage 1 (blue) and state B, we can pick either the edge with distance 3 or the edge with distance 4 since both edges are leaving node B.
# What is the English-language description of the optimization function for each state s in stage n?
#* <math>f_i^*(r)


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. Dynamic programming is used when the increase in benefit in regard to increasing the quantity of resources is not linearly proportional. The volume may also be considered in addition to the weight of the resources. A volume constraint is added to the problem and represented in the state by stage ''n'' by an ordered pair (''s, v'') for remaining weight and volume. By considering ''d'' constraints, the number of states can grow exponentially with a ''d'' -dimensional state space even if the value of ''d'' is small. The problem becomes infeasible to solve and is referred to as the curse of dimensionality. However, the curse has faded due to advances in computational power.<sup>6</sup>
</math> is the minimum total cost to go from state r in stage i to reach node t, which is the final stage.
# What are the boundary conditions?
#* There is 0 cost for stage 4 since we have already reached the ending, node t.
# What is the recurrence relation?
#* <math> f_n^*(s) = \min_{edges\ from\ r\ to\ a\ state\ p\ in\ stage\ i+1} \{c[r,p] + f_{i+1}^*(p)\}
</math>
# Compute the optimal path based on the recurrence relation defined in Step 6 and the boundary condition defined in Step 5.
#* We will assign a number to each node, and this number will correspond to the <math>f_i^*(r)


'''Inventory Planning Problem'''
</math> for that node as defined above in Step 6. This will be the smallest cumulative sum possible between that node and the edge connecting that node to the next layer, or next stage. The <math>f_i^*(r)


In inventory management, dynamic programming is used to determine how to meet anticipated and unexpected demand in order to minimize overall costs. Tracking an inventory system involves establishing a set of policies that monitor and control the levels of inventory, determining when a stock must be replenished, and the quantity of parts to order. For example, a production schedule can be computationally solved by knowing the demand, unit production costs, and inventory supply limits in order to keep the production costs below a certain rate.<sup>7</sup>
</math> for each state in each stage are shown in red below, and the optimal path is indicated by the red arrows.[[File:Layered graph with shortest path.jpg|center|thumb|422x422px|Layered graph with <math>f_i^*(r) </math> for each node and shortest path in red.]]
# Find the optimal solution by looking up the table.
#* The length of the shortest path: f0*(s)=8. The shortest path can be found by following the red arrows moving forward. '''s → B → D → G → t.'''


=Conclusion=
=Applications=
The eight-step procedure is an approach used in dynamic programming to transform a problem into simpler problems to yield an optimal solution. The recursive nature of the procedure allows for the optimization problems to be solved using computational models that reduce time and effort and can be used in many applications across many industries.
As suggested in previous sections, the principles of dynamic programming enable it to be used in a variety of industries ranging from finance and transportation to retail and agriculture. In each of these sectors, the fundamental steps outlined in the algorithm discussion are applied toward their individual specific circumstances. Due to the vastness of its applicability, the basics of dynamic programming are embedded in a variety of software programs such as any GPS system or computerized game where a user can play against an algorithm. There are pieces of dynamic programming within almost any optimization application that invokes a hierarchical decision-making process.


=References=
'''''Bus Route Selection'''''
1. Bellman, Richard. “The Theory of Dynamic Programming.” ''Bulletin of American Mathematical Society, vol.'' 60, 1954, pp 503–515, <nowiki>https://www.ams.org/journals/bull/1954-60-06/S0002-9904-1954-09848-8/S0002-9904-1954-09848-8.pdf</nowiki>. 18 Nov 2020.


2. Bradley, Stephen P. ''Applied Mathematical Programming''. Addison-Wesley. 1 February 1977. 320-342. 18 Nov 2020
According to a study by engineering students Zhu Wenfei and LI Runmei, dynamic programming is the backbone of creating the most effective path for public transportation, for both the passengers and the city. The study focused on maximizing profit for the bus carriers and passengers, simultaneously. Though factors like distance between stops, average load factor, bus capacity and others are complex, these all affect how the bus operates most efficiently. Furthermore, these factors help form constraints included in models for passenger flow, passenger “satisfaction,” and bus scheduling and speed.<ref name=":1">Zhu, W and Li, R. (2014). Research on dynamic timetables of bus scheduling based on dynamic programming. Chinese Control Conference, pp. 8930-8934.</ref> Employing the process seen in the examples above, they determined that optimal intervals (Figure 1) where the bus can be most cost effective and useful for civilians.<ref name=":1" /> With a 40/60 weight on the two parties in the objective function, the optimization results show a very small decrease in satisfaction for the bus carriers, while a substantial increase for the passengers.  
[[File:Wiki - Dynamic Programming.docx.jpg|center|thumb|433x433px|A screenshot of final results from employing the method described above and indicating an improvement from current methods.<ref name=":1" /> ]]
'''''Hybrid Vehicle Optimization'''''


3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020
Because of how many variables are present in vehicle dynamics, it is certainly a prime application for dynamic programming. Specifically, there are unique objective functions for all types of vehicles due to their range in purpose. Lukic and Wang’s study on hybrid engine performance simulated a vehicle's configuration and how a set of parameters affected fuel consumption. For example, the effect of vehicle mass, planetary gear ratios, frontal surface area, maximum battery capacity, and few others were all evaluated to maximize the fuel economy.<ref name=":2">Wang, R and Lukic, S, M. (2012). Dynamic programming technique in hybrid electric vehicle optimization. IEEE International Electric Vehicle Conference, pp. 1-8.</ref> In doing so, it was found that having a state of charge (SOC) at the initial condition that was slightly higher, while simultaneously discouraging the utilization of the engine on/off feature, would result in the best combination of parameters for gas mileage in the test for PHEVs (plug-in hybrid electric vehicle).<ref name=":2" /> Overall, this method of including multiple parameters and evaluating them for a solution worked again for this set of constraints and single objective function
[[File:Wiki - Dynamic Programming.docx (1).jpg|center|thumb|468x468px|A results table from Lukic and Wang’s study that shows the optimal values of 0.9 and 0.5 for most optimal for best fuel economy.<ref name=":2" />]]


5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.
=Conclusion=
In conclusion, dynamic programming has changed the way that optimization problems can be solved.. Solving a dynamic programming problem begins with a critical assessment of whether dynamic programming is the right approach. This is determined by analyzing the problem's structure—specifically, whether it can be broken down into smaller, overlapping subproblems. If the problem exhibits these characteristics, it suggests that dynamic programming can provide an efficient solution.


6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.
DP is a valuable optimization method because of its ability to split and store subproblems to reach a global optimal value. Even further, it has the capability of working with all types of data whether it be complex numerical models or descriptions as strings of text. As seen with the examples in previous sections, a multitude of sectors benefit from the strengths and flexibility of DP. Considering dynamic programming has been developed into the largely inclusive tool that it is now, there are not many paths for its future directions. The algorithm has been and is continuously thoroughly examined and incorporated into viable solution spaces.  


7. Bellman, Richard. “Dynamic Programming Approach to Optimal Inventory Processes with Delay in Delivery.” ''Quarterly of Applied Mathematics'', vol 18, 1961, p. 399-403, <nowiki>https://www.ams.org/journals/qam/1961-18-04/S0033-569X-1961-0118516-2/S0033-569X-1961-0118516-2.pdf</nowiki>. 19 Nov 2020
=References=
<references />

Latest revision as of 19:53, 15 December 2024

Author: Satyasri Ventrapragada (sv353), John-Anthony Gonzales (jg2533), Salina Tekele (st2257)

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu

Introduction

In an attempt to innovate new ways for solving the world’s issues, scientists and mathematicians came together years ago to push forward with new ideas. After some time and iteration, dynamic programming (DP) was born –– a complex mathematical optimization method that aims to solve a wide range of problems. Dynamic programming is best used when the problem can be divided into subproblems that are solved until a globally optimal solution is reached. This comes with a small caveat from Sean Eddy claiming, dynamic programming is “guaranteed to give you a mathematically optimal (highest scoring) solution,” but it matters most how the data is scored[1]. Considering all of this, it is important to highlight that Richard Bellman pushed hard for advancements in the early stages and can be credited with the development of dynamic programming.

As mentioned, Richard Bellman – a well renowned Stanford professor that was contracting for a non-profit research institution at the time – founded monumental principles on dynamic programming beginning in the 1950s when he started publishing formal work on the topic. In his first publishing, Bellman was forced to strategically name the new computational method due to political condemnation. To avoid using words like “research” and “mathematical,” Bellman sought to emphasize the time-varying and incremental aspects of using the algorithm; therefore, he eventually chose “dynamic programming” to effectively summarize the intent of the steps he was creating [2].

After learning more about the principles and mechanics of dynamic programming, it is intended to aid in decision-making challenges that have the specific circumstantial opportunities for its use. In particular, anything similar to the applications that are discussed later are concrete examples of where and how dynamic programming can be implemented. As these examples will show, the main objectives are to show the ease of dynamic programming in practice, exactly how this takes place, and what some of the drawbacks and limitations might be. Having this tool widely available, easily deployable, and readily adaptable for any fitting situation has changed the way that optimization can occur for the better.

Algorithm Discussion

When tackling a dynamic programming problem, there are generally a number of key steps to follow. The first and most crucial step is determining whether dynamic programming is the right approach. A key indicator of this is whether the problem can be broken down into smaller, overlapping subproblems. Problems that involve minimizing or maximizing a quantity, or those that require counting possible arrangements, are often strong candidates for dynamic programming solutions.[3] For example, in the Fibonacci sequence:

F(n)=F(n−1)+F(n−2),F(0)=0,F(1)=1

Dynamic programming reduces the time complexity by reusing previously computed solutions.

Next, identify the key variables that change between subproblems, as they are crucial for breaking the problem down. listing a few subproblems and comparing their parameters helps which variables vary.

The third step is to define the recurrence relation, which expresses how the solution to a larger subproblem can be constructed from solutions to smaller subproblems. The recurrence relation serves as the core of the dynamic programming approach, describing how to combine the results of smaller subproblems to build up the final solution.[4] For example, in the Fibonacci number calculation the recurrence relation is given by:

F(n)=F(n−1)+F(n−2)

Once this is done, the next step is to identify the base cases which represent the simplest, smallest possible inputs for which the solution is trivial or already known.[3] The base cases for the Fibonacci sequence are defined as:

F(0)=0,F(1)=1

Base cases are essential because they serve as the foundation for building up solutions to more complex subproblems. They also act as stopping conditions for the recursion or termination conditions for the iterative approach, ensuring that the algorithm does not run indefinitely.

The following decision is whether to use a recursive (top-down, memoization) or iterative (bottom-up, tabulation) approach. The top-down approach uses recursion and caches results to avoid redundant calculations, but can lead to stack overflow with deep recursions. The bottom-up approach solves subproblems iteratively, saving space but being harder to understand initially. Both achieve the same goal.

Next, implement memoization (top-down) or tabulation (bottom-up). Memoization stores results of expensive function calls in a table or dictionary, returning the stored result for repeated subproblems to avoid redundant calculations. [3] Letting f(x) represent the solution to a subproblem, the first time f(x) is computed the results are stored in a table or cache T. For subsequent calls with the same input, the result is retrieved from the cache, T(x).

f(x) = { compute and store result in T(x) if f(x) is not already cached

f(x) = { T(x) if f(x) is cached }

This approach avoids redundant calculations, improving performance, especially for problems with overlapping subproblems.

Finally, the time complexity depends on the number of unique subproblems N and the time to solve each, T(x). The number of subproblems is determined by the distinct states defined by the changing parameters, and the complexity per subproblem depends on the work required to compute each solution.

Thus the total time complexity is:

Ttotal = N x T(x)

Dynamic programming often reduces time complexity from exponential to polynomial time, making otherwise intractable problems solvable.

Numerical Examples

Example 1: Knapsack Problem

The Smiths are trying to replicate a delicious Christmas fruitcake recipe, and the recipe calls for berries with a total of up to 11 lbs of berries packed into the fruitcake. The Smiths purchased 4 boxes of strawberries and 4 boxes of blueberries during their Christmas grocery shopping trip last weekend but are unsure of how many boxes of strawberries and blueberries to include in their fruitcake. Each box of strawberries weighs 2 lbs and each box of blueberries weighs 3 lbs. To make the choice easier, they spent all day researching how different amounts of strawberries and blueberries impact the taste of the fruitcake and made a benefit table listing the value each box of berries adds to the overall taste of the fruitcake. The benefit table is shown below in Table 1. Please use Dynamic Programming to help the Smiths choose the optimal number of boxes of strawberries and blueberries to include in their delicious Christmas fruitcake this year!


Table 1. Availability and weights of the berries.

Type of berry Availability (number of boxes) Weight per box (lb)
Strawberries 4 2
Blueberries 4 3


Table 2. Benefit table for number of boxes of berries.

Number of boxes of berries in fruitcake 0 1 2 3 4
Strawberries 0 2 3 5 7
Blueberries 0 1 2 4 5


To solve the Smiths’ fruitcake problem, we will be using dynamic programming through the following 8 steps:


Step 1: What are the stages?

The different types of items are the stages. For this problem, there are 2 stages: a box of strawberries or a box of blueberries, and the decision made in that stage is to specify the number of boxes of each berry to include in the fruitcake.


Step 2: What are the states?

The states correspond to the remaining number of boxes of berries we can include in the fruitcake. For example, if we had already made a decision to include 1 box of strawberries and 1 box of blueberries in the previous states, the current state would be 1 since the recipe requires only 3 total boxes of berries.


Step 3: What actions may be taken at each state in each stage?

If we are in stage n with availability a[n] and remaining capacity s, we can pack j items of type n into the fruitcake:


Step 4: What is the English-language description of the optimization function for each state s in stage n?

is the value of the maximum benefit possible with items of type n (or greater) while fitting into the remaining capacity s.

Step 5: What are the boundary conditions?

The benefit is 0 when there are no more types of berries to use even though there is remaining capacity.

, where N is the number of unique berries (N = 2) in this problem. Therefore, since there is no third type of berry.


Step 6: What is the recurrence relation?

We will construct a benefit function corresponding to each remaining capacity s for each of the items n, . . . , N to use j number of boxes of type n berries in the fruitcake.


Step 7: Compute optimal values in a bottom up fashion.

Let be the optimal number of boxes of berry type n where n=1 corresponds to strawberries and n=2 corresponds to blueberries.

Unused capacity s

(lbs of berries left to put into fruitcake)

(maximum benefit function for strawberries)

Type 1 opt

(optimal number of boxes of strawberries)

(maximum benefit function for blueberries)

Type 2 opt

(optimal number of boxes of blueberries)

11 0
10 0
9 0
8 0
7 0
6 0
5 0
4 0
3 0
2 0
1 0
0 0

Let’s start with our first state, s=11, where there are 11 lbs of berries left to add to the fruitcake.


Recall from Step 6:


Recall from Step 5 that is simply for a boundary condition and = 0.

Therefore,


Recall from Table 1 that the maximum benefit occurs when j = 3 where = 6. We can now fill in the first 3 rows of our table for n = 2 (blueberries) since the equation for U,,

will not change for when s = 11, 10, and 9 and will remain as . Similarly, when s = 8, 7, or 6, , when s = 5, 4, or 3, , and when s = 2, 1, or 0, . Since a greater number of boxes of blueberries results in a greater benefit function value as shown in Table 2, the j that will give us the most benefit for n = 2 would be the maximum value of the set for a given state, s. The populated values for n = 2 can be seen below.

Unused capacity s

(lbs of berries left to put into fruitcake)

(maximum benefit function for strawberries)

Type 1 opt

(optimal number of boxes of strawberries)

(maximum benefit function for blueberries)

Type 2 opt

(optimal number of boxes of blueberries)

11 4 3 0
10 4 3 0
9 4 3 0
8 2 2 0
7 2 2 0
6 2 2 0
5 1 1 0
4 1 1 0
3 1 1 0
2 0 0 0
1 0 0 0
0 0 0 0

What is the physical meaning of each row? For example, for the row when s = 7 lbs, 2 boxes of blueberries can be added into the fruitcake for maximum benefit ( = 5) since each box of blueberries weighs 3 lbs and the greater the number of boxes of blueberries, the more the benefit as seen in Table 2.

Now, we want to fill in the strawberries section of our table, or n=1. To do this, we repeat Step 7:

Let’s start with our first state, s=11, where there are 11 lbs of berries left to add to the fruitcake.

since a[1] = 4 and = 5.


Recall from Step 6:

Unlike before for n=1, the second term, , is not equal to 0. Therefore, we must calculate for each j in to find the optimal number of boxes of strawberries, , that corresponds to the maximum benefit, , for any given s. Let’s construct a table for s=11 just for clarity:

j in
0 = 0 + = 0 + 4 = 4
1 = 2 + = 2 + 4 = 6
2 = 3 + = 3 + 2 = 5
3 = 5 + = 5 + 1 = 6
4 = 7 + = 6 + 1 = 8

As seen above, the maximum , , occurs when = 4 . This means that the maximum benefit with respect to n=1 occurs when 4 boxes of strawberries are packed into the fruitcake when s=11. We will repeat this process for the rest of the states, s = 10, 9, …, 0, and the populated table is shown below.

Unused capacity s

(lbs of berries left to put into fruitcake)

(maximum benefit function for strawberries)

Type 1 opt

(optimal number of boxes of strawberries)

(maximum benefit function for blueberries)

Type 2 opt

(optimal number of boxes of blueberries)

11 8 4 5 3 0
10 7 4 5 3 0
9 7 4 5 3 0
8 7 4 2 2 0
7 5 3 2 2 0
6 5 3 2 2 0
5 3 2, 1 1 1 0
4 3 2 1 1 0
3 2 1 1 1 0
2 2 1 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0


Step 8: Find the optimal solution by looking at the table

The maximum benefit possible is 8, with 4 boxes of strawberries and 1 box of blueberries added to the fruitcake. Here are the steps after constructing the table to get to that final answer:

  1. Where does the maximum benefit occur? The maximum value for the benefit is 8, and this occurs at s = 11 where = 8 .
  2. How many boxes of strawberries does = 8 correspond to? = 4 when = 8 as seen in the table, so 4 boxes of strawberries.
  3. How many lbs of fruit remain to add into the fruitcake? The total capacity is 11 lbs, and 4 boxes of strawberries each weighing 2 lbs were already added, so . 3 lbs of fruit remain to add into the fruitcake.
  4. What is the optimal number of boxes of blueberries that should be added according to the table? Find s = 3, and find . = 1, so 1 box of blueberries should be added.

Final Answer: The Smiths should add 4 boxes of strawberries and 1 box of blueberries to their fruitcake.

Example 2: Layered Graphs

Find the shortest path in this layered graph using the concepts of dynamic programming.

Layered graph to find shortest path using dynamic programming.

We can partition the nodes into layers where the first layer is s, the second layer is A, B, and C, the third layer is D and E, the fourth layer is F and G, and the fifth layer is t. We will make a decision of the path to take at each layer, and each decision will correspond to a stage of the dynamic programming problem.

Layered graph with each stage, or layer.

To solve this shortest path problem, we will be using the previously explained 8 steps to solve the dynamic programming problem.

  1. What are the stages?
    • The stages are the different layers. There are 5 stages.
  2. What are the states?
    • The states are nodes in each layer.
  3. What actions may be taken at each state in each stage?
    • At each state in each stage, we will have to make a decision for which edge to pick. For example, in stage 1 (blue) and state B, we can pick either the edge with distance 3 or the edge with distance 4 since both edges are leaving node B.
  4. What is the English-language description of the optimization function for each state s in stage n?
    • is the minimum total cost to go from state r in stage i to reach node t, which is the final stage.
  5. What are the boundary conditions?
    • There is 0 cost for stage 4 since we have already reached the ending, node t.
  6. What is the recurrence relation?
  7. Compute the optimal path based on the recurrence relation defined in Step 6 and the boundary condition defined in Step 5.
    • We will assign a number to each node, and this number will correspond to the for that node as defined above in Step 6. This will be the smallest cumulative sum possible between that node and the edge connecting that node to the next layer, or next stage. The for each state in each stage are shown in red below, and the optimal path is indicated by the red arrows.
      Layered graph with for each node and shortest path in red.
  8. Find the optimal solution by looking up the table.
    • The length of the shortest path: f0*(s)=8. The shortest path can be found by following the red arrows moving forward. s → B → D → G → t.

Applications

As suggested in previous sections, the principles of dynamic programming enable it to be used in a variety of industries ranging from finance and transportation to retail and agriculture. In each of these sectors, the fundamental steps outlined in the algorithm discussion are applied toward their individual specific circumstances. Due to the vastness of its applicability, the basics of dynamic programming are embedded in a variety of software programs such as any GPS system or computerized game where a user can play against an algorithm. There are pieces of dynamic programming within almost any optimization application that invokes a hierarchical decision-making process.

Bus Route Selection

According to a study by engineering students Zhu Wenfei and LI Runmei, dynamic programming is the backbone of creating the most effective path for public transportation, for both the passengers and the city. The study focused on maximizing profit for the bus carriers and passengers, simultaneously. Though factors like distance between stops, average load factor, bus capacity and others are complex, these all affect how the bus operates most efficiently. Furthermore, these factors help form constraints included in models for passenger flow, passenger “satisfaction,” and bus scheduling and speed.[5] Employing the process seen in the examples above, they determined that optimal intervals (Figure 1) where the bus can be most cost effective and useful for civilians.[5] With a 40/60 weight on the two parties in the objective function, the optimization results show a very small decrease in satisfaction for the bus carriers, while a substantial increase for the passengers.

A screenshot of final results from employing the method described above and indicating an improvement from current methods.[5]

Hybrid Vehicle Optimization

Because of how many variables are present in vehicle dynamics, it is certainly a prime application for dynamic programming. Specifically, there are unique objective functions for all types of vehicles due to their range in purpose. Lukic and Wang’s study on hybrid engine performance simulated a vehicle's configuration and how a set of parameters affected fuel consumption. For example, the effect of vehicle mass, planetary gear ratios, frontal surface area, maximum battery capacity, and few others were all evaluated to maximize the fuel economy.[6] In doing so, it was found that having a state of charge (SOC) at the initial condition that was slightly higher, while simultaneously discouraging the utilization of the engine on/off feature, would result in the best combination of parameters for gas mileage in the test for PHEVs (plug-in hybrid electric vehicle).[6] Overall, this method of including multiple parameters and evaluating them for a solution worked again for this set of constraints and single objective function

A results table from Lukic and Wang’s study that shows the optimal values of 0.9 and 0.5 for most optimal for best fuel economy.[6]

Conclusion

In conclusion, dynamic programming has changed the way that optimization problems can be solved.. Solving a dynamic programming problem begins with a critical assessment of whether dynamic programming is the right approach. This is determined by analyzing the problem's structure—specifically, whether it can be broken down into smaller, overlapping subproblems. If the problem exhibits these characteristics, it suggests that dynamic programming can provide an efficient solution.

DP is a valuable optimization method because of its ability to split and store subproblems to reach a global optimal value. Even further, it has the capability of working with all types of data whether it be complex numerical models or descriptions as strings of text. As seen with the examples in previous sections, a multitude of sectors benefit from the strengths and flexibility of DP. Considering dynamic programming has been developed into the largely inclusive tool that it is now, there are not many paths for its future directions. The algorithm has been and is continuously thoroughly examined and incorporated into viable solution spaces.

References

  1. Eddy, S. (2004, July). What is dynamic programming?. Nature Biotechnology. https://doi.org/10.1038/nbt0704-909.
  2. Dreyfus, S. (2002, February). Richard Bellman on the Birth of Dynamic Programming, pp. 48-51.
  3. 3.0 3.1 3.2 Benjaminson, E. (2023, January). A Framework for Solving Dynamic Programming Problems. Github.io. sassafras13.github.io/SolvingDPProblems/.
  4. Luu, H. (2020, November). Dissecting Dynamic Programming – Top down & Bottom Up. Medium. hien-luu.medium.com/dissecting-dynamic-programming-top-down-bottom-up-3d3a1d62fbd7.
  5. 5.0 5.1 5.2 Zhu, W and Li, R. (2014). Research on dynamic timetables of bus scheduling based on dynamic programming. Chinese Control Conference, pp. 8930-8934.
  6. 6.0 6.1 6.2 Wang, R and Lukic, S, M. (2012). Dynamic programming technique in hybrid electric vehicle optimization. IEEE International Electric Vehicle Conference, pp. 1-8.