Dynamic ProgrammingThe general ideaDynamic programming is essentially a recursive algorithm, which is oftenuseful if the problem can be represented as a parametrized set of subproblems,such that each subproblem is reducible to others with smaller parameters.The formulation can yield an efficient algorithm if the following two condi-tions are satisfied:• The number of different subproblems is not too large (does not growexponentially).• The iterative reductions finally reduce the task to some initial cases forwhich the solution is already known or directly computable.We show the principle through an example.ExampleA telecom company wants to create an extension plan for its network, year byyear over a time horizon of T years, such that the network will have enoughcapacity to keep up with the growing demand in every year, and the totalcost is minimum. The following information is available as input:• cost[t, k] is the known cost we have to pay if in year t we extend thecapacity by k units (k is assumed to be an integer).• demand[t] is the known capacity demand in year t.Goal: find an extension plan by specifying how much new capacity has tobe bought in each year, such that in every year the accumulated capacitysatisfies the demand, and the total cost is minimum.SolutionFor easy description, let us use the following notations:• k will denote the amount of capacity.• The time (year) will be denoted by t. This variable runs over a timehorizon T, that is t = 1, . . . , T.• cost[t, k] denotes the known cost we have to pay if in year t we buy kunits of capacity.• demand[t] denotes the known demand for year t.• Let A[t, k] be the minimum achievable accumulated cost of a decisionsequence up to the end of year t, if it achieves a total capacity of k.Let us now formulate the recursive algorithm:The optimal accumulated cost up to the end of year t with accumulatedcapacity k can be obtained recursively as follows.If the last amount of capacity we have bought is r and now we have altogetherk, then by the end of the previous year we must have had k −r. If we alreadyknow the optimum cost up to year t − 1 for all possible values of the capacity,then we can express the updated total cost asA[t, k] = A[t − 1, k − r] + cost[t, r].Since r is a free parameter, the updated optimum will be the minimum withrespect to r:A[t, k] = minrA[t − 1, k − r] + cost[t, r]where the minimum is taken over all possible values of r ≤ k that correspondsto the possible amounts of capacity we can buy.Of course, k capacity in year t is acceptable only if k ≥ demand[t], that is,the accumulated capacity satisfies the demand. To exclude those values thatviolate this requirement, we can prevent using them by assigning infinite cost(or some very large number) to these cases. Thus, the final recursice formulawill beA[t, k] =∞ if k < demand[t]minrA[t − 1, k − r] + cost[t, r] if k ≥ demand[t]We can apply the above recursive formula whenever t > 1. But how dowe handle the first year, that is, how do we start the recursion? Whent = 1, there is no previosly accumulated capacity yet, so then we simply takeA[1, k] = cost[1, k] for every k.In this way the A[t, k] values can be computed recursively for t = 1, . . . , T.Having done the iteration, the optimum cost will beOP T COST = mink≥demand[T ]A[T, k]Comment:This systematic solution solves the problem in time bounded by a polynomialof the time horizon length (T ) and the maximum value of k (capacity) asopposed to the full decision tree where the running time would grow
View Full Document
Unlocking...