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's gravatar image

accept rate: 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

JordiPereiraGude's gravatar image

accept rate: 100%

Dear Jordi, thank you very much for your answer.

(08 Aug '16, 03:29) Thomas
Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 21 Jul '16, 10:02

Seen: 628 times

Last updated: 08 Aug '16, 03:29

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