Cornell University Computational Optimization Open Textbook - Optimization Wiki - User contributions [en]

Eight step procedures

2020-12-14T04:59:23Z

Skepdb:

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=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. Specifying the stages also divides the problem into smaller pieces. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. There are multiple states for each stage. In general, the states consists of the information that is needed to solve the smaller problem within each stage.<ref>Chinneck. (2015). Chapter 15 Dynamic Programming. Carleton.Ca. https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf</ref> 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This helps create for a decision that must be made at each stage. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This can help create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function, and shows the relationsip between the value of a decision at a particular stage and the value of optimal decision made at the previous stages. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. Note that for each state, an optimal decision made at the remaining stages of the problem is independent from the decisions of the previous states. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step for solving a problem using the eight step procedure. 

=Numerical Example=
''Suppose we have a knapsack with a weight capacity of C=5 and N=2 types of items. An item of type n weighs W [n] and generates a benefit of b [n,j] when packing j items of type n to the knapsack however only a[n] units of this item are available.''

To solve a Knapsack problem we use the following steps:

'''Step 1: Specify the stages of the problem'''

Weight capacity of C=5 and N=2

'''Step 2: Specify the states for each stage'''

Item types are stages: n=1,2

'''Step 3: Specify the allowable actions for each state in each stage'''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

'''Step 4: Describe the optimization function using an English-language description.'''

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

'''Step 5: Define the boundary conditions'''

Boundary Conditions:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

'''Step 6: Define the recurrence relation'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

'''Step 7: Compute the optimal value from the bottom-up'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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
|}

'''Step 8: Arrive at the optimal solution'''

=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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

'''Needleman-Wunsh Algorithm (Global Sequence Alignment)'''

Developed by Saul B. Needleman and Christian D. Wunsch in 1970, the Needleman-Wunsh algorithm, also known as global sequence alignment, is used to find similarities within protein or nucleotide sequences. This algorithm is an application of dynamic programming used to divide a large problem such as a large sequence into smaller subproblems and the solutions of the subproblems are used to find the optimal sequences with the highest scores. A matrix is constructed consisting of strings of the protein or nucleotide sequences. A scoring system is determined for each of the nucleotide pairs (adenine, guanine, cytosine, thymine) where there could exist a match (+1), mismatch (-1), or gap (-1). The sum of the scores determine the entire alignment pair. Then the scores are calculated for the pairs and filled out in the matrix. To find the optimal alignment, one would perform a "traceback" by starting at the upper left matrix to the bottom right. The algorithm is limited in that it can align only entire proteins.<ref>Needleman, S. B. and Wunsch, C. D. "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins." J. Mol. Biol. 48, 1970, p. 443-453.</ref>

=Conclusion=
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.

=References=
<references />

Eight step procedures

2020-12-14T04:58:35Z

Skepdb:

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=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. Specifying the stages also divides the problem into smaller pieces. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. There are multiple states for each stage. In general, the states consists of the information that is needed to solve the smaller problem within each stage.<ref>Chinneck. (2015). Chapter 15 Dynamic Programming. Carleton.Ca. https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf</ref> 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This helps create for a decision that must be made at each stage. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This can help create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function, and shows the relationsip between the value of a decision at a particular stage and the value of optimal decision made at the previous stages. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. Note that for each state, an optimal decision made at the remaining stages of the problem is independent from the decisions of the previous states. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step for solving a problem using the eight step procedure. 

=Numerical Example=
''Suppose we have a knapsack with a weight capacity of C=5 and N=2 types of items. An item of type n weighs W [n] and generates a benefit of b [n,j] when packing j items of type n to the knapsack however only a[n] units of this item are available.''

To solve a Knapsack problem we use the following steps:

'''Step 1: Specify the stages of the problem'''

Weight capacity of C=5 and N=2

'''Step 2: Specify the states for each stage'''

Item types are stages: n=1,2

'''Step 3: Specify the allowable actions for each state in each stage'''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

'''Step 4: Describe the optimization function using an English-language description.'''

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

'''Step 5: Define the boundary conditions'''

Boundary Conditions:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

'''Step 6: Define the recurrence relation'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

'''Step 7: Compute the optimal value from the bottom-up'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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
|}

'''Step 8: Arrive at the optimal solution'''

=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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

'''Needleman-Wunsh Algorithm (Global Sequence Alignment)'''

Developed by Saul B. Needleman and Christian D. Wunsch in 1970, the Needleman-Wunsh algorithm, also known as global sequence alignment, is used to find similarities within protein or nucleotide sequences. This algorithm is an application of dynamic programming used to divide a large problem such as a large sequence into smaller subproblems and the solutions of the subproblems are used to find the optimal sequences with the highest scores. A matrix is constructed consisting of strings of the protein or nucleotide sequences. A scoring system is determined for each of the nucleotide pairs (adenine, guanine, cytosine, thymine) where there could exist a match (+1), mismatch (-1), or gap (-1). The sum of the scores determine the entire alignment pair. Then the scores are calculated for the pairs and filled out in the matrix. To find the optimal alignment, one would perform a "traceback" by starting at the upper left matrix to the bottom right. The algorithm is limited in that it can align only entire proteins<ref>Needleman, S. B. and Wunsch, C. D. "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins." J. Mol. Biol. 48, 1970, p. 443-453.</ref>

=Conclusion=
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.

=References=
<references />

Eight step procedures

2020-12-14T04:27:15Z

Skepdb: /* Numerical Example */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=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. Specifying the stages also divides the problem into smaller pieces. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. There are multiple states for each stage. In general, the states consists of the information that is needed to solve the smaller problem within each stage.<ref>Chinneck. (2015). Chapter 15 Dynamic Programming. Carleton.Ca. https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf</ref> 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This helps create for a decision that must be made at each stage. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This can help create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function, and shows the relationsip between the value of a decision at a particular stage and the value of optimal decision made at the previous stages. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. Note that for each state, an optimal decision made at the remaining stages of the problem is independent from the decisions of the previous states. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step for solving a problem using the eight step procedure. 

=Numerical Example=
''Suppose we have a knapsack with a weight capacity of C=5 and N=2 types of items. An item of type n weighs W [n] and generates a benefit of b [n,j] when packing j items of type n to the knapsack however only a[n] units of this item are available.''

To solve a Knapsack problem we use the following steps:

