Dynamic Programming 1 - Discrete Dynamic Programming

z Dynamic Programming 1 A warm-up example z Suppose that there are 20 matches on a table, and the person who picks up the last match wins. At each alternating turn, my opponent or I can pick up 1 or 2 matches. Assuming that I go first, how can I be sure of winning the game? z (Play with partner, and then discuss). 2 20 Matches z Choose a person to go first. z Alternate in eliminating 1 or 2 matches. z The person who takes the last match wins. 3 20 Matches strategy z What is the optimal strategy? 4 An Example for Dynamic Programming: 20 matches Version 2 z Choose a person to go first. z Alternate in eliminating 1 or 2 or 6 matches. z The person who takes the last match wins. 5 20 Matches 6 Winning and losing positions (in the game in 20 matches version 2) z Suppose you have k matches left. Identify whether you have a Winning strategy (assuming your opponent plays optimally) or whether you will Lose. 1 W 2 W 3 L 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 7 Decisions with 4 or 5 matches left. Your opponent is Y. Take 1 You win. 4 Take 2 3 Y loses 2 Y wins Take 6 Take 1 You win. 5 Take 2 Take 6 4 Y wins 3 Y loses 8 Decisions with 6 or 7 matches left. Take 1 You win. 6 Take 2 Take 6 5 Y wins. f(5) = W 4 Y wins. f(4) = W 0 Y loses Take 1 You lose. 7 Take 2 Take 6 6 Y wins. f(6) = W 5 Y wins. f(5) = W 1 Y wins. f(1) = W 9 Decisions with n matches left. Take 1 n-1 f(n-1) f(n) n Take 2 Take 6 n-2 f(n-2) n-6 f(n-6) The Dynamic Programming Recursion f(n) = W if f(n-1) = L or f(n-2) = L or f(n-6) = L; and f(n) = L if f(n-1) = f(n-2) = f(n-6) = W. 10 Aspects of Dynamic Programming z Recall that f(n) = W or L. z BEGIN WITH THE END IN MIND. – In this game, we start with 20 matches. But we first determine f(n) for n near near the end of the game, when there are 1 or 2 or 3 matches left. z THE RECURSION – We determine f(n) in terms of previously computed values. We determine f(7) in terms of f(1) to f(6). We determine f(8) in terms of f(1) to f(7). etc. 11 Dynamic programming Terminology Take 1 n-1 f(n-1) f(n) n Take 2 Take 6 n The state n-2 f(n-2) n-6 f(n-6) f(n) The optimal value function. The state describes all that is needed for making a decision. In this case, all that one needs to know the number of matches that remains. The optimal value function f(n) describes the value from making the optimal decision while in state n. 12 Dynamic Programming Recursion Take 1 n-1 f(n-1) f(n) n Take 2 Take 6 n-2 f(n-2) n-6 f(n-6) The Dynamic Programming Recursion f(n) = W if f(n-1) = L or f(n-2) = L or f(n-6) = L; f(n) = L if f(n-1) = f(n-2) = f(n-6) = W. The Dynamic Programming Recursion is the method of computing the optimal value function in state n from the optimal values for previous states. 13 Boundary Conditions z In this game, we start with 20 matches. But we first determine f(n) at the end of the game, when there are 1 or 2 or 3 matches left. Boundary conditions: the values of f(n) that can be computed directly without need of recursion. 14 Principle of optimality Take 1 n-1 f(n-1) f(n) n Take 2 Take 6 n-2 f(n-2) n-6 f(n-6) The Principle of Optimality. The optimum decision to do at state n is to make a decision, and then proceed optimally from that point on. 15 The Steps of the Dynamic Program Step 1. Determine the states. Step 2. Determine the boundary conditions for the optimal value function. f(0) = L Step 3. Write the dynamic programming recursion. Take 1 n-1 f(n-1) f(n) n Take 2 Take 6 n-2 f(n-2) n-6 f(n-6) f(n) = W if f(n-1) = L or f(n-2) = L or f(n-6) = L; f(n) = L otherwise. 16 Running the Recursion Step 4. Use the recursion to solve for all values of the optimal value function. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 Who sees the pattern determining the losing positions? 17 The same table 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 18 Finding the shortest path from node 1 to all other nodes in an acyclic network. 5 2 12 9 6 1 3 16 13 10 7 4 17 14 11 8 19 18 15 19 The recursion. Computing d(10) d(6) = 10 6 d(j) is the shortest length of a path from node 1 to node j. 10 6 precedes 10 10 7 9 d(7) = 6 d(6) + 10 10 7 precedes 10 d(7) + 9 d(10) = min { 10 + 10, 6 + 9 } = 15 In general, d(j) = min { d(i) + cij : i < j } 20 Shortest Paths z Find the shortest path from node 1 to each other node, in order. – What is the shortest path from node 1 to node 2, 3, 4, … ? – Determine these values one at a time. 21 Finding the shortest path to node n from all other nodes in an acyclic network. 5 2 12 9 6 1 3 16 13 10 7 4 17 14 11 8 19 18 15 22 Shortest Paths z Find the shortest path to node 19 from each node in order. – What is the shortest path to node 19 from node 18, 17, 16….? – Determine these values one at a time. 23 Shortest Paths z What is the number of paths from node 1 to node j for each j = 1 to 19. f(10) = 4 f(j) is the number of paths from node 1 to node j. 10 10 10 precedes 14 14 9 11 f(11) = 3 4 14 11 precedes 14 f(14) = f(10) + f(11) = 7. 3 24 Dynamic Programming with Stages z These are problems with K decision stages. z The boundary conditions are usually the decisions in Stage K. z The recursion determines decisions in stage k by using optimal values from stage k+1. z Decisions have both an associated stage and an associated state. 25 Optimal Capacity Expansion: What is the least cost way of building plants? Year Cum. Demand Incremental Cost per at end of year plant in $ millions 2005 1 2 2006 2 4 2007 4 6 2008 6 5 2009 7 3 2010 8 0 Each plant costs $50 million plus the incremental cost. Cost of $15 million in any year in which a plant is built. At most 3 plants a year can be built 26 Step 1A. Determine Stages z Often in dynamic programs it is obvious how many decisions need to be made. z Stage 1: first decision to be made – How many plants to build in 2005 z Stage 2: second decision to be made – How many plants to build in 2006 … z Stage 6: sixth decision to be made – how many plants to build in 2010 27 Step 1B. Determine States for each Stage z Stage 1. – State = 0. No plants have been built yet z Stage 2. – State = 1, 2, or 3. (State is the number of plants built in previous stages.) … z Stage k – State i means that i plants have been built in stages 1 to k-1. f(Y, j) is the minimum cost for years Y to K of starting in year Y with j plants already built. 28 Step 2C. An example of the recursion. Build 0 What is f(2006, 1) ? 0 + f(2007, 1) Build 1 15 + 4 + f(2007, 2) (2006, 1) Build 2 Build 3 15 + 8 + f(2007, 3) 15 + 12 + f(2007, 4) Let c(Y, j) be the cost of building j plants in year Y, excluding the $50 million per plant. f(2006, 1) = min{c(2006, k) + f(2007, 1+k) : k = 0 to 3 }. 29 Dynamic Program. Start in the last stage and work backwards to the first stage. Year Cum. Demand Incremental Cost per at end of year plant in $ millions 2009 7 -- 2010 8 0 (2010, 7) f(2010, 7) = 15. Build a plant. (2010, 8) f(2010, 8) = 0. Do nothing. We will consider only incremental costs per plant. The real cost is 8 x $50 million higher. 30 Dynamic Program. Start in the last stage and work backwards to the first stage. Year Cum. Demand Incremental Cost per at end of year plant in $ millions 2008 6 -- 2009 7 3 Build 0 (2009, 6) 0+ f(2010, 6) Build 1 15 + 3 + f(2010, 7) Build 2 15 + 6 + f(2010, 8) 31 Exercise. Compute f(2008, 7), f(2008, 8) Build 0 0+ f(2010, 7) (2009, 7) Build 1 15 + 3 + f(2010, 8) (2009, 8) Build 0 0 + f(2010, 8) 32 Exercise. Compute f(2007, j) for j = 4 to 8. Year Cum. Demand Incremental Cost per plant in $ millions 2007 4 -- 2008 6 5 (2008, 4) f(2009, 6) = 21 f(2009, 7) = 15 (2008, 5) f(2009, 8) = 0 (2008, 6) c(2008, 0) = 0 (2008, 7) c(2008, 1) = 20 c(2008, 2) = 25 (2008, 8) c(2008, 3) = 30 33 8 0 0 0 7 15 15 15 21 6 21 21 5 30 30 4 45 45 3 48 54 2 57 63 1 72 0 69 2005 2006 2007 2008 2009 2010 34 Dynamic Programming in General z Break up a complex decision problem into a sequence of smaller decision subproblems. z Stages: one solves decision problems one “stage” at a time. Stages often can be thought of as “time” in most instances. – Not every DP has stages 35 Dynamic Programming in General z States: The information at a stage that is needed to make the decision. – match problem: “state” is the number of matches left – Capacity expansion: state is number of plants that are already built at the stage z At each state-stage, there are one or more decisions. The DP recursion determines the best decision. – match problem: how many matches to remove – Capacity expansion: how many plants to build. 36 Principle of Optimality z Any optimal policy has the property that whatever the current state and decision, the remaining decisions must constitute an optimal policy with regard to the state resulting from the current decision. (As formulated by Richard Bellman.) z Whatever node j is selected, the remaining path from j to the end is the shortest path starting at j. 37 Backwards recursion z Determine boundary conditions for stage K. Determine values for other stages using recursion. z In the match examples, determine f(n) from f(k) for k < n. z Next lecture: more examples of dynamic programming. 38 Summary for Dynamic Programming z States and stages and decisions z Recursion z Principle of optimality z useful in a wide range of situations – games – shortest paths – capacity expansion – and much much more 39