15.082 and 6.
855J
Shortest Paths 2:
Application to lot-sizing
R-Heaps
1
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?
2
Application 19.19. Dynamic Lot Sizing (1)
D
0
1 2 3 4 K-1 K
-d1 -d2 -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.
3
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
D
0
4 5 6 7 K-1 K
-d4 -d5 -d6 -d7 -dK-1 -dK
4
D
0
4 5 6 7 K-1 K
-d4 -d5 -d6 -d7 -dK-1 -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 a 7).
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 D
i i+1 i+2 j-1 j
-di -di+1 -di+2 -dj-1 -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 Potential
2 4 4 Bottleneck:
2 2 Scanning
0
1 1 2 3 6 empty
4 2 buckets.
3 3 5
4
0 1 2 3 4 5 6 7
2 3
8
Using a bucket with a larger “width”
22 If costs are
2 45 4 larger, one can
22 29
0
make larger
1 14 26 3 6 buckets. But
41 27 then, how does
one do a “find
3 31 5 min?”
41
10 - 20 - 30 - 40 - 50 - 60 - 70 -
0-9 19 29 39 49 59 69 79
2 3
width = 10
9
A comment on buckets
The bucket implementation
Finding the first node in a bucket takes O(1) time
If the buckets have width 1, then each node has
minimum label
If the buckets have width > 1, then we need to find
the node in the bucket with min d(j).
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.
10
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
11
Radix Heap Example
Buckets: 5
2 4
bucket sizes grow 15 2
13
exponentially
ranges change 1 6
dynamically
20
0
8
9
3 5
2 4 8 16 32
0 1 7 15 31 63
3 Radix Heap
Animation
12
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.
13
On the number of buckets
Let K = Number of Buckets.
Running time is O(m + nK).
The initial widths of the buckets are 1, 1, 2, 4, 8,
…, 2K-2
K =2+ log (C+1)
Note that Bucket K has width at least C
Further improvements are possible.
14
Algorithm Outline
Initialization:
Initializes the buckets with bucket ranges 0, 1,
2-3, 4-7, 8-15, etc;
Initializes d( );
places node j in the bucket whose range
contains d(j);
Update(i)
d(j) = min(d(j), d(i) + cij) for (i,j) A(i)
Reinsert(j) if necessary: that is move it to the
bucket whose range contains d(j);
15
Algorithm outline (continued)
Select min
scans buckets to find the min non-empty
bucket, say bucket B (e.g., B = 4)
scans B to find d*, the min temporary label
redistributes the ranges in bucket B to
buckets 1 to B-1, starting with value d*
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)
selects a node from Bucket 1.
Additional issue to address later: why we have
enough buckets.
16
Algorithm running time: Initialization
Initializes the buckets with bucket ranges 0, 1, 2-3, 4-
7, 8-15, etc;
O(K) steps
Initializes d( );
O(n)
places node j in the bucket whose range contains d(j);
O(n) assuming that d(1) = 0 and d(j) = for j > 1.
17
Initialization step
5
Initialize 2 4
distance labels 13
15 2
0
Initialize buckets
1 6
and their ranges.
20
0
8
Insert nodes into 9
3 5
buckets.
2 4 8 16 32
0 1 7 15 31 63 2
3 3
4
1 5
6
18
Update(i) Analysis
d(j) = min(d(j), d(i) + cij) for (i,j) A(i)
O(m) time in total
Reinsert(j) if necessary: that is move it to the
bucket whose range contains d(j);
Potentially O(K) per scan of each arc.
Improved running time comes from a “global
perspective”
19
More on update
Example: d(9) =57
Update takes time
Case 1: d(9) is decreased to 37 O(m + nK)
Node 9 stays in bucket 7 Each node j can
O(1) time for the update shift left K-1
buckets, and
Case 2: d(9) is decreased to 23 determining the
buckets takes
Node 9 moves to bucket 3
O(K) additional
4 steps to find the bucket steps.
20 22 26 32
18 19 21 25 31 63
1 2 3 4 5 6 7 20
Select Min (step 1)
scans buckets to find the min non-empty bucket,
say bucket B (e.g., B = 4)
O(K) steps per find min,
O(nK) steps in total
2
11
13
8 16 32
0
9
13 1
10
14 12
15 15 15 31 63
3
6
8
21
Select Min (step 3)
scans B to find d*, the min temporary label
will be analyzed later
redistributes the ranges in bucket B to buckets 1
to B-1, starting with value d*
O(K) steps per find min,
O(nK) steps in total
e.g, suppose d(6) = 19, d(8) = 25;
2
11
21 13
23
8
27 16
32
0
9
13
19 1
10
14
20 12
15
22 15
26 15
31 31 63
3
6
8
22
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)
O(K) over all select min for each node j
O(nK) in total
selectsa node from Bucket 1.
O(1) per select min
O(n) in total
2
11
21 13
23
8
27 16
32
0
9
13
19 1
10
14
20 12
15
22 15
26 15
31 31 63
3
6 8 6
8
d(6) = 19, d(8) = 25 23
Select Min (Step 2): a dominance argument
scans B to find d*, the min temporary label
Suppose that there are n’ nodes in bucket B.
O(n’) steps to determine d*
But the n’ nodes then are reinserted
at least n’ steps to reinsert these nodes
Conclusion. The running time for Step 3 is
O( running time for reinsertion ) = O(nK)
2
11
21 13
23
8
27 16
32
0
9
13
19 1
10
14
20 12
15
22 15
26 15
31 31 63
3
6
8
B
24
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.
25
On choosing K
Rule for last bucket: always keep its width equal to C.
Example: C = 30
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
2
11
21 13
23
8
27 16
32
0
9
13
19 1
10
14
20 12
15
22 15
26 15
31 31 61
3
6 9
8 4
1 2 3 4 5 6 7
26
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
2
11
21
34 13
23
36
8
27
40 16
48 32
62
0
9
13
19
32 1
10
14
20
33 12
15
22
35 15
26
39 15
31
47 31
61 61
91
3
6 9
8 4
1 2 3 4 5 6 7
27
Summary
Dynamic Lot-Sizing: reduces to a shortest path
problem.
Radix Heap: A bucket based method for shortest
path
buckets may be redistributed
simple implementation leads to a very good
running time
28
Running Time Analysis
One of the key features will be in determining
what steps to count and what steps do not
need to be counted.
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.
29