1
$\begingroup$

Apologies if this does not fit the proper format for this site, as it is a somewhat general question.

I have an application that sits on top of a SQL database, and need to handle a process which is very much like a linear algebra problem, whereby an amount a (any number between 0-1B) needs to get distributed among n entities (e), based on a few parameters (rank, weight, min/max requirements) set at the entity level.

Example:

a = 100

entity    weight    min    max
----------------------------------------------
X         0.25      10     40
Y         0.75      40     60     
...

In this example, 25 (a * X[weight]) would go to entity X, and 75 would go to entity Y; however, 75 exceeds Y[max], so the remaining 15 need to go to another entity (in this case, X, since it stays at or under X[max]).

Intuitively, this is in iterative process. In a real example, there would be more entities, so more iterations would be necessary. SQL is not designed to iteration. I am looking for a way to better handle this in a set based method.

What I am looking for is something along the lines of:

  • a statistical method that I can use to minimize the number of iterations I need to make, or even better, a way that this can be distilled into a formula?

  • alternatively, maybe there is a way to store some of the data in a static way to minimize the steps needed to make the calculations on the fly?

  • Creating a lookup table, whereby for each entity there could be a stored outcome for min/max ranges, based on the other entities (they are in groups of 10 or less).

Improve this question
$\endgroup$
3
  • $\begingroup$ I think you're describing a linear program en.wikipedia.org/wiki/Linear_programming optimize some linear function, subject to some linear inequality or equality constraints. But it's not clear from the post what the objective is that you're minimizing, or really what the task is aside from something involving satisfying constraints. $\endgroup$
    – Sycorax
    Feb 19, 2021 at 14:51
  • $\begingroup$ The original problem is not really an optimization problem, in terms of optimizing a value. I guess it is more like a distribution algorithm which I am trying to either put into a formula or optimize for number of iterations. $\endgroup$
    – Sam Cohen-Devries
    Feb 19, 2021 at 15:07
  • 1
    $\begingroup$ It's not well defined what happens in the cases where the weights produce values outside the allowed ranges. If one entity is outside the allowed range do you just abandon the idea of weights entirely, or should the others still be in proportion? With weights out the window there could be many possible solutions (or none), do you care at all which one is chosen? $\endgroup$
    – pseudospin
    Feb 20, 2021 at 0:02

1 Answer 1

Reset to default
1
$\begingroup$

It looks like a resource allocation problem. I can't think of any statistical method which would help here, but maybe there is.

I think the process can be simplified by first calculating the amount in excess and in "shortage". I don't know if there's a formal method for this but I would try something like the following:

  • Distribute $a$ based on the weights. Then calculate for every entity:
    • its excess amount: X has 0, Y has 15 (75-60)
    • its missing amount: X has 0, Y has 0.
    • its capacity for additional amount. X has 15 (40-25) and Y has 0.
    • its capacity for giving away some amount. X has 15 (25-10) and Y has 20 (60-40)
  • Calculate the sum of excess amount $S_{excess}$, sum of missing amount $S_{missing}$, and capacity $S_{plus}$, $S_{minus}$. Let $S = S_{excess} - S_{missing}$:
    • If $S>0$
      • If $S>S_{plus}$, then no solution
      • Otherwise (1) fill every entity which has amount missing to their minimum, (2) distribute amount S by filling any entity which has capacity for more.
    • If $S<0$
      • If $|S|>S_{minus}$, then no solution.
      • Otherwise (1) unload every entity which has amount in excess to their maximum, (2) take total amount |S| from any entity which capacity for giving away.

If I'm not mistaken this requires only two steps, each step going over all the entities.

Improve this answer
$\endgroup$
2
  • $\begingroup$ really appreciate this detailed response! just to confirm, in the second step, S_excess, S_missing, etc... these are aggregated across all entities? $\endgroup$
    – Sam Cohen-Devries
    Feb 25, 2021 at 15:23
  • $\begingroup$ @Samcd sorry I missed your question: yes these are aggregated across all the entities. $\endgroup$
    – Erwan
    Mar 3, 2021 at 23:25

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.