Difference between revisions of "Eight step procedures"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 7: Line 7:
  
 
===Methodology===
 
===Methodology===
To solve a problem using the 8-step procedure, one must follow the following steps: <br />
+
To solve a problem using the 8-step procedure, one must use the following steps: <br />
 
<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 <math>n</math>. <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 <math>s</math>. We set <math>C</math> equal to the maximum value of <math>s</math>. <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>  
+
<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 <math>s</math>, and each stage, or <math>n</math>. This can also be called <math>f^{*}_{n}(s)</math> <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 <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 />
+
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 <math>j</math> items for the remaining capacity <math>s</math> for items <math>n</math>. 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 <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> <br />
+
<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> <br />
 
<br />
 
<br />
 +
 
'''Step 7: Compute the optimal value from the bottom-up''' <br />
 
'''Step 7: Compute the optimal value from the bottom-up''' <br />
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. <br />
+
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. <br />
 
<br />
 
<br />
 +
 
'''Step 8: Arrive at the optimal solution''' <br />
 
'''Step 8: Arrive at the optimal solution''' <br />
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>. <br />
+
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>. <br />
  
 
=Numerical Example=
 
=Numerical Example=

Revision as of 20:34, 20 November 2020

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 .

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:


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

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:


Step 7: Compute the optimal value from the bottom-up
In this step, a table is made containing all , , and optimal values for all variables. This step can be done manually or by using programming.

Step 8: Arrive at the optimal solution
Once the value for 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 , calculate our remaining space , and use that value to arrive at an optimal value for all .

Numerical Example

Applications

Conclusion

References