'''Step 1: Specify the stages of the problem'''

Weight capacity of C=5 and N=2

'''Step 2: Specify the states for each stage'''

Item types are stages: n=1,2

'''Step 3: Specify the allowable actions for each state in each stage'''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

'''Step 4: Describe the optimization function using an English-language description.'''

<math>f^{*}_{n}(s)</math>

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

'''Step 5: Define the boundary conditions'''

Boundary Conditions:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

'''Step 6: Define the recurrence relation'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

'''Step 7: Compute the optimal value from the bottom-up'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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
|}

'''Step 8: Arrive at the optimal solution'''

<math> f^{*}_{1}(5)= 26 </math>

=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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

=Conclusion=
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.

=References=

Eight step procedures

2020-12-14T03:29:01Z

Skepdb: /* Numerical Example */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=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. Specifying the stages also divides the problem into smaller pieces. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. There are multiple states for each stage. In general, the states consists of the information that is needed to solve the smaller problem within each stage.<ref>Chinneck. (2015). Chapter 15 Dynamic Programming. Carleton.Ca. https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf</ref> 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This helps create for a decision that must be made at each stage. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This can help create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function, and shows the relationsip between the value of a decision at a particular stage and the value of optimal decision made at the previous stages. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. Note that for each state, an optimal decision made at the remaining stages of the problem is independent from the decisions of the previous states. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step for solving a problem using the eight step procedure. 

=Numerical Example=
''Suppose we have a knapsack with a weight capacity of C=5 and N=2 types of items. An item of type n weighs W [n] and generates a benefit of b [n,j] when packing j items of type n to the knapsack however only a[n] units of this item are available.''

To solve a Knapsack problem we use the following steps:

'''Step 1: Specify the stages of the problem'''

Weight capacity of C=5 and N=2

'''Step 2: Specify the states for each stage'''

Item types are stages: n=1,2

'''Step 3: Specify the allowable actions for each state in each stage'''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

'''Step 4: Describe the optimization function using an English-language description.'''

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

'''Step 5: Define the boundary conditions'''

Boundary Conditions:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

'''Step 6: Define the recurrence relation'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

'''Step 7: Compute the optimal value from the bottom-up'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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
|}

'''Step 8: Arrive at the optimal solution'''

=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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

=Conclusion=
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.

=References=

Eight step procedures

2020-12-14T02:52:22Z

Skepdb: /* Methodology */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=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. Specifying the stages also divides the problem into smaller pieces. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. There are multiple states for each stage. In general, the states consists of the information that is needed to solve the smaller problem within each stage.<ref>Chinneck. (2015). Chapter 15 Dynamic Programming. Carleton.Ca. https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf</ref> 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This helps create for a decision that must be made at each stage. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This can help create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function, and shows the relationsip between the value of a decision at a particular stage and the value of optimal decision made at the previous stages. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. Note that for each state, an optimal decision made at the remaining stages of the problem is independent from the decisions of the previous states. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step for solving a problem using the eight step procedure. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

=Conclusion=
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.

=References=

Eight step procedures

2020-12-14T02:46:22Z

Skepdb: /* Methodology */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. There are multiple states for each stage. In general, the states consists of the information that is needed to solve the smaller problem within each stage.<ref>Chinneck. (2015). Chapter 15 Dynamic Programming. Carleton.Ca. https://www.sce.carleton.ca/faculty/chinneck/po/Chapter15.pdf</ref> 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. Note that for each state, an optimal decision made at the remaining stages of the problem is independent from the decisions of the previous states. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

=Conclusion=
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.

=References=

Eight step procedures

2020-12-14T02:25:03Z

Skepdb: /* References */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

=Conclusion=
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.

=References=

Eight step procedures

2020-12-14T02:24:39Z

Skepdb: /* Applications */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:24:04Z

Skepdb: /* Applications */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.<ref>Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.</ref>

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:23:34Z

Skepdb: /* Applications */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>Neumann K. “Dynamic Programming Basic Concepts and Applications.” Optimization in Planning and Operations of Electric Power Systems. Physica, Heidelberg, 1993, p 31-56.</ref>

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:22:56Z

Skepdb: /* Introduction */

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

=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 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.<ref>Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. https://www.byte-by-byte.com/dpbook/. 18 Nov 2020</ref>

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:22:31Z

Skepdb: /* Introduction */

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

=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 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:22:03Z

Skepdb: /* Introduction */

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

=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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:20:59Z

Skepdb: /* References */

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

=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 1950s1, 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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:20:38Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=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 1950s1, 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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
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> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

4. You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T02:20:03Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=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 1950s1, 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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
To solve a problem using the 8-step procedure, one must use the following steps:<ref>4</ref> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

4. You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-14T00:17:01Z

Skepdb: /* Methodology */

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

=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 1950s1, 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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

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

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
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>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often denoted with a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

4. You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-12-11T21:31:07Z

Skepdb:

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

=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 1950s1, 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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

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

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision. This is often denoted by <math>s</math>. Often, <math>C</math> is set equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This stage varies greatly based on the problem presented. 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. 
 

'''Step 6: Define the recurrence relation''' 
This is often noted by a function. 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
This is the final step. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

4. You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-11-25T22:20:45Z

Skepdb:

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

=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 1950s1, 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 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.2 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.3

=Theory, Methodology, and/or Algorithmic Discussion=

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

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This can be defined as: 
<math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 

'''Step 6: Define the recurrence relation''' 
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
<math> 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 \} </math> 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.5

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. 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.6

'''Inventory Planning Problem'''

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.7

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

4. You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-11-25T22:16:11Z

Skepdb:

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

=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>1</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 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>2</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.<ref>3</ref>

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
To solve a problem using the 8-step procedure, one must use the following steps:<ref>4</ref> 
 

