1
$\begingroup$

A similar question has been asked here, but this one is more complicated and has more constraints.

I'm trying to find an algorithm to solve the following (real-life) problem:

A customer has $M$ amount of money each month that he wants to invest according to her preferred asset allocation. Example

  • 60% stocks
  • 20% bonds
  • 20% REITs

She has a list of "favourite" financial instruments and a preferred allocation in each of the asset classes, e.g.:

  • Stocks: C (60%) and AAPL (40%)
  • Bonds: AGG (70%) and LQD (30%)
  • REITs: VNQI (100%)

Now, the algorithm would provide an investment advice (how many units and what financial instruments to buy) according to the following constraints:

  1. Total sum of purchases with fees cannot exceed $M$ (amount of money).
  2. Units are integer and indivisible, you can buy either one or two stocks but not 1.5. Since the customer ivests small(-ish) sums, this constraint becomes important. Example: $M$ is \$500 and AAPL is \$173 per unit!
  3. Main goal is fee minimisation (again, since the sum invested is not large, fees become relatively large). Instruments have different fees that not flat-rate. E.g.: fees for buying C are "\$1 if transaction sum is <\$100, 0.30% otherwise", but for VNQI they're "\$10 if sum < \$2000, 0.40% otherwise".
  4. Second goal is allocation that is approximately close to the "model allocation" above. Note that the model is concerned with asset classes, not individual instruments. That means the customer can buy only C or only AAPLto attain the desired 60% in Stocks. However, remember that there's also a preferred allocation within an asset class; if we decide not to buy C this month, then we'll need buy more of it next time to keep the stocks in balance.
  5. Fee minimisation can be attained by limiting the number of transactions. That means we can decide to buy, e.g., C, AGG and VNQI only, and think about buying AAPL and LQD next month. We can go even further and decide not to buy a whole asset class at all if the first solution has fees that are too high (above some pre-determined limit). In that case we'll remember that decision and buy more of it next month.

Now, I've been thinking about this for some time; I had my CS lessons over fifteen years ago, so had to rack my brain :) My first thought was of Bin packing problem. Nah. Doesn't really fit.
Then I remembered about Multi-dimensional unbounded knapsack. Again, not what I was looking for.
Considered Quadratic programming and Dantzig's simplex algorithm for linear programming. Not exactly fitting...

Maybe there is a special algorithm / special case for this kind of problem? Or shall I invent a new one? :)

$\endgroup$
  • $\begingroup$ Are you looking to have fun, or just get the project done. If the number of investments are very small, it may be reasonable to simply brute force the state-space. $\endgroup$ – Cort Ammon Feb 22 '18 at 0:34
  • $\begingroup$ Thanks for the advice @CortAmmon; as for your question - both, actually :) If I wanted a quick-and-dirty solution I wouldn't post on CS, I'd ask on StackOverflow :) I'm looking for a theoretically right way to tackle this problem. $\endgroup$ – Alexander Feb 22 '18 at 9:35
  • $\begingroup$ @Alexander: Did you solve this problem and have an example on how you did it? I am also trying to do the same thing. :) (working on a simplistic rebalancing algo) $\endgroup$ – Jannik Oct 1 '18 at 11:06
1
$\begingroup$

I'd suggest using integer linear programming (ILP). You need to buy an integer number of stocks, so you can use integer variables to represent the amount of each stock you buy. ILP can express constraints (requirements that must be true). The main limitation is that the objective function you are trying to minimize must be a linear function of the variables, but that can often be accomodated with auxiliary variables. For instance, your rules about the fees for buying different stocks can be expressed with ILP.

You'll have to figure out how you want to quantify and formalize "allocation that is approximately close to the model", as currently that is rather vague. Also note that anytime you say you have two goals, you aren't ready to formulate this as an optimization problem, because that leaves open how you plan to trade off the goals. You need to identify a single objective function you want to minimize, which means you'll need to think how you want to combine fee minimization with approximate model allocation. We can't tell you how to do that as that is a matter of what you want to achieve. One way would be to sum up the absolute value of the deviations from the model, and require this to be no more than a certain maximum. Another way would be to sum up the absolute value of the deviations, and add that to the objective function as an extra penalty.

$\endgroup$
  • $\begingroup$ Thanks @D.W.! You need to identify a single objective function you want to minimize - THIS! I think that was the reason the known solutions didn't seem to fit my problem. As for closeness to the model - yes, I'd thought about sum of squares of deviations. $\endgroup$ – Alexander Feb 22 '18 at 9:40
  • $\begingroup$ @Alexander, ok! If it's sum of absolute values, you can express that in ILP. If it's sum of squares, that's not expressible in ILP and will require something more powerful. $\endgroup$ – D.W. Feb 22 '18 at 16:49
  • $\begingroup$ Right... I'll use absolute values, then. Just out of curiosity @D.W., what would be "something more powerful"? :) $\endgroup$ – Alexander Feb 26 '18 at 8:45
  • $\begingroup$ @Alexander, mixed-integer quadratic programming (MIQP). $\endgroup$ – D.W. Feb 26 '18 at 17:09

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.