The Radix Heap Algorithm

Shortest Paths 2: Application to lot-sizing R-Heaps Application 19.19. Dynamic Lot Sizing (1) ‹ ‹ ‹ ‹ K periods of demand for a product. The demand is dj in period j. Assume that dj > 0 for j = 1 to K. Cost of producing pj units in period j: aj + bjpj hj : unit cost of carrying inventory from period j Question: what is the minimum cost way of meeting demand? Application 19.19. Dynamic Lot Sizing (1) 0 1 -d1 2 -d2 D 3 4 K-1 K -d3 -d4 -dK-1 -dK Flow on arc (0, j): amount produced in period j Flow on arc (j, j+1): amount carried in inventory from period j Lemma: There is production in period j or there is inventory carried over from period j-1, but not both. Lemma: There is production in period j or there is inventory carried over from period j-1, but not both. Suppose now that there is inventory from period j-1 and production in period j. Let period i be the last period in which there was production prior to period j, e.g., j = 7 and i = 4. Claim: There is inventory stored in periods i, i+1, …, j-1 0 4 -d4 5 -d5 D 6 7 K-1 K -d6 -d7 -dK-1 -dK 0 D 4 5 6 7 K-1 -d4 -d5 -d6 -d7 -dK-1 K -dK Thus there is a cycle C with positive flow. C = 0-4-5-6-7-0. Let x07 be the flow in (0,7). The cost of sending ∆ units of flow around C is linear (ignoring the fixed charge for production). Let Q = b4 + h4 + h5 + h6 – b7. ‹ If Q < 0, then the solution can be improved by sending a unit of flow around C. ‹ If Q > 0, then the solution can be improved by decreasing flow in C by a little. ‹ If Q = 0, then the solution can be improved by increasing flow around C by x07 units (and thus eliminating the fixed cost a7). ‹ This contradiction establishes the lemma. Corollary. Production in period i satisfies demands exactly in periods i, i+1, …, j-1 for some j. Consider 2 consecutive production periods i and j. Then production in period i must meet demands in i+1 to j-1. 0 i -di i+1 -di+1 D i+2 -di+2 j-1 -dj-1 j -dj Let cij be the (total) cost of this flow. cij = ai + bi(di + di+1 + … + dj-1) + hi(di+1 + di+2 + … + dj-1) + hi+1(di+2 + di+3 + … + dj-1) + … hj-2(dj-1) Let cij be the cost of producing in period i to meet demands in periods i, i+1, …, j-1 (including cost of inventory). Create a graph on nodes 1 to K+1, where the cost of (i,j) is cij. 1 2 3 4 K K+1 Each path from 1 to K+1 gives a production and inventory schedule. The cost of the path is the cost of the schedule. 1 6 8 11 K+1 Interpretation: produce in periods 1, 6, 8 and 11. Conclusion: The minimum cost path from node 1 to node K+1 gives the minimum cost lot-sizing solution. Review of the Bucket Implementation 2 4 2 4 2 0 Potential Bottleneck: Scanning empty buckets. 2 2 1 1 3 6 4 2 3 3 5 4 0 1 2 2 3 4 3 5 6 7 Using a bucket with a larger “width” 22 45 2 4 22 29 0 26 14 1 3 6 27 41 31 3 41 0-9 10 19 5 20 - 30 - 40 29 39 49 2 50 59 3 width = 10 If costs are larger, one can make larger buckets. But then, how does one do a “find min?” 60 69 70 79 A comment on buckets ‹ The bucket implementation z Finding the first node in a bucket takes O(1) time z If the buckets have width 1, then each node has minimum label z If the buckets have width > 1, then we need to find the node in the bucket with min d(j). z Finding the node in the bucket with min d(j) can take O(n) time if there are a fraction of n nodes in the bucket. A Special Purpose Data Structure ‹ RADIX HEAP: a specialized implementation of priority queues for the shortest path problem. ‹ A USEFUL PROPERTY (of Dijkstra's algorithm): The minimum temporary label d( ) is monotonically non-decreasing. The algorithm labels node in order of increasing distance from the origin. ‹ C = 1 + max length of an arc Radix Heap Example Buckets: 5 2 bucket sizes grow exponentially ranges change dynamically 15 13 6 20 8 9 3 1 2 1 0 0 4 2 3 4 7 8 15 16 31 5 32 63 Radix Heap Animation Some General Comments ‹ The Update Step seems fairly routine, but reinserting a node can take O(K) steps, where K is the number of buckets. ‹ The Find Min Step is complicated, and it seems more time intensive than anything else we have looked at. It looks like it could be O(n) per find min and thus O(n2) in total. ‹ Remarkable Fact. A relatively elementary implementation of this algorithm leads to an O(m + n log C) algorithm. On the number of buckets ‹ Let K = Number of Buckets. z Running time is O(m + nK). z The initial widths of the buckets are 1, 1, 2, 4, 8, …, 2K-2 z K =2+ ⎡ log (C+1) ⎤ „ z Note that Bucket K has width at least C Further improvements are possible. Algorithm Outline ‹ Initialization: z Initializes the buckets with bucket ranges 0, 1, 2-3, 4-7, 8-15, etc; z Initializes d( ); z places node j in the bucket whose range contains d(j); ‹ Update(i) z d(j) = min(d(j), d(i) + cij) for (i,j) ∈ A(i) z Reinsert(j) if necessary: that is move it to the bucket whose range contains d(j); Algorithm outline (continued) ‹ Select min z scans buckets to find the min non-empty bucket, say bucket B (e.g., B = 4) z scans B to find d*, the min temporary label z redistributes the ranges in bucket B to buckets 1 to B-1, starting with value d* z reinserts nodes that were in bucket B into the previous 1 to B-1 so that node j is in the bucket whose range contains d(j) z selects a node from Bucket 1. ‹ Additional issue to address later: why we have enough buckets. Algorithm running time: Initialization ‹ ‹ ‹ Initializes the buckets with bucket ranges 0, 1, 2-3, 47, 8-15, etc; z O(K) steps Initializes d( ); z O(n) places node j in the bucket whose range contains d(j); z O(n) assuming that d(1) = 0 and d(j) = ∞ for j > 1. Initialization step ∞ Initialize distance labels 2 13 2 6 Insert nodes into buckets. 1 15 ∞ 20 0 1 4 0 1 Initialize buckets and their ranges. 0 ∞ 5 8 9 3 5 ∞ 2 3 4 7 8 15 ∞ 16 31 32 63 ∞ 2 3 4 5 6 Update(i) Analysis ‹ d(j) = min(d(j), d(i) + cij) for (i,j) ∈ A(i) z O(m) time in total ‹ Reinsert(j) if necessary: that is move it to the bucket whose range contains d(j); z Potentially O(K) per scan of each arc. z Improved running time comes from a “global perspective” More on update Example: d(9) =57 Case 1: d(9) is decreased to 37 Update takes time O(m + nK) Node 9 stays in bucket 7 O(1) time for the update Each node j can shift left K-1 buckets, and determining the buckets takes O(K) additional steps. Case 2: d(9) is decreased to 23 Node 9 moves to bucket 3 4 steps to find the bucket 18 19 20 21 22 25 26 31 32 63 9 1 2 3 4 5 6 7 Select Min (step 1) ‹ scans buckets to find the min non-empty bucket, say bucket B (e.g., B = 4) z O(K) steps per find min, z O(nK) steps in total 0 9 13 1 10 14 11 2 3 12 15 13 ∅ 15 8 ∅ 15 16 31 6 8 32 63 Select Min (step 3) ‹ ‹ scans B to find d*, the min temporary label z will be analyzed later redistributes the ranges in bucket B to buckets 1 to B-1, starting with value d* z O(K) steps per find min, z O(nK) steps in total z e.g, suppose d(6) = 19, d(8) = 25; 0 9 13 19 1 10 14 20 2 11 21 3 12 15 22 13 ∅ 23 15 26 8 ∅ 27 15 31 16 ∅ 31 6 8 32 63 Select Min (steps 4, 5) ‹ reinserts nodes that were in bucket B into the previous 1 to B-1 so that node j is in the bucket whose range contains d(j) z O(K) over all select min for each node j z O(nK) in total ‹selects a node from Bucket 1. zO(1) per select min zO(n) in total 0 9 13 19 6 1 10 14 20 2 11 21 3 12 15 22 13 ∅ 23 15 26 8 ∅ 27 15 31 8 d(6) = 19, d(8) = 25 16 ∅ 31 6 8 32 63 Select Min (Step 2): a dominance argument ‹ scans B to find d*, the min temporary label z Suppose that there are n’ nodes in bucket B. z O(n’) steps to determine d* z But the n’ nodes then are reinserted z at least n’ steps to reinsert these nodes Conclusion. The running time for Step 3 is O( running time for reinsertion ) = O(nK) 0 9 13 19 1 10 14 20 2 11 21 3 12 15 22 13 ∅ 23 15 26 8 ∅ 27 15 31 16 ∅ 31 6 8 B 32 63 Summary of Running Time ‹ ‹ ‹ ‹ ‹ ‹ O(m) for scanning arcs in update O(nK) for finding the minimum non-empty bucket O(nK) for redistributing the ranges O(nK) for Reinserting nodes into (different) buckets. O(nK) for finding the minimum distance value in buckets O(m + nK) in total. On choosing K ‹ Rule for last bucket: always keep its width equal to C. z Example: C = 30 z Suppose we need to redistribute range of bucket 7 Suppose we redistribute the last bucket. suppose d(9) = 32 and d(4) = 60 d(i) + C <= upper range of last bucket 0 9 13 19 1 1 10 14 20 2 2 11 21 3 12 15 22 3 13 ∅ 23 15 26 4 8 ∅ 27 15 31 5 16 ∅ 31 32 61 6 8 9 4 6 7 Distributing bucket 7 ‹ Usually, the bucket being distributed is left empty with no range. ‹ For the last bucket, we keep its width equal to C Suppose we do later do Update(i) i is not in the last bucket, so d(i) < 62. d(i) + C <= upper range of last bucket 0 9 13 19 32 1 1 10 14 20 33 2 2 11 21 34 3 12 15 22 35 3 13 ∅ 23 36 15 26 39 4 8 ∅ 27 40 15 31 47 5 16 ∅ 48 31 61 32 62 61 91 6 8 9 4 6 7 Summary ‹ Dynamic Lot-Sizing: reduces to a shortest path problem. ‹ Radix Heap: A bucket based method for shortest path z buckets may be redistributed z simple implementation leads to a very good running time ‹ Running Time Analysis z One of the key features will be in determining what steps to count and what steps do not need to be counted. z Analyze on a global level, if possible The number of steps at a particular find min may be O(nK). But that is also the number of steps over all iterations. ‹ Bottom Line in Practice: Radix Heaps are very efficient in practice, as are some other bucket based algorithms.