Difference between revisions of "Eight step procedures"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
m
Line 7: Line 7:
  
 
===Definition===
 
===Definition===
To solve a problem using the 8-step procedure, one must follow the following steps:
+
To solve a problem using the 8-step procedure, one must follow the following steps: <br />
 
Step 1: Specify the stages of the problem
 
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.
 
• The stages of a dynamic programming problem can be defined as points where decisions are made. These are often denoted with the variable n.
Line 24: Line 24:
 
Step 7: Compute the optimal value from the bottom-up
 
Step 7: Compute the optimal value from the bottom-up
 
• In this step, a table is made
 
• In this step, a table is made
 
  
 
=Numerical Example=
 
=Numerical Example=

Revision as of 17:21, 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 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 Un(s) or j = 0,1,…,min{a[n], floor(s/w[n])} 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