'''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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This can be defined as: 
<math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 

'''Step 6: Define the recurrence relation''' 
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
<math> 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 \} </math> 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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.<ref>5

</ref>

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. 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.<ref>6</ref>

'''Inventory Planning Problem'''

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.<ref>7</ref>

=Conclusion=
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.

=References=
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

3. Gavin-Hughes, Sam. “Dynamic Programming for Interviews.” Byte by Byte. <nowiki>https://www.byte-by-byte.com/dpbook/</nowiki>. 18 Nov 2020

4. You, Fengqi. “Dynamic Programming” 5 Oct 2020. Online. Microsoft PowerPoint presentation.

5. Neumann K. “Dynamic Programming Basic Concepts and Applications.” ''Optimization in Planning and Operations of Electric Power Systems''. Physica, Heidelberg, 1993, p 31-56.

6. Taylor, C. Robert. Applications Of Dynamic Programming To Agricultural Decision Problems. United States, CRC Press, 2019.

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

Eight step procedures

2020-11-22T20:33:55Z

Skepdb: /* Introduction */

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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This can be defined as: 
<math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 

'''Step 6: Define the recurrence relation''' 
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
<math> 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 \} </math> 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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'''

=Conclusion=

=References=

Eight step procedures

2020-11-22T06:23:11Z

Skepdb: /* Introduction */

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

=Introduction=

=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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This can be defined as: 
<math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 

'''Step 6: Define the recurrence relation''' 
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
<math> 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 \} </math> 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|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=

=Conclusion=

=References=

Eight step procedures

2020-11-22T06:18:40Z

Skepdb: /* Introduction */

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

=Introduction=

=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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This can be defined as: 
<math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 

'''Step 6: Define the recurrence relation''' 
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
<math> 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 \} </math> 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=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:

<math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

<math> f^{*}_{2}(5)= max\left \{ b[2,j]+ f^{*}_{3}(5-j*w[2]) \right \} </math>=
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|5
|
|
|
|
|0
|-
|4
|
|
|
|
|0
|-
|3
|
|
|
|
|0
|-
|2
|
|
|
|
|0
|-
|1
|
|
|
|
|0
|-
|0
|
|
|
|
|0
|}

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-22T06:10:18Z

Skepdb:

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

=Introduction=

=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 <math>n</math>. 
 

'''Step 2: Specify the states for each stage''' 
The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 

'''Step 3: Specify the allowable actions for each state in each stage''' 
This can be defined as: 
<math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 

'''Step 4: Describe the optimization function using an English-language description.''' 
In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 

'''Step 5: Define the boundary conditions''' 
This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 

'''Step 6: Define the recurrence relation''' 
During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
<math> 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 \} </math> 
 

'''Step 7: Compute the optimal value from the bottom-up''' 
In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 

'''Step 8: Arrive at the optimal solution''' 
Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=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

<math>
U_{2}(5)\, =\, 0,1,...,min\left \{ a[2], \left \lfloor \frac{5}{w[2]}\right \rfloor \right \}
</math>= '''{0,1,2}'''

Boundary Conditions: <math>f^{*}_{n+1}(s) = 0</math>, ''s=0,1,2,3,4,5'' ''C=5''

<math> 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 \} </math>
{| class="wikitable"
|+
!Unused Capacity s
!<math>f^{*}_{1}(s)</math>
!Type 1 opt <math>U^{*}_{1}(s)</math>
!<math>f^{*}_{2}(s)</math>
!Type 2 opt <math>U^{*}_{2}(s)</math>
!<math>f^{*}_{3}(s)</math>
|-
|5
|
|
|
|
|0
|-
|4
|
|
|
|
|0
|-
|3
|
|
|
|
|0
|-
|2
|
|
|
|
|0
|-
|1
|
|
|
|
|0
|-
|0
|
|
|
|
|0
|}

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-22T04:34:43Z

Skepdb: /* Numerical Example */

Eight step procedures

2020-11-21T01:34:22Z

Skepdb: /* Methodology */

Eight step procedures

2020-11-21T01:29:40Z

Skepdb: /* Definition */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Methodology===
To solve a problem using the 8-step procedure, one must follow 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 <math>n</math>. 
 
'''Step 2: Specify the states for each stage''' 
• The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o <math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 
'''Step 4: Describe the optimization function using an English-language description.''' 
• In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 
'''Step 5: Define the boundary conditions''' 
• This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
o <math> 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 \} </math> 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 
'''Step 8: Arrive at the optimal solution''' 
• Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-21T01:28:58Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Definition===
To solve a problem using the 8-step procedure, one must follow 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 <math>n</math>. 
 
'''Step 2: Specify the states for each stage''' 
• The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o <math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 
'''Step 4: Describe the optimization function using an English-language description.''' 
• In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 
'''Step 5: Define the boundary conditions''' 
• This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
o <math> 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 \} </math> 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made containing all <math>s</math>, <math>f^{*}_{n}(s)</math>, and optimal values for all <math>n</math> variables. This step can be done manually or by using programming. 
 
'''Step 8: Arrive at the optimal solution''' 
• Once the value for <math>f^{*}_{n}(s)</math> 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 <math>n</math>, calculate our remaining space <math>s</math>, and use that value to arrive at an optimal value for all <math>n</math>. 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-20T23:40:38Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Definition===
To solve a problem using the 8-step procedure, one must follow 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 <math>n</math>. 
 
'''Step 2: Specify the states for each stage''' 
• The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o <math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 
'''Step 4: Describe the optimization function using an English-language description.''' 
• In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 
'''Step 5: Define the boundary conditions''' 
• This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math> s=0,...,C </math> 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
o <math> 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 \} </math> 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-20T23:32:52Z

Skepdb: /* Definition */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Definition===
To solve a problem using the 8-step procedure, one must follow 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 <math>n</math>. 
 
'''Step 2: Specify the states for each stage''' 
• The states of a problem are defined as the knowledge necessary to make a decision, or <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o <math>
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
</math> 
 
'''Step 4: Describe the optimization function using an English-language description.''' 
• In this sentence, we describe the optimization function for each state, or <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> 
 
'''Step 5: Define the boundary conditions''' 
• This helps create a starting point to finding a solution to the problem. First, we set <math>f^{*}_{n+1}(s) = 0</math> for all values of <math>s</math>. Here, we can note that <math>s = 0,…,C</math> 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. We can write this statement as: 
o f*n(s) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])} 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-20T23:27:46Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

Eight step procedures

2020-11-20T23:25:35Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

Eight step procedures

