Weighted average distribution algorithm

Question

I have N buckets, each with a normalized weight of W_i. I would like to distribute $x to each bucket by its weight. Each bucket has a minimum $ (MIN_i) and maximum $ (MAX_i) that the algorithm needs to fulfill. The min and max of each buckets take priorities over the weights. Is this problem solvable in polynomial time and how does the algorithm look like?

Example:

4 buckets, A, B, C, D

A: W_A = 100, MIN_A = 0, MAX_A = 150

B: W_B = 100, MIN_B = 0, MAX_B = 60

C: W_C = 1, MIN_C = 20, MAX_C = 150

D: W_D = 1, MIN_D = 30, MAX_D = 150

Total $ = $150

Expected Result:

A: $50

B: $50

C: $20

D: $30

Note that C and D are using their mins and the rest of the dollars are split evenly because A and B have the same weight.

Answer 1

Step 1: Assign all min budgets

in your example: 
( 0, 0, 20 ,30)

Step 2: Calculate ideal assignments if there were no boundaries:

in your example: 
(100/202)*150 =74
(100/202)*150 =74
(1/202)*150 = 0.74
(1/202)*150 = 0.74

Step 3: Subtract what is "current assignment" from the ideal:

in your example:
0 - 74 = -74
0 - 74 = -74
20 - 0.74 = 19.26
30 - 0.74 = 29.26

Step 4: Assign a dollar/cent to the lowest value in step 3

in your example:
-74 is the lowest value
so just assign a dollar to the first one with the lowest value

Step 5: Repeat steps 3 and 4 and stop allocating budgets to a bucket that reaches its cap.

Answer 2

Let z be a real parameter. My understanding of the problem is that you want to find z such that, when bucket i is allocated max(MIN_i, min(MAX_i, W_i z)), the sum of allocations equals x.

Here's an O(n log n)-time algorithm (there's probably a linear-time one, but if it does exist it's likely to be more complicated). Intuitively what it does is to increase z continuously until the sum of allocations equals x.

The derivative of the sum in z is the sum of the derivatives for each bucket. The derivative of bucket i is 0 for z < a, then W_i for a < z < b, then 0 for b < z, where a = MIN_i / W_i is the first critical point, and b = MAX_i / W_i is the second critical point. We sort these critical points and then trace out the resulting piecewise linear function. In Python 3 (intentionally avoiding some Python idioms):

import collections

Bucket = collections.namedtuple('Bucket', ('weight', 'min', 'max'))
Event = collections.namedtuple('Event', ('key', 'i', 'derivative'))


def allocate(total, buckets):
  n = len(buckets)
  events = []
  derivative = 0
  residual = total
  derivatives = []
  for i in range(n):
    bucket = buckets[i]
    events.extend([Event(bucket.min / bucket.weight, i, bucket.weight),
                   Event(bucket.max / bucket.weight, i, 0)])
    residual -= bucket.min
    derivatives.append(0)
  events.sort()
  z = 0
  for event in events:
    if derivative > 0:
      w = z + residual / derivative
      if w <= event.key:
        z = w
        break
    residual -= derivative * (event.key - z)
    derivative -= derivatives[event.i]
    derivatives[event.i] = event.derivative
    derivative += derivatives[event.i]
    z = event.key
  allocations = []
  for i in range(n):
    bucket = buckets[i]
    allocations.append(max(bucket.min,
                           min(bucket.max,
                               bucket.weight * z)))
  return allocations

print(allocate(150,
               [Bucket(100, 0, 150),
                Bucket(100, 0, 60),
                Bucket(1, 20, 150),
                Bucket(1, 30, 150)]))
# [50.0, 50.0, 20, 30]
print(allocate(100,
               [Bucket(40, 42, 55),
                Bucket(40, 0, 100),
                Bucket(20, 0, 4)]))
# [48.0, 48.0, 4]