Algorithm for constrained proportional distribution

Question

I have a problem that essentially reduces to the following problem. Consider a set of n bins, with each of those bins having a weight (a 'weighting value' maybe - I'm not talking about the physical weight of the bin), a minimum (Edit: threshold) content and a maximum content. The objective is to distribute a certain amount x across all bins, in such a way that the amount in each bin is proportional to the weight of that bin, but still within the constraints of that bin (i.e., not lower than the minimum (Edit: at least the threshold), not more than the maximum). Anything under the minimum (edit: threshold) or over the maximum should be re-distributed across the other bins.

The naive implementation would assign x proportionally in a first round, not exceeding the maximum of any one bin; carry any excess to a next round and repeat until x is distributed; then it would check all bins to see if the minimum is met; those bins that don't meet the minimum, would be emptied and their content summed into a certain amount that would be redistributed across all bins and so on until all constraints are met and x distributed.

However, this algorithm is quadratic in runtime and I've already seen real datasets that aren't even near worst case and still exhaust my calculation budget. So, my question is - does anyone recognize this problem as as a known optimization problem? I'm lost in the sea of literature, and I think I'm just not searching for it using the right terminology. Of course I'm also happy (actually, happier :) ) with direct hints on how I can go about solving this in more efficient ways.

EDIT: I just found out that I used the wrong terminology above - although the example is OK. I'm using the wrong terminology in my own attempts at solving this, causing (at least some of) the confusion that lead me to asking this question. Either way, where it says 'minimum' above, it should read 'threshold'. So when the threshold for a bin is 5, it should only allocate to that bin when there's more than 5; if not, the amount should be distributed proportionally across the other bins.

I've adapted the text above to indicate this but it hasn't helped the legibility of the problem - not sure what the editorial guidelines are on issues like this here, because outright changing it into the correct version will make the comments not make any sense.

Answer 1

Let me first solve the problem under my previous misinterpretation, in which allowable answers must fill each bin to its minimum quantity.

First check to see if your amount x is greater than the sum of the maximum capacities of all the bins, or less than the sum of the minimum capacities. If either is the case there is no good solution under the current selection of bins.

For each bin compute normalized min and max quantities - the current min and max quantities divided by the weight of that bin.

Consider allocating to bins using a (currently unknown) magic quantity q. If normalized min > q, fill the bin to its minimum. If normalized max < q, fill the bin to its max. Otherwise fill the bin with weight * q. For very low values of q we get the absolute min total content. For very high values of q we get the absolute max total content. One of the intermediate values of q should match your desired total content. At this value the intermediate bins have zero error and the min and max bins are as close to their ideal filling as the constraints will let them.

The total amount distributed, as a function of q, is monotonic increasing piecewise linear, changing slope at normalized minimum and maximum values. If you compute and sort these breakpoints in time O(n log n) you can binary search to find breakpoints which provide just above and just below your target quantity with total cost n for each guess and log n guesses required. Then use linear interpolation to find the correct value of q exactly.

Alternatively, if you sort normalized max and min values into one array I think you can track how the amount distributed increases as you increase q. Start off with q at the lowest minimum, where the amount distributed is the sum of all of the minimums. The gradient here is the weight for that lowest minimum bin. As you pass other minimums the gradient increases by their weight. As you start to pass maximums, the gradient decreases by their weight. Scanning along this array, you can find the place where the amount distributed is the desired quantity, and the dominant cost is the cost of sorting pooled normalized maximums and minimums.

We now have an algorithm for filling the bins in the case when each must end up with at least its minimum quantity. This constraint is incorrect, and in fact we can recognize when this goes wrong - when either the sum of the minimum quantities is above the target quantity, or when some bin ends up with more than its fair share.

When the algorithm goes wrong we can use the same strategy as in the original naive solution - remove some bins from consideration if there are bins whose minimum is too large, and put some bins back if we don't have room for everything (I don't know if that is the correct answer but I assume it's at least acceptable because of its use in the naive solution). We remove bins this starting with the bins whose normalized minimum quantity is largest. Again, because we can binary chop on the bins we only need log n passes - I presume we want to use as many bins as possible.

This gives us an outer loop of log n passes round our original solution. If the original solution takes time n log n and we repeat it from scratch each time the cost is n (log n)^2. If we use the alternate where the only log n factor is because of an initial sort, we need only do that initial sort once, at the start, and each inner pass costs us only O(log n). This gives us a total cost of O(n log n).

Answer 2

This problem is essentially the apportionment problem in electoral systems, and as such it has been widely studied, both by mathematicians and by political scientists (not necessarily with the same criteria).

The apportionment problem includes both the assignment of parliamentary seats to parties or lists based on electoral result (as in Spain or the Netherlands, for example) and to the assignment of parliamentary seats to subnational electoral districts based on population (states in the United States, for example), voting population, or even the total vote in a previous election. Political exigencies have led to a variety of adjustments to the basic algorithms, including minima and maxima (as in your question) and non-linearities.

Except in very rare cases, it is impossible to achieve perfect proportionality such that the allocation to each entity is exactly proportional to the weight (vote / population / etc.) of that entity. The apportionment algorithm is generally expected to minimize disproportionality, but there is no consensus on how to measure disproportionality, so there are frequently different (though similar) apportionments for the same weights, each of which minimizes a different metric.

For the most part, we can divide apportionment algorithms into two broad categories: greatest divisor (or greatest average) and greatest remainder.

Greatest divisor methods

The greatest divisor methods attempt to find some q such that the allocation of entity i is computed as

Ai = ⌊Wi/q + α⌋

where Wi is the weight of entity i and α is some number in the range [0, 1). There is almost always such a q, except in rare cases where two or more entities are tied, in which case it may be necessary to arbitrarily select some subset of the tied entities to award an additional apportionment. Common values of α are 0 (the "D'Hondt method") and 0.5 (the "Sainte-Laguë method"); both of these are named after the mathematicians who developed the respective algorithms and proved their optimality (obviously using slightly different metrics.) The D'Hondt method tends to slightly favour entities with larger weights, but is the one most commonly used in proportional representation systems other than in Scandinavia, where methods more similar to Sainte-Laguë are used, which are more neutral with respect to weight. (Values of α greater than 0.5 would tend to favour smaller weights.) (Algorithms for finding the quotient q are provided below.)

A slightly different method is currently used to apportion congressional seats between US states: the Huntington-Hill method (named after a mathematician and a statistician). In this method, rather than attempting to round allocations linearly (as in Sainte-Laguë), the allocations are rounded according to the geometric mean.

Greatest remainder methods

The greatest remainder method is often said to be easier to understand, and the algorithm to perform it is slightly simpler, but there are some issues with stability of the results. Here, we start by computing a value of q which is known to result in an apportionment which (using the same formula as above with α set to 0) is either correct or one too small for every entity. It is then necessary to apportion up to one allocation more for some subset of the entities; this is done by ordering the remainders dropped by the floor operator, and awarding the extra allocation to those entities with the largest remainders (hence the name "largest remainder").

There is more than one way to compute q to provide the starting point for the largest remainder method, and the final result depends (somewhat unpredictably) on the initial choice of q. It is precisely this unpredictability which leads to criticisms of the largest remainder method: it was once used to apportion congressional seats to states in the US, but the algorithm was changed as a result of the "Alabama paradox"; a particular distribution of population with which the addition of an extra congressional seat would have caused the state of Alabama to have a smaller apportionment.

Nonetheless, largest remainder mechanisms are still used in a few jurisdictions, and are often proposed on the (arguably misguided) assumption that the ease of understanding the mathematics is more important than the occasional paradoxical result. Two common formulas for computing q are (here, N is the number to be allocated):

• Hare formula: q = ΣW / N

• Droop formula: q = ⌊1 + (ΣW / (N + 1))⌋

Of these, the Droop formula is more common.

---

Algorithms

There is a very simple O(N) algorithm for allocating with a greatest remainder method. First, q is computed (as above); then an initial allocation is made by dividing each weight by q and taking the integral part; these initial allocations are summed and subtracted from the desired total allocation. The difference k must be an integer between 0 and N; subsequently the largest k remainders are found and those entities have their allocation incremented. This can be done in time O(N) using quick-select, although it's very common to see code which does a complete O(N log N) sort.

The simplest formulation of the largest divisor algorithm is O(ΣA log N), where N is the number of entities (as above) and ΣA is the total allocation. For the simplest case -- the D'Hondt allocation -- we start by allocating 0 to each entity, and then placing the N entities in a max-heap ordered by comparing the computed ratio Wi/(Ai+1). We then iteratively increase the allocation of the entity at the top of the heap, which changes its comparison value forcing a down-heap operation, until we have allocated the desired total. Since the heap is always of size N, the ΣA down-heap operations each take time log(N). We can, however, significantly improve this running time by constructing an initial estimate of the divisor and thus a base allocation, as with the largest remainder method, and then proceeding with the algorithm from that starting point. If the initial guess is within N of the correct allocation, the total time will be O(N log N). (This modification is described in the Brasilian election law, for example.)

The Sainte-Laguë mechanism replaces the comparison computation with Wi/(2×Ai+1), which effectively causes the comparison to be made at the mid-point of the allocation range [Ai, Ai+1). Similarly, the Huntington-Hill geometric mean algorithm uses comparison based on Wi/√(Ai×(Ai+1)). Neither of these modifications affects asymptotic complexity.

Incorporating minimum and maximum allocations

Adapting these algorithm to minimum and maximum allocations can be done in a variety of ways, again depending on the proportionality metric one wishes to optimize. I don't know of real-world examples with maxima, but minima are very common when least remainder methods are used to apportion seats between subnational entities, since it's general considered undemocratic for an entity to have no representation even if the entity is very small.

A very common rule is to separate out the minimum allocations and run one of the above algorithms only with what is left to be allocated. (That's the mechanism used both in the United States and here in Perú to apportion seats to states/departmentos.) The result, of course, disproportionately benefits smaller subnational entities because the value of a "free" extra seat to an entity which only has two seats is proportionately much greater than the value of the same "free" extra seat to an entity with 36 seats.

With the greatest divisor method, a simple and clearly more proportionate solution is to preallocate the minima but then continue with the standard algorithm from that starting point. If an entity reaches its maximum, it is then removed from the heap rather than down-heaped, making it unavailable for future allocations.

For greatest-remainder, something similar could be done. For example, the initial allocation could be performed according to the formula, and then adjusted to conform to the maxima and minima. If the adjustment reduces one or more allocations which reach their maxima, the secondary allocation might exceed the number of entities, but this does not complicate the algorithm much (each allocation will be increased by k or k+1 instead of 0 or 1), except that care must be taken to avoid secondary allocations from exceeding maxima. If, on the other hand, many allocations are increased to comply with the minima, it might turn out that the secondary "allocation" becomes a negative allocation using the smallest remainders instead of the largest (and again taking care not to reduce any entity below its minimum).