2020-11-20T22:43:59Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Definition===
To solve a problem using the 8-step procedure, one must follow 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 s. We set C equal to the maximum value of s. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o <img src="https://latex.codecogs.com/gif.latex?U_{n}(s)\,&space;or\,&space;j\,&space;=\,&space;0,1,...,min\left&space;\{&space;a[n],&space;\left&space;\lfloor&space;\frac{s}{w[n]]}&space;\right&space;\rfloor&space;\right&space;\}" title="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 s, and each stage, or n. This can also be called 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 f*n+1(s) = 0 for all values of s. Here, we can note that s = 0,…,C 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving j items for the remaining capacity s for items n. We can write this statement as: 
o f*n(s) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])} 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-20T22:43:17Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Definition===
To solve a problem using the 8-step procedure, one must follow 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 s. We set C equal to the maximum value of s. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o [img[https://latex.codecogs.com/gif.latex?U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a%5Bn%5D, \left \lfloor \frac{s}{w%5Bn%5D%5D} \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 s, and each stage, or n. This can also be called 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 f*n+1(s) = 0 for all values of s. Here, we can note that s = 0,…,C 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving j items for the remaining capacity s for items n. We can write this statement as: 
o f*n(s) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])} 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-20T22:42:33Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

===Definition===
To solve a problem using the 8-step procedure, one must follow 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 s. We set C equal to the maximum value of s. 
 
'''Step 3: Specify the allowable actions for each state in each stage''' 
• This can be defined as: 
o <a href="https://www.codecogs.com/eqnedit.php?latex=U_{n}(s)\,&space;or\,&space;j\,&space;=\,&space;0,1,...,min\left&space;\{&space;a[n],&space;\left&space;\lfloor&space;\frac{s}{w[n]]}&space;\right&space;\rfloor&space;\right&space;\}" target="_blank"><img src="https://latex.codecogs.com/gif.latex?U_{n}(s)\,&space;or\,&space;j\,&space;=\,&space;0,1,...,min\left&space;\{&space;a[n],&space;\left&space;\lfloor&space;\frac{s}{w[n]]}&space;\right&space;\rfloor&space;\right&space;\}" title="U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]]} \right \rfloor \right \}" /></a> 
 
'''Step 4: Describe the optimization function using an English-language description.''' 
• In this sentence, we describe the optimization function for each state, or s, and each stage, or n. This can also be called 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 f*n+1(s) = 0 for all values of s. Here, we can note that s = 0,…,C 
 
