Eight step procedures: Difference between revisions

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 10: Line 10:
<br />
<br />
'''Step 1: Specify the stages of the problem''' <br />
'''Step 1: Specify the stages of the problem''' <br />
• The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable n. <br />
• The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable <math>n</math>. <br />
<br />
<br />
'''Step 2: Specify the states for each stage''' <br />
'''Step 2: Specify the states for each stage''' <br />
• 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. <br />
• 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>. <br />
<br />
<br />
'''Step 3: Specify the allowable actions for each state in each stage''' <br />
'''Step 3: Specify the allowable actions for each state in each stage''' <br />
• This can be defined as: <br />
• This can be defined as: <br />
o <math>  
o <math>  
U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]]} \right \rfloor \right \}
    U_{n}(s)\, or\, j\, =\, 0,1,...,min\left \{ a[n], \left \lfloor \frac{s}{w[n]} \right \rfloor \right \}
         </math> <br />
         </math> <br />
<br />
<br />
'''Step 4: Describe the optimization function using an English-language description.''' <br />
'''Step 4: Describe the optimization function using an English-language description.''' <br />
• 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) <br />
• 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> <br />
<br />
<br />
'''Step 5: Define the boundary conditions''' <br />
'''Step 5: Define the boundary conditions''' <br />
• 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 <br />
• 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> <br />
<br />
<br />
'''Step 6: Define the recurrence relation''' <br />
'''Step 6: Define the recurrence relation''' <br />
• 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: <br />
• 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: <br />
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])} <br />
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])} <br />
<br />
<br />

Revision as of 19:32, 20 November 2020

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 .

Step 2: Specify the states for each stage
• The states of a problem are defined as the knowledge necessary to make a decision, or . We set equal to the maximum value of .

Step 3: Specify the allowable actions for each state in each stage
• This can be defined as:
o

Step 4: Describe the optimization function using an English-language description.
• In this sentence, we describe the optimization function for each state, or , and each stage, or . This can also be called

Step 5: Define the boundary conditions
• This helps create a starting point to finding a solution to the problem. First, we set for all values of . Here, we can note that Failed to parse (syntax error): {\displaystyle s = 0,…,C}

Step 6: Define the recurrence relation
• During this step, we make an allowable decision involving items for the remaining capacity for items . 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