1
$\begingroup$

Resource allocation problem

Given

  1. T, total amount of resources
  2. N, targets of resource allocation
  3. T > 0; N > 1; T < N

Allocate resources amongst targets, s.t.

$$0 <= allocation_{i} < 1$$ $$allocation_{i+1} < allocation_{i}$$ $$\sum_{i=1}^N allocation_i <= T$$

$$minimize (T - \sum_{i=1}^N allocation_i)$$

An important freedom and a constraint is that the solution need not be the most optimal; however it must arrive within just a few iterations (like, say, < 10) because of runtime limitations.

I started with $$allocation_i = e^{-ki}$$ and locate k but that only led me to a problem with a numerical solution which can take long to solve. I want to explore if there are other monotonically decreasing functions that will solve faster and provide a reasonably good allocation.

Some illustrative values of T, N if it helps. N typically in (10, 1000); T/N typically in (0.05, 0.5)

EDIT: I rewrote the question taking into account the comments, and also reformatted it. I hope this is clearer. This is my first post here and I am just learning how-to form the question :-)

Thanks

$\endgroup$
  • $\begingroup$ What is $T$? Is it $T=\sum_{i=0}^N \exp (-k i)$? So you want to find $k$ from the inequality: $$\sum_{i=0}^N \exp (-k i) < N+1$$??? $\endgroup$ – Yuriy S Sep 26 '17 at 23:25
  • $\begingroup$ Yes, but as close to RHS as possible. Also please see my other comment - any monotonically decreasing function will do for my problem $\endgroup$ – Dinesh Sep 27 '17 at 1:13
  • $\begingroup$ Wait a minute, by your statement in the 3rd paragraph, the sum is only approximately equal to $T$, in other words the total allocated amount may be a little less than $T$: $$\sum_{i=0}^N \exp (-k i) \leq T$$ Because if you request it to be exactly $T$, you will have a problem finding an analytical solution, but you can approach $T$ from below quite well. Another question is how to obtimize the curve for any $N$ so the allocated amount is as close to $T$ as possible. $$ $$ What I don't quite get is why is $T \leq N+1$, how are the numbers connected? If $T=N+1$, then each recipient can get $1$ $\endgroup$ – Yuriy S Sep 27 '17 at 15:44
  • $\begingroup$ In other words, if you could please explain what you really want to achieve (it might be just me, but I don't understand). For example which parameter is fixed here and which is variable? $T$ or $N$? Or both? Are they always connected by $T \leq N+1$ and if so, why? This might go beyond the scope of the question, let's say I'm just curious $\endgroup$ – Yuriy S Sep 27 '17 at 15:50
  • $\begingroup$ I rewrote the question, hope this is clearer now. My basic problem is to allocate given resource amount amongst targets, in a decreasing fashion, exhausting the resource as best as possible, but must do it quickly. $\endgroup$ – Dinesh Sep 27 '17 at 21:53
1
$\begingroup$

I post this as another answer for clarity.

There seems to be a much simpler way to allocate resources for you in the special case of:

$$T \leq \frac{N+1}{2}$$

Considering the value ranges you provided this condition seems to be fulfilled.

Then we use the simple fact:

$$\sum_{i=1}^N i=\frac{N(N+1)}{2}$$

Now let us divide both sides by $N$ and reverse the order of summation:

$$\sum_{i=1}^N \frac{i}{N}=\frac{N+1}{2}$$

$$\sum_{i=1}^N \frac{N-i+1}{N}=1+\frac{N-1}{N}+\frac{N-2}{N}+\dots+\frac{1}{N}=\frac{N+1}{2}$$

Finally we introduce a parameter $p$ such that:

$$p=\frac{2T}{N+1} \leq 1$$

Then:

$$p \sum_{i=1}^N \frac{N-i+1}{N}=T$$

$$T=\frac{2T}{N+1}+\frac{2T(N-1)}{N(N+1)}+\frac{2T(N-2)}{N(N+1)}+\frac{2T(N-3)}{N(N+1)}+ \dots$$

Each term above is the part of a resource allocated to each of the $N$ targets.

The largest part is:

$$A_1=p=\frac{2T}{N+1}$$

The smallest part is:

$$A_N=\frac{p}{N}=\frac{2T}{N(N+1)}$$


In addition:

If the first recipient should always get a full resource ($A_1=1$) you can just put it aside and rename the parameters:

$$T-1 \to T^*$$

$$N-1 \to N^*$$


Important update!

We can actually relax the above condition on $T$ using the relations:

$$\sum_{i=N+1}^{2N} i=\frac{N(3N+1)}{2}$$

$$\sum_{i=2N+1}^{3N} i=\frac{N(5N+1)}{2}$$

and so on.

Thus, we can make the condition to be:

$$T \leq \frac{3N+1}{4}$$

$$T \leq \frac{5N+1}{6}$$

And finally for any integer $M \geq 1$:

$$T \leq \frac{M N+1}{M+1}$$

I will allow you to derive the expression for $p$ and the allocations yourself.

$\endgroup$
2
$\begingroup$

As I read it, the terms of the series are $e^{-ki}, i=0..N $.

This is just a geometric series with sum

$\begin{array}\\ s &=\sum_{i=0}^N e^{-ki}\\ &=\sum_{i=0}^N (e^{-k})^{i}\\ &=\dfrac{1-(e^{-k)^{N+1}}}{1-e^{-k}}\\ &=\dfrac{1-r^{N+1}}{1-r}\\ \end{array} $

where $r = e^{-k} $.

So you want $T = \dfrac{1-r^{N+1}}{1-r} =\sum_{i=0}^N r^i $.

This can only be solved numerically for $N \ge 5$. Once we get $r$, then $k = -\ln(r)$.

If $T$ is close to $N+1$, then, if we approximate $r = 1-d$ where $d$ is small, the sum is

$\begin{array}\\ T &=\sum_{i=0}^N r^i\\ &=\sum_{i=0}^N (1-d)^i\\ &\approx\sum_{i=0}^N (1-id) \qquad\text{for quite small }d\\ &=N+1-d\sum_{i=0}^N i\\ &=N+1-dN(N+1)/2\\ \end{array} $

so $d =2\dfrac{N+1-T}{N(N+1)} $.

$\endgroup$
  • $\begingroup$ In my use case, T and N don't share any relationship. T is resource and has a bound, e.g. 300 or 1000. N is very unpredictable. Is it possible to get to a reasonable estimate for r in a few iterations? ALSO, is there some other monotonically decreasing function that will do such an allocation of resources? $\endgroup$ – Dinesh Sep 27 '17 at 1:11
  • $\begingroup$ Then you have to solve it numerically. $\endgroup$ – marty cohen Sep 27 '17 at 1:22
  • $\begingroup$ are there better decreasing functions that can be solved quickly or is e(-k) the best factor? $\endgroup$ – Dinesh Sep 27 '17 at 21:54
  • $\begingroup$ @Dinesh, I wasn't able to find a better option so far. I don't think it's that hard to compute $k$ numerically by using Newton's method for example $\endgroup$ – Yuriy S Sep 27 '17 at 23:12
0
$\begingroup$

Considering the edited question and marty cohen's answer, I don't see a more simple way that the geometric series.

Even though I don't see which function $f(i)$ under the sum could get us an analytic solution for the parameter, geometric series with $f(i)=p^i$ still allow us a simple numerical scheme to find $p$.


Let's first allow the first target to get a full resource. It would be easy to subtract some part of it and add to the second target if needed.

So denoting the allocations $A_i$ we always have $A_1=1$.


For the geometric series we have the condition:

$$\sum_{i=0}^{N-1} A_{i+1}=\sum_{i=0}^{N-1} p^i=T$$

$$p<1$$

$$\frac{1-p^N}{1-p}=T$$

We obtain an algebraic equation of degree $N$:

$$p^N-T p+T-1=0$$

Note that for $N >> 1$ and $p<1$ we have approximately:

$$p \approx \frac{T-1}{T}$$

This will be our first guess for the numerical iterations.

Newton's method consists of picking some $p_0$ and then computing the next iterations as:

$$p_{k+1}=p_k-\frac{F(p_k)}{F'(p_k)}$$

In our case:

$$F(p)=p^N-T p+T-1$$

$$F'(p)=Np^{N-1}-T$$

Thus:

$$p_0=\frac{T-1}{T}$$

$$p_{k+1}=p_k-\frac{p_k^N-T p_k+T-1}{Np_k^{N-1}-T}$$


Let's check this method for $T=300$ and $N=1000$:

$$p_0=\frac{299}{300}=\color{blue}{0.996}6666\dots$$

$$p_1=p_0-\frac{p_0^{1000}-300 p_0+299}{1000p_0^{999}-300}=\color{blue}{0.99680}083907776694848\dots$$

$$p_2=\color{blue}{0.996802135}036332828\dots$$

$$p_3=\color{blue}{0.99680213516858413}5\dots$$

Since Newton's method has quadratic convergence, the number of correct digits approximately doubles at each step.


Now everything depends on the computational resources you have and the accuracy you need.

(Update: See another answer for a more simple method, for a certain condition on $T,N$)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.