'''Step 6: Define the recurrence relation''' 
• During this step, we make an allowable decision involving j items for the remaining capacity s for items n. We can write this statement as: 
o f*n(s) = max j=0,1,…,min{a[n], floor(s/w[n]0} {b[n,j]+f*n+a(s-j*w[n])} 
 
'''Step 7: Compute the optimal value from the bottom-up''' 
• In this step, a table is made 

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-20T22:35:31Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

Eight step procedures

2020-11-20T22:28:56Z

Skepdb: /* Theory, Methodology, and/or Algorithmic Discussion */

Eight step procedures

2020-11-20T22:22:10Z

Skepdb: /* Definition */

Eight step procedures

2020-11-20T22:21:19Z

Skepdb: /* Definition */

Eight step procedures

2020-11-20T22:16:05Z

Skepdb:

Eight step procedures

2020-11-20T03:01:38Z

Skepdb:

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

=Introduction=

=Theory, Methodology, and/or Algorithmic Discussion=

=Numerical Example=

=Applications=

=Conclusion=

=References=

Eight step procedures

2020-11-11T01:08:23Z

Skepdb: Created page with "Author: Eljona Pushaj, Diana Bogdanowich, Stephanie Keomany Steward: Fengqi You"

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

Quadratic programming

2020-11-11T00:54:40Z

Skepdb:

This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Quadratic_programming

Author: Jack Heider (ChE 345 Spring 2015) 
Steward: Dajun Yue, Fengqi You

=Introduction=
[[File:QPPic.jpg|frame|Optimizating of a quadratic function.12]]

Quadratic programming (QP) is the problem of optimizing a quadratic objective function and is one of the simplests form of non-linear programming.1 The objective function can contain bilinear or up to second order polynomial terms,2 and the constraints are linear and can be both equalities and inequalities. QP is widely used in image and signal processing, to optimize financial portfolios, to perform the least-squares method of regression, to control scheduling in chemical plants, and in [https://optimization.mccormick.northwestern.edu/index.php?title=Sequential_quadratic_programming&action=edit&redlink=1 sequential quadratic programming], a technique for solving more complex non-linear programming problems.3,4 The problem was first explored in the early 1950s, most notably by Princeton University's [http://en.wikipedia.org/wiki/Philip_Wolfe_(mathematician) Wolfe] and [http://en.wikipedia.org/wiki/Marguerite_Frank Frank], who developed its theoretical background,1 and by [http://en.wikipedia.org/wiki/Harry_Markowitz Harry Markowitz], who applied it to portfolio optimization, a subfield of finance.

=Problem formulation=
A general quadratic programming formulation contains a quadratic objective function and linear equality and inequality constraints:2,5,6

<math>\text{min} f(x)=q^{T}x+\frac{1}{2}x^{T}Qx</math> 
<math>s.t. Ax=a</math> 
<math>Bx\le b</math> 
<math>x\ge0</math>

The objective function is arranged such that the vector <math>q</math> contains all of the (singly-differentiated) linear terms and <math>Q</math> contains all of the (twice-differentiated) quadratic terms. Put more simply, <math>Q</math> is the Hessian matrix of the objective function and <math>q</math> is its gradient. By convention, any constants contained in the objective function are left out of the general formulation.6 The one-half in front of the quadratic term is included to remove the coefficient (2) that results from taking the derivative of a second-order polynomial.

As for the constraints, the matrix equation <math>Ax=a</math> contains all of the linear equality constraints, and <math>Bx \le b</math> are the linear inequality constraints.

When there are only inequality constraints (<math>Bx\le b</math>), the Lagrangean is:6 
<math>L(x,\lambda,\mu)=q^{T}x+\frac{1}{2}x^{T}Qx+{\lambda}^T(Ax-a)+{\mu}^T(Bx-b)=0</math> 

==Global solutions==
If the objective function is convex, then any local minimum found is also the sole global minimum. To analyze the function’s convexity, one can compute its Hessian matrix and verify that all eigenvalues are positive, or, equivalently, one can verify that the matrix Q is positive definite.6 This is a sufficient condition, meaning that it is not required to be true in order for a local minimum to be the unique global minimum, but will guarantee this property holds if true.

==KKT conditions==
Solutions can be tested for optimality using Karush-Kuhn-Tucker conditions just as is done for other nonlinear problems:5 

Condition 1: sum of gradients is zero: 
<math>\triangledown L({x}^*,{\lambda}^*,{\mu}^*)=q^{T}+\frac{1}{2}x^{T}Q+{\lambda}^{*T}A+{\mu}^{*T}B</math> 

Condition 2: all constraints satisfied: 
<math>Ax^*-a=0</math> 
<math>Bx^*-b\le0</math>

Condition 3: complementary conditions: 
<math>{\mu}^TBx-b=0</math> 
<math>{x}^{T},{\lambda}^{T},{\mu}^T\ge0</math>

==Solution strategies==
Because quadratic programming problems are a simple form of nonlinear problem, they can be solved in the same manner as other non-linear programming problems.
An unconstrained quadratic programming problem is most straightforward to solve: simply set the derivative (gradient) of the objective function equal to zero and solve.7 More practical (constrained) formulations are more difficult to solve. The typical solution technique when the objective function is strictly convex and there are only equality constraints is the [https://optimization.mccormick.northwestern.edu/index.php?title=Conjugate_gradient_methods&action=edit&redlink=1 conjugate gradient method]. If there are inequality constraints (<math>Bx\le b</math>), then the [https://optimization.mccormick.northwestern.edu/index.php/Interior-point_method_for_NLP interior point] and active set methods are the preferred solution methods. When there is a range on the allowable values of <math>x</math> (in the form <math>x^L\le x\le x^U</math>, which is the case for image and signal processing applications, [https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods trust-region methods] are most frequently used.4 For all convex cases, an NLP solver in the optimization utility GAMS, such as KNITRO, MINOS, or CONOPT, can find solutions for quadratic programming problems.

=Numerical example=
[[File:ChE345 Wiki Mathematica.png|frame|Plot of the unconstrained objective function. Figure generated using Wolfram Mathematica.]]

This example demonstrates how to determine the KKT point of a specific QP problem:

<math>\text{min}</math>
<math>f(x)=3{x_1}^2+{x_2}^2+2{x_1}{x_2}+x_1+6{x_2}+2</math> 
<math>\text{s.t.}</math>
<math>2{x_1}+3{x_2} \ge 4</math> 
<math>{x_1},{x_2} \ge 0</math>

Rewrite the constraints. 
<math>g_1=-2{x_1}-3{x_2}+4\le 0</math> 
<math>g_2=-{x_1} \le 0</math> 
<math>g_3=-{x_2} \le 0</math> 

Construct the gradients. 
<math>\triangledown f= \begin{bmatrix} 6{x_1}+2{x_2}+1 \\ 2{x_1}+2{x_2}+6 \end{bmatrix}, \triangledown {g_1}= \begin{bmatrix} -2 \\ -3 \end{bmatrix}, \triangledown {g_2}= \begin{bmatrix} -1 \\ 0 \end{bmatrix}, \triangledown {g_3}= \begin{bmatrix} 0 \\ -1 \end{bmatrix} </math>

Assuming all constraints are satisfied, set the gradient equal to zero to attempt to find an optima. 
<math>6{x_1}+2{x_2}+1=0</math> 
<math>2{x_1}+2{x_2}+6=0</math> 

<math>{x_1}=\frac{5}{4}</math>,
<math>{x_2}=-\frac{17}{4}</math> 

Make constraints <math>g_1</math> and <math>g_3</math>, which are violated, active. Set both equal to zero. 
<math>{g_1} = -2{x_1}-3{x_2}+4=0</math> 
<math>{g_3} = -{x_2}=0</math> 

Solve the resulting system of equations. 
<math>\triangledown f+ {\mu_1} \triangledown {g_1}+ {\mu_3} \triangledown {g_3} =0</math> 
<math>{g_1}=0</math> 
<math>{g_3}=0</math> 

<math> \begin{bmatrix} 6{x_1}+2{x_2}+1 \\ 2{x_1}+2{x_2}+6 \end{bmatrix} +{\mu_1} \begin{bmatrix} -2 \\ -3 \end{bmatrix} +{\mu_3} \begin{bmatrix} 0 \\ -1 \end{bmatrix} </math> 
<math>-2{x_1}-3{x_2}+4=0</math> 
<math>-{x_2}=0</math> 

Formulating the system as one matrix and row reducing is one of the simplest ways to solve. Doing so yields: 
<math>{x_1}=2, {x_2}=0, {\mu_1}=6.5, {\mu_3}=9.5</math> 

Drop constraint <math>g_3</math> because <math>{\mu_3}</math> is negative and resolve the system. Doing so yields: 
<math>{x_1}=0.5, {x_2}=1, {\mu_1}=3</math> 

Which yields an objective function value of <math>f=11.25</math> 

Verify linear dependence of the gradient: 
<math>\triangledown f+ {\mu_1} \triangledown {g_1}</math> 
<math> \begin{bmatrix} 6 \\ 9 \end{bmatrix} +3 \begin{bmatrix} -2 \\ -3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \therefore </math> 

Verify the uniqueness of the solution: 
<math>{\triangledown}^2 f(x)= \begin{bmatrix} 6 & 2 \\ 2 & 1 \end{bmatrix} \rightarrow \begin{bmatrix} 6-\lambda & 2 \\ 2 & 1-\lambda \end{bmatrix} =0 \rightarrow \lambda = 0.298, 6.702</math>

Because both eigenvalues are positive, the Hessian matrix is positive determinant, and this local minimum is the global minimum of the objective function given these constraints. 

=Applications=

A few of the many quadratic programming applications are discussed in more detail and accompanied with general models below, and a list of other areas in which QP is important is presented as well.

*Quadratic knapsack problem (QKP)
In the standard knapsack problem, there are a number of items with different weights and values, and the items are selected based on which combination yields the highest overall value without exceeding the overall weight limit of the knapsack.

In the quadratic knapsack problem, the objective function is quadratic or, more specifically, bilinear, and the constraints are the same as in the typical knapsack problem.8 QKP's are used in designing email servers and to optimize the locations of "nodes" in applications such as positioning transportation hubs like airports and train stations.8 Additionally, the problem can model situations in which a limited number of people are assigned to complete specific objectives that require them to interact.9 One formulation is presented below:8 
<math>\text{max or min}</math>
<math>x^{T}Qx</math> 
<math>Ax \le a</math> 
<math>x \in {B}^{n} </math> 

The quadratic knapsack problem, although it looks very simple, is NP-hard and is thus difficult to solve. To make obtaining solutions easier, these problems are often linearized.8

*Model predictive control
Quadratic programming also has important applications in chemical engineering. Model predictive control (MPC) is a group of algorithms that help manage production in chemical plants by dictating production in each batch. While often formulated as linear programs because the resulting models are more stable, robust and easier to solve, MPC models are sometimes made with quadratic programming.11 As an example of its utility, quadratic programming was used by Di Ruscio in an MPC algorithm for a thermomechanical pulping process, which a method for making paper.11

*Least squares
Least squares regression is one of the most common types of regression, and works by minimizing the sum of the squares of the difference between data points and a proposed fit. Quadratic optimization is one method that can be used to perform a least squares regression and is more flexible than most linear methods. One formulation for a quadratic programming regression model is as follows:3

<math>\text{min}</math>
<math>e'Ie</math> 
<math>e = Y-X \beta</math>

In this model, <math>\beta</math> and <math>e</math> are the unknown regression parameters, <math>I</math> is an identity matrix, and <math>X</math> and <math>Y</math> contain data about the independent and dependent variables respectively.3

*Other applications
Quadratic programming is used in a wide range of applications not touched upon in the sample presented above. Other major areas in which QP's are relied upon include signal and image processing12 and a subfield of optimization called partial differential constrained optimization.3 QP's are also extensively used in finance, as variance, which is used to measure risk, is a function containing squares.13,14,15 More specifically, Markowitz won the 1990 Nobel Prize in Economics for his widely-used model that employs quadratic programming to optimizes the amount of risk taken on based on variances.14

Additionally, [https://optimization.mccormick.northwestern.edu/index.php?title=Sequential_quadratic_programming&action=edit&redlink=1 Sequential quadratic programming], an algorithm for solving more complicated NLP's that uses QP subproblems, is one of the most important applications.

=Conclusion=
Quadratic programming, the problem of optimizing a quadratic function, have been widely used since its development in the 1950s because it is a simple type of non-linear programming that can accurately model many real world systems, notably ones dependent on two variables. Problems formulated this way are straightforward to optimize when the objective function is convex. QP has applications in finance, various types of computer systems, statistics, chemical production, and in algorithms to solve more complex NLP's.

=References=
1. Frank, Marguerite, and Philip Wolfe. "An Algorithm for Quadratic Programming." Naval Research Logistics Quarterly 3 (1956): 95-110. Web. 4 June 2015. 
2. Floudas, Christodoulos A., and V. Visweswaran. "Quadratic Optimization." Nonconvex Optimization and Its Applications, 2 (1995): 217-69. Web. 23 May 2015. 
3. McCarl, Bruce A., Moskowitz, Herbert, and Harley Furtan. "Quadratic Programming Applications." The International Journal of Management Science, 5 (1977): 43-55. 
4. Geletu, Abele. "Quadratic programming problems." Ilmenau University of Technology. Web. 23 May 2015. 
5. Bradley, Hax, and Magnanti. Applied Mathematical Programming. Boston: Addison-Wesley, 1997. 421-40. Web. 23 May 2015. 
6. Jensen, Paul A., and Jonathan F. Bard. "Quadratic Programming." Operations Research Models and Methods. The University of Texas at Austin. Web. 23 May 2015. 
7. Binner, David. "Quadratic programming example - no constraints." Miscellaneous mathematical utilities. AKiTi. Web. 23 May 2015. 
8. Pisinger, David. "The Quadratic Knapsack Problem – A Survey." Discrete Applied Mathematics, 155 (2007): 623 – 648. Web. 23 May 2015. 
9. "Quadratic Multiple Knapsack Problem." Optimization of Complex System. Optiscom Project. 2012. Web. 6 June 2015. 
10. Gallo, G., P. L. Hammer, and B. Simeone. "Quadratic Knapsack Problems." Mathematical Programming 12 (1980): 132-149. Web. 24 May 2015. 
11. Di Ruscio, David. "Model Predictive Control and Optimization." Telemark University College. Mar. 2001. Web. 24 May 2015. 
12. Ma, W. K. "Signal Processing Optimization Techniques." The Chinese University of Hong Kong. Web. 24 May 2015. 
13. Tütüncü, Reha H. "Optimization in Finance." Tokyo Institute of Technology. Spring 2003. Web. 23 May 2015. 
14. Van Slyke, R. "Portfolio Optimization." NYU Polytechnic School of Engineering. 16 Nov. 2007. Web. 24 May 2015. 
15. "Portfolio Optimization." SAS/OR(R) 9.2 User's Guide: Mathematical Programming. SAS Institute. Web. 23 May 2015.

Quadratic programming

2020-11-11T00:54:07Z

Skepdb: test

This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Quadratic_programming

Author: Jack Heider (ChE 345 Spring 2015) 
Steward: Dajun Yue, Fengqi You

=Introduction=
[[File:QPPic.jpg|frame|Optimizating of a quadratic function.12]]

Quadratic programming (QP) is the problem of optimizing a quadratic objective function and is one of the simplests form of non-linear programming.1 The objective function can contain bilinear or up to second order polynomial terms,2 and the constraints are linear and can be both equalities and inequalities. QP is widely used in image and signal processing, to optimize financial portfolios, to perform the least-squares method of regression, to control scheduling in chemical plants, and in [https://optimization.mccormick.northwestern.edu/index.php?title=Sequential_quadratic_programming&action=edit&redlink=1 sequential quadratic programming], a technique for solving more complex non-linear programming problems.3,4 The problem was first explored in the early 1950s, most notably by Princeton University's [http://en.wikipedia.org/wiki/Philip_Wolfe_(mathematician) Wolfe] and [http://en.wikipedia.org/wiki/Marguerite_Frank Frank], who developed its theoretical background,1 and by [http://en.wikipedia.org/wiki/Harry_Markowitz Harry Markowitz], who applied it to portfolio optimization, a subfield of finance. test test test

=Problem formulation=
A general quadratic programming formulation contains a quadratic objective function and linear equality and inequality constraints:2,5,6

<math>\text{min} f(x)=q^{T}x+\frac{1}{2}x^{T}Qx</math> 
<math>s.t. Ax=a</math> 
<math>Bx\le b</math> 
<math>x\ge0</math>

The objective function is arranged such that the vector <math>q</math> contains all of the (singly-differentiated) linear terms and <math>Q</math> contains all of the (twice-differentiated) quadratic terms. Put more simply, <math>Q</math> is the Hessian matrix of the objective function and <math>q</math> is its gradient. By convention, any constants contained in the objective function are left out of the general formulation.6 The one-half in front of the quadratic term is included to remove the coefficient (2) that results from taking the derivative of a second-order polynomial.

As for the constraints, the matrix equation <math>Ax=a</math> contains all of the linear equality constraints, and <math>Bx \le b</math> are the linear inequality constraints.

When there are only inequality constraints (<math>Bx\le b</math>), the Lagrangean is:6 
<math>L(x,\lambda,\mu)=q^{T}x+\frac{1}{2}x^{T}Qx+{\lambda}^T(Ax-a)+{\mu}^T(Bx-b)=0</math> 

==Global solutions==
If the objective function is convex, then any local minimum found is also the sole global minimum. To analyze the function’s convexity, one can compute its Hessian matrix and verify that all eigenvalues are positive, or, equivalently, one can verify that the matrix Q is positive definite.6 This is a sufficient condition, meaning that it is not required to be true in order for a local minimum to be the unique global minimum, but will guarantee this property holds if true.

==KKT conditions==
Solutions can be tested for optimality using Karush-Kuhn-Tucker conditions just as is done for other nonlinear problems:5 

Condition 1: sum of gradients is zero: 
<math>\triangledown L({x}^*,{\lambda}^*,{\mu}^*)=q^{T}+\frac{1}{2}x^{T}Q+{\lambda}^{*T}A+{\mu}^{*T}B</math> 

Condition 2: all constraints satisfied: 
<math>Ax^*-a=0</math> 
<math>Bx^*-b\le0</math>

Condition 3: complementary conditions: 
<math>{\mu}^TBx-b=0</math> 
<math>{x}^{T},{\lambda}^{T},{\mu}^T\ge0</math>

==Solution strategies==
Because quadratic programming problems are a simple form of nonlinear problem, they can be solved in the same manner as other non-linear programming problems.
An unconstrained quadratic programming problem is most straightforward to solve: simply set the derivative (gradient) of the objective function equal to zero and solve.7 More practical (constrained) formulations are more difficult to solve. The typical solution technique when the objective function is strictly convex and there are only equality constraints is the [https://optimization.mccormick.northwestern.edu/index.php?title=Conjugate_gradient_methods&action=edit&redlink=1 conjugate gradient method]. If there are inequality constraints (<math>Bx\le b</math>), then the [https://optimization.mccormick.northwestern.edu/index.php/Interior-point_method_for_NLP interior point] and active set methods are the preferred solution methods. When there is a range on the allowable values of <math>x</math> (in the form <math>x^L\le x\le x^U</math>, which is the case for image and signal processing applications, [https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods trust-region methods] are most frequently used.4 For all convex cases, an NLP solver in the optimization utility GAMS, such as KNITRO, MINOS, or CONOPT, can find solutions for quadratic programming problems.

=Numerical example=
[[File:ChE345 Wiki Mathematica.png|frame|Plot of the unconstrained objective function. Figure generated using Wolfram Mathematica.]]

This example demonstrates how to determine the KKT point of a specific QP problem:

<math>\text{min}</math>
<math>f(x)=3{x_1}^2+{x_2}^2+2{x_1}{x_2}+x_1+6{x_2}+2</math> 
<math>\text{s.t.}</math>
<math>2{x_1}+3{x_2} \ge 4</math> 
<math>{x_1},{x_2} \ge 0</math>

Rewrite the constraints. 
<math>g_1=-2{x_1}-3{x_2}+4\le 0</math> 
<math>g_2=-{x_1} \le 0</math> 
<math>g_3=-{x_2} \le 0</math> 

Construct the gradients. 
<math>\triangledown f= \begin{bmatrix} 6{x_1}+2{x_2}+1 \\ 2{x_1}+2{x_2}+6 \end{bmatrix}, \triangledown {g_1}= \begin{bmatrix} -2 \\ -3 \end{bmatrix}, \triangledown {g_2}= \begin{bmatrix} -1 \\ 0 \end{bmatrix}, \triangledown {g_3}= \begin{bmatrix} 0 \\ -1 \end{bmatrix} </math>

Assuming all constraints are satisfied, set the gradient equal to zero to attempt to find an optima. 
<math>6{x_1}+2{x_2}+1=0</math> 
<math>2{x_1}+2{x_2}+6=0</math> 

<math>{x_1}=\frac{5}{4}</math>,
<math>{x_2}=-\frac{17}{4}</math> 

Make constraints <math>g_1</math> and <math>g_3</math>, which are violated, active. Set both equal to zero. 
<math>{g_1} = -2{x_1}-3{x_2}+4=0</math> 
<math>{g_3} = -{x_2}=0</math> 

Solve the resulting system of equations. 
<math>\triangledown f+ {\mu_1} \triangledown {g_1}+ {\mu_3} \triangledown {g_3} =0</math> 
<math>{g_1}=0</math> 
<math>{g_3}=0</math> 

<math> \begin{bmatrix} 6{x_1}+2{x_2}+1 \\ 2{x_1}+2{x_2}+6 \end{bmatrix} +{\mu_1} \begin{bmatrix} -2 \\ -3 \end{bmatrix} +{\mu_3} \begin{bmatrix} 0 \\ -1 \end{bmatrix} </math> 
<math>-2{x_1}-3{x_2}+4=0</math> 
<math>-{x_2}=0</math> 

Formulating the system as one matrix and row reducing is one of the simplest ways to solve. Doing so yields: 
<math>{x_1}=2, {x_2}=0, {\mu_1}=6.5, {\mu_3}=9.5</math> 

Drop constraint <math>g_3</math> because <math>{\mu_3}</math> is negative and resolve the system. Doing so yields: 
<math>{x_1}=0.5, {x_2}=1, {\mu_1}=3</math> 

Which yields an objective function value of <math>f=11.25</math> 

Verify linear dependence of the gradient: 
<math>\triangledown f+ {\mu_1} \triangledown {g_1}</math> 
<math> \begin{bmatrix} 6 \\ 9 \end{bmatrix} +3 \begin{bmatrix} -2 \\ -3 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} \therefore </math> 

Verify the uniqueness of the solution: 
<math>{\triangledown}^2 f(x)= \begin{bmatrix} 6 & 2 \\ 2 & 1 \end{bmatrix} \rightarrow \begin{bmatrix} 6-\lambda & 2 \\ 2 & 1-\lambda \end{bmatrix} =0 \rightarrow \lambda = 0.298, 6.702</math>

Because both eigenvalues are positive, the Hessian matrix is positive determinant, and this local minimum is the global minimum of the objective function given these constraints. 

=Applications=

A few of the many quadratic programming applications are discussed in more detail and accompanied with general models below, and a list of other areas in which QP is important is presented as well.

*Quadratic knapsack problem (QKP)
In the standard knapsack problem, there are a number of items with different weights and values, and the items are selected based on which combination yields the highest overall value without exceeding the overall weight limit of the knapsack.

In the quadratic knapsack problem, the objective function is quadratic or, more specifically, bilinear, and the constraints are the same as in the typical knapsack problem.8 QKP's are used in designing email servers and to optimize the locations of "nodes" in applications such as positioning transportation hubs like airports and train stations.8 Additionally, the problem can model situations in which a limited number of people are assigned to complete specific objectives that require them to interact.9 One formulation is presented below:8 
<math>\text{max or min}</math>
<math>x^{T}Qx</math> 
<math>Ax \le a</math> 
<math>x \in {B}^{n} </math> 

The quadratic knapsack problem, although it looks very simple, is NP-hard and is thus difficult to solve. To make obtaining solutions easier, these problems are often linearized.8

*Model predictive control
Quadratic programming also has important applications in chemical engineering. Model predictive control (MPC) is a group of algorithms that help manage production in chemical plants by dictating production in each batch. While often formulated as linear programs because the resulting models are more stable, robust and easier to solve, MPC models are sometimes made with quadratic programming.11 As an example of its utility, quadratic programming was used by Di Ruscio in an MPC algorithm for a thermomechanical pulping process, which a method for making paper.11

*Least squares
Least squares regression is one of the most common types of regression, and works by minimizing the sum of the squares of the difference between data points and a proposed fit. Quadratic optimization is one method that can be used to perform a least squares regression and is more flexible than most linear methods. One formulation for a quadratic programming regression model is as follows:3

<math>\text{min}</math>
<math>e'Ie</math> 
<math>e = Y-X \beta</math>

In this model, <math>\beta</math> and <math>e</math> are the unknown regression parameters, <math>I</math> is an identity matrix, and <math>X</math> and <math>Y</math> contain data about the independent and dependent variables respectively.3

*Other applications
Quadratic programming is used in a wide range of applications not touched upon in the sample presented above. Other major areas in which QP's are relied upon include signal and image processing12 and a subfield of optimization called partial differential constrained optimization.3 QP's are also extensively used in finance, as variance, which is used to measure risk, is a function containing squares.13,14,15 More specifically, Markowitz won the 1990 Nobel Prize in Economics for his widely-used model that employs quadratic programming to optimizes the amount of risk taken on based on variances.14

Additionally, [https://optimization.mccormick.northwestern.edu/index.php?title=Sequential_quadratic_programming&action=edit&redlink=1 Sequential quadratic programming], an algorithm for solving more complicated NLP's that uses QP subproblems, is one of the most important applications.

=Conclusion=
Quadratic programming, the problem of optimizing a quadratic function, have been widely used since its development in the 1950s because it is a simple type of non-linear programming that can accurately model many real world systems, notably ones dependent on two variables. Problems formulated this way are straightforward to optimize when the objective function is convex. QP has applications in finance, various types of computer systems, statistics, chemical production, and in algorithms to solve more complex NLP's.

=References=
1. Frank, Marguerite, and Philip Wolfe. "An Algorithm for Quadratic Programming." Naval Research Logistics Quarterly 3 (1956): 95-110. Web. 4 June 2015. 
2. Floudas, Christodoulos A., and V. Visweswaran. "Quadratic Optimization." Nonconvex Optimization and Its Applications, 2 (1995): 217-69. Web. 23 May 2015. 
3. McCarl, Bruce A., Moskowitz, Herbert, and Harley Furtan. "Quadratic Programming Applications." The International Journal of Management Science, 5 (1977): 43-55. 
4. Geletu, Abele. "Quadratic programming problems." Ilmenau University of Technology. Web. 23 May 2015. 
5. Bradley, Hax, and Magnanti. Applied Mathematical Programming. Boston: Addison-Wesley, 1997. 421-40. Web. 23 May 2015. 
6. Jensen, Paul A., and Jonathan F. Bard. "Quadratic Programming." Operations Research Models and Methods. The University of Texas at Austin. Web. 23 May 2015. 
7. Binner, David. "Quadratic programming example - no constraints." Miscellaneous mathematical utilities. AKiTi. Web. 23 May 2015. 
8. Pisinger, David. "The Quadratic Knapsack Problem – A Survey." Discrete Applied Mathematics, 155 (2007): 623 – 648. Web. 23 May 2015. 
9. "Quadratic Multiple Knapsack Problem." Optimization of Complex System. Optiscom Project. 2012. Web. 6 June 2015. 
10. Gallo, G., P. L. Hammer, and B. Simeone. "Quadratic Knapsack Problems." Mathematical Programming 12 (1980): 132-149. Web. 24 May 2015. 
11. Di Ruscio, David. "Model Predictive Control and Optimization." Telemark University College. Mar. 2001. Web. 24 May 2015. 
12. Ma, W. K. "Signal Processing Optimization Techniques." The Chinese University of Hong Kong. Web. 24 May 2015. 
13. Tütüncü, Reha H. "Optimization in Finance." Tokyo Institute of Technology. Spring 2003. Web. 23 May 2015. 
14. Van Slyke, R. "Portfolio Optimization." NYU Polytechnic School of Engineering. 16 Nov. 2007. Web. 24 May 2015. 
15. "Portfolio Optimization." SAS/OR(R) 9.2 User's Guide: Mathematical Programming. SAS Institute. Web. 23 May 2015.