Questions Tagged With dynamic-programminghttp://www.or-exchange.com/tags/dynamic-programming/?type=rssquestions tagged <span class="tag">dynamic-programming</span>enSat, 28 Oct 2017 12:53:07 -0400Optimality condition for dynamic programminghttp://www.or-exchange.com/questions/15119/optimality-condition-for-dynamic-programming<p>Dear all</p>
<p>Can I know if dynamic programming can solve any optimization problem and if the obtained solution from DP is always optimal? If not, in what cases DP is not able to find the optimal solution?</p>
<p>Thanks</p>Amin-ShSat, 28 Oct 2017 12:53:07 -0400http://www.or-exchange.com/questions/15119/optimality-condition-for-dynamic-programmingdynamic-programmingWhat's the difference between Approximate Dynamic Programming (ADP) and RL/QL?http://www.or-exchange.com/questions/15086/whats-the-difference-between-approximate-dynamic-programming-adp-and-rlql<p>Dear all,
I am confused about the difference between Approximate Dynamic Programming and Reinforcement Learning (such as QL) or approximated RL?
you know, somebody told me that they are the same but RL/QL is in the context of computer science and ADP is in the context of operational research and engineering.</p>
<p>also, I've heard policy iteration and policy search keywords. are the different?</p>Mahdi MassahiMon, 16 Oct 2017 04:09:18 -0400http://www.or-exchange.com/questions/15086/whats-the-difference-between-approximate-dynamic-programming-adp-and-rlqldynamic-programmingmachine-learningUse Dynamic Programming to maximise a nonlinear objective functionhttp://www.or-exchange.com/questions/13618/use-dynamic-programming-to-maximise-a-nonlinear-objective-function<p>Using dynamic programming, </p>
<blockquote>
<p>Maximise $$z = x_1(1-x_2)x_3$$</p>
<p>subject to</p>
<p>$$x_1 - x_2 + x_3 \le 1$$</p>
<p>$$x_1, x_2, x_3 \ge 0$$</p>
</blockquote>
<p>Here's the outline of my solution 1. How is it?</p>
<p>Let \(y_2=1-x_2\).</p>
<p>Also let's change the other x's to y's.</p>
<p>Then we have</p>
<blockquote>
<p>Maximise $$z = y_1y_2y_3$$</p>
<p>subject to</p>
<p>$$y_1 + y_2 + y_3 \le 2$$</p>
<p>$$y_1, \color{red}{y_2,} y_3 \ge 0$$</p>
<p>$$y_2 \le 1$$</p>
</blockquote>
<p>We can deduce that \(y_2 \ge 0\), but do we need to? In this case I guess not, but in general?</p>
<p>If we solve this problem by dynamic programming, then we get the same answer as in Wolfram.</p>
<hr>
<p>Here's the outline of my solution 2. How is it?</p>
<p>Stage 3: Max \(x_3\)</p>
<p>$$f_3^{op}(s_3) = \max_{0 \le x_3 \le s_3} {x_3}$$</p>
<p>Stage 2: Min \(x_2\)</p>
<p>$$f_2^{op}(s_2) = \min_{0 \le x_2 \le s_2} {(1-x_2) f_3^{op}(s_2+x_2)}$$</p>
<p>Stage 1: Max \(x_1\)</p>
<p>$$f_1^{op}(s_1) = \max_{0 \le x_1 \le s_1} {(x_1) f_2^{op}(s_1 - x_1)}$$</p>
<p>where $$s_1 = 1$$</p>
<p>After we solve $$x_1^{op} = 2/3$$</p>
<p>we get</p>
<p>$$x_2^{op} = s_2 = s_1 - x_1 = 1 - 2/3 = 1/3$$</p>
<p>$$x_3^{op} = s_2 + x_2 = 1/3 + 1/3 = 2/3$$</p>
<hr>
<ol>
<li>
<p>I think we have to minimise \(x_2\) and maximise everything else because the \(x_2\) part we want to maximise is \(1-x_2\), which would be done by minimising \(x_2\). Is that right?</p>
</li>
<li>
<p>Why should we still have \(x_2 \color{red}{\le s_2}\)? My solution (whose answer agrees with Wolfram) seems to rely on \(x_2^{*} = s_2\). I was thinking that the negative coefficient of \(x_2\) in the constraint removes that. If not, what is the role of the negative coefficient of \(x_2\) (in the constraint, not objective function)? Just the \(s_2 \color{red}{+} x_2\)?</p>
</li>
</ol>BCLCFri, 22 Apr 2016 06:38:43 -0400http://www.or-exchange.com/questions/13618/use-dynamic-programming-to-maximise-a-nonlinear-objective-functiondynamic-programmingoptimizationnonlinear-optimizationScenario generation approaches for multi-stage stochastic integer program with recoursehttp://www.or-exchange.com/questions/13031/scenario-generation-approaches-for-multi-stage-stochastic-integer-program-with-recourse<p>I am very new to the field and I was trying to understand the differences between approaches for generating scenarios in SP. From what I have seen, people have mostly focused on moment matching methods followed by some discretization to reduce the scenario space. However, how does this compare to a time-series approach where one first makes a prediction for each action/solution in the future and then optimizes based on this (in an MPC way of solving the problem)?</p>
<p>I am a practitioner so I would be very grateful if someone can give some practical advice on this.</p>lstavrWed, 25 Nov 2015 05:22:47 -0500http://www.or-exchange.com/questions/13031/scenario-generation-approaches-for-multi-stage-stochastic-integer-program-with-recoursedynamic-programmingstochasticscenariointeger-programmingDynamic programming for ILPhttp://www.or-exchange.com/questions/11819/dynamic-programming-for-ilp<p>How can we use Dynamic programming technique to solve a ILP/LP? Any book or resources?? thanks </p>cbotMon, 30 Mar 2015 03:28:04 -0400http://www.or-exchange.com/questions/11819/dynamic-programming-for-ilpdynamic-programminginteger-programmingMaximize profit with dynamic programminghttp://www.or-exchange.com/questions/11812/maximize-profit-with-dynamic-programming<p>I have 3 tablesâ€¦</p>
<pre><code>quantity, expense, profit
1, 2312, 3212
</code></pre>
<p>All equal structure but with different values and different number of rows.</p>
<p>I want to write a recursive function describing the optimal choices of quantities in order to maximize my profit.</p>
<p>I have a given amount to spend and the total expenses can't exceed this.</p>
<p>Besides, I use the notation that p_nj should the profit in table n and quantity j and c_{nj} should express the cost of choosing quantity j in table n.</p>
<p>I think it's something like</p>
<p>f_n(A) = max{ p_nj + f_{n+1}(A-c_nj) }</p>
<p>where A is the amount I can invest.</p>
<p>My intuition is that I'm adding the profit p_nj for each iteration and subtracting the cost from the total available amount (A-c_nj).</p>
<p>I don't think it's correct but I guess it's something like that. How can I iterate through all the three different tables with recursion?</p>OrnSat, 28 Mar 2015 10:23:11 -0400http://www.or-exchange.com/questions/11812/maximize-profit-with-dynamic-programmingdynamic-programmingrecursive-equationoptimizationMultiple knapsack problem using dynamic programminghttp://www.or-exchange.com/questions/10703/multiple-knapsack-problem-using-dynamic-programming<p>Hi,</p>
<p>I want to know if I can solve a multiple knapsack problem using dynamic programming or not.taking a very small example of 2 knapscks, can I solve it. I am not able to think of recurrence for the problem. I searched a lot for this but could get research papers on how relaxations can solve it using branch and bound techniques. </p>
<p>I dont understand, how this takes exponenitial time and recurrence becomes intractable. Can someone help to get the recurrence for multiple knapsack?</p>nickyThu, 20 Nov 2014 03:30:34 -0500http://www.or-exchange.com/questions/10703/multiple-knapsack-problem-using-dynamic-programmingdynamic-programmingWhat is a meaning of dynamic ?http://www.or-exchange.com/questions/4423/what-is-a-meaning-of-dynamic<p>What is the importance of dynamic programming in OR?</p>
<p>And is it different from time series analysis and planning ? </p>
<p>To me the word "dynamic" makes no sense about what exactly this programming means. </p>
<p>I request all the members to kindly clarify my confusion.</p>
<p>thank you so much in advance</p>RamSun, 08 Jan 2012 10:49:07 -0500http://www.or-exchange.com/questions/4423/what-is-a-meaning-of-dynamicdynamic-programmingoperations-researchmathematical-modeling[HOMEWORK] a dynamic programming example ?http://www.or-exchange.com/questions/3953/homework-a-dynamic-programming-example<p>Hi everyone, I have been trying to solve a problem for some time but not succesful yet.the question is the following;</p>
<p>A technological store face with a demand of 100 tv per month. This demand is not random, it is uniform in the month, and must be satisfied. Store manager orders televisions collectively from the main dealer, each tv costs 1000$ , and shipping cost is 1250$. the cost of keeping a tv for a month is 100$. What is the amount of order for minimum cost ?</p>
<p>I tried to solve it by the following:
let stage j = month j , </p>
<p>state u = number of tvs in store in the beginning of stage j and </p>
<p>I(u)= cost of keeping u number of tvs in store.</p>
<p>Define x = number of tvs manager orders </p>
<p>then if M_j(u) = minimum cost of process starting from stage j with state u</p>
<p>M_j(u) = min {I(u) + 1000x + 1250.D_x + M_(j+1) (u+x-100) } </p>
<p>where min is taken over possible x values. </p>
<p>D_x is a variable that is 1 if x is positive and 0 for x=0.</p>
<p>question says nothing about the capacity of the store?</p>
<p>the demand must be satisfied so we can say u+x >= 100</p>
<p>well I'm stuck here..</p>n_s_rFri, 04 Nov 2011 09:08:09 -0400http://www.or-exchange.com/questions/3953/homework-a-dynamic-programming-exampledynamic-programminghomework