Dynamic Programming - Constraints

 0 Hello, I have a question regarding Dynamic Programming. Do you know if it is allowed to introduce global constraints next to the termination constraints? Or am I supposed to shift all constraints into the state variable. But does this approach enlarge the state space? Example: Suppose I have an item stock 'S' and need to plan for the following how many items I should buy to refill my stock again to K items. The day is divided into T=4 phases (stages of the DP) and a price factor differs. For each phase there is a budget restriction of 'y_t' dollars. In the end of the planning, I am supposed to have S=K items again. The costs are v_t * x_t where x_t denotes the amount of items to buy and v_t just a constant pricing factor. Try to minimize the costs My approach is the following: S_t - the current stock amount at phase t t - current phase (S_t,t) - state variable My DP recurrence would be like C(S_t, t) = min(v_t*x_t + C(S_t +x_t, t+1)) where S_0 = 0 and C(S_t,T+1) = 0 How would you add the budget constraint? Can I add this as a constraint like in a Linear Program? Does a constraint eliminate some states? Thank you. asked 21 Jul '16, 10:02 Thomas 23●6 accept rate: 0%

 0 The budget (specifically, the remaining budget) becomes part of the state definition as the stock level is. That is, including the additional constraint enlarges the state space rather than reducing it. Best regards, Jordi answered 02 Aug '16, 11:10 JordiPereira... 26●1 accept rate: 100% Dear Jordi, thank you very much for your answer. (08 Aug '16, 03:29) Thomas
 toggle preview community wiki

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×28
×27
×3

Asked: 21 Jul '16, 10:02

Seen: 628 times

Last updated: 08 Aug '16, 03:29

Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.