Search code examples
algorithmsortinggreedy

optimizing resource allocation using criterion set

A dying father is interesting in divesting his estate. he has a portfolio like so:

AAPL : 5,000
MSFT : 10,000
AMZN : 6,000 and etc

we know the number of different type of stocks is finite, and the total number of stocks held is finite

He has a number of estate beneficiaries, a number unknown to us but we know it is finite. Each beneficiary has different requirements that we know, the number of requirements are finite.

For instance:

Case 1:
    Charity X can only take 3,000 shares of AAPL and 6,000 share of MSFT
    Leftover  : 2,000 shares of AAPL, 4,000 shares of MSFT, 6,000 shares of AMZN

Case 2:
    Charity X can only take 3,000 shares of AAPL and 6,000 share of MSFT
    Charity Y can ony take 1,000 shares of AAPL
    Leftover  : 1,000 shares of AAPL, 4,000 shares of MSFT, 6,000 shares of AMZN

Is there an algorithm that is able to:

  • return the optimal distribution of shares across 1 beneficiary, OR 2 beneficiary OR 3 beneficiaries etc

  • with the minimal leftover in the original dying father's portfolio - if the type of stock requirement, and limit on number of stock of that type for each beneficiary is known?

Solution

  • This can be solved by some form of linear programming.

    It fits the definition of a linear programming problem exactly: You have a set of non-negative variables: the amounts of each stock everyone, including the "leftover" fraction gets. You have a set of constraints on them: the maximum number of shares one fraction can hold of a type. And you have a target function to maximize! The number of leftover shares should be minimized, i.e. its negative should be maximized.

    I'm not a finance person, but I guess that you cannot have fractional shares. In this case, the problem gets a lot harder because all your numbers are required to be integers. This is then called "integer linear programming" (ILP). In many practical solutions, this can be NP-hard. However, chances are that your instance can be solved effectively if your numbers aren't too weird. ILP solvers are also well researched because a lot of problems can be mapped to them. Also check this answer on SO.