Back to Home Back to Notes

Best-Efforts Stock Allocation

Mixed-Integer Programming to Minimize Portfolio Drift
28th December, 2019

Let's say you have a three-fund portfolio, in which, say, 64% of your portfolio is comprised of domestic stock funds, 16% is comprised of international stock funds, and 20% is comprised of bond funds. Since stock prices go up and down over time, the percentage of the invested money drifts over time, so you re-balance your portfolio, say, annually, wherein you sell the funds that have exceeded the target percentage and buy the funds that are below the target percentage.

But what if you don't want to sell? Is there a way to rebalance your portfolio on the go, wherein each time you deposit money into your portfolio, you buy greater funds that have slipped below the target percentage and fewer funds that have exceeded the target percentage? Side note: Betterment calls this Cash Flow Rebalancing.

Manual cash flow rebalancing is very cumbersome, even for small amounts. My goal for many months was to both minimize the drift from the target percentage while also maximizing the amount spent from the monthly budget for investing. In the absence of quantifiable efforts, my allocations became ad-hoc. My thought process was like: Does it seem like the domestic stock index fund is valued too high? Okay, then, let's invest more in the bonds or the international index funds. I needed a better approach to decide how to spread my monthly allotment of funds into my portfolio.

Failed Attempt: SMT Solvers

As a quick and dirty hack, let's try to find the best allocation using a solver. It's relatively easy to express the problem into a set of constraints of the following form.

There are several implementation-related concerns, such as whether to use unbounded integeris and real-precision arithmetic, how to combine the different optimization objectives (pareto fronts versus ordered objectives), and how to express the maximization/minimization problem in SMT-LIB. Unfortunately, these low-level concerns probably don't matter much, since multi-objective optimization problems are quite difficult to solve. Here's a rough-cut initial version of my SMT-LIB code for solving the problem for a two-fund portfolio. Z3 returns unknown when checking for satisfiability for the following program.

  (declare-const x_count Real)
  (declare-const x_price Real)
  (declare-const y_count Real)
  (declare-const y_price Real)
  (declare-const x_current_alloc Real)
  (declare-const y_current_alloc Real)
  (declare-const x_target_percent Real)
  (declare-const y_target_percent Real)
  (declare-const x_drift Real)
  (declare-const y_drift Real)
  (declare-const dollars Real)

  ; The price of each share.
  (assert (= x_price 10))
  (assert (= y_price 20))

  ; The number of shares bought.
  (assert (>= x_count 0))
  (assert (>= y_count 0))

  ; The amount invested in each fund before buying new shares.
  (assert (>= x_current_alloc 50))
  (assert (>= y_current_alloc 50))

  ; The target percentage for each fund.
  (assert (= x_target_percent 0.9))
  (assert (= y_target_percent 0.1))

  ; Budget for investing.
  (assert (= dollars 100))

  ; Computes drift (TODO: include the current allocation).
  (assert (= x_drift (- x_target_percent (/ (* x_price x_count) (+ (* x_price x_count) (* y_price y_count))))))
  (assert (= y_drift (- y_target_percent (/ (* y_price x_count) (+ (* x_price x_count) (* y_price y_count))))))

  ; Budget constraints.
  (assert (<= (+ (* x_count x_price) (* y_count y_price)) dollars))
  (assert (<= x_count (/ dollars x_price)))
  (assert (<= y_count (/ dollars y_price)))

  ; Drift constraints
  (assert (<= x_drift  0.15))
  (assert (>= x_drift -0.15))
  (assert (<= y_drift  0.15))
  (assert (>= y_drift -0.15))

  ; Minimize objective function (remaining amount after spending).
  (minimize (- dollars (+ (* x_count x_price) (* y_count y_price))))

  (set-option :opt.priority pareto)
  (check-sat-using (then simplify smt))
  ; (check-sat)

  (get-value (x_count))
  (get-value (y_count))

Multi-Objective Linear Programming

While Z3 has trouble finding a solution, the same problem can be expressed, perhaps more succintly, as a linear programming problem, specifically, as a multi-objective mixed-integer programming problem. I used PolySCIP, which accepts input in the IBM MPS file format. The file format is somewhat cumbersome to read, but at a high level, it records coefficients of the constraint inequalities. I use the following Go code to generate the MPS file.

  package main
  import "fmt"
  import "log"

  func main() {
    available := 1000.0
    tolerance := 0.05

    split := []float64{ 0.6, 0.1, 0.1, 0.1 }
    price := []float64{   2,   1,  10,   5 }
    alloc := []float64{   0,  10,  70,  50 }

    if len(split) != len(price) || len(price) != len(alloc) {
      log.Fatal("Unequal sizes of input slices, terminating.")
    }

    count := len(split)

    alloc_total := 0.0
    for _, value := range alloc {
      alloc_total += value
    }

    fmt.Println("NAME  ALLOCATION")

    fmt.Println("OBJSENSE")
    fmt.Println(" MIN")

    fmt.Println("ROWS")
    fmt.Println(" N Remain")
    fmt.Println(" L Budget")

    for idx := 0; idx < count; idx += 1 {
      fmt.Printf(" G Drift%vMin\n", idx)
      fmt.Printf(" L Drift%vMax\n", idx)
    }

    fmt.Println("COLUMNS")
    fmt.Printf ("  x#%v Remain     %v\n", count, available)

    for idx := 0; idx < count; idx += 1 {
      fmt.Printf ("  x#%v Drift%vMin  %v\n", count, idx, alloc[idx])
      fmt.Printf ("  x#%v Drift%vMax  %v\n", count, idx, alloc[idx])
    }

    for idx_0 := 0; idx_0 < count; idx_0 += 1 {
      fmt.Printf ("  x#%v Remain     %v\n", idx_0, -price[idx_0])
      fmt.Printf ("  x#%v Budget     %v\n", idx_0, +price[idx_0])

      for idx_1 := 0; idx_1 < count; idx_1 += 1 {
        factor_min := -1.0 * (split[idx_1] - tolerance)
        factor_max := -1.0 * (split[idx_1] + tolerance)

        if idx_0 == idx_1 {
          factor_min = 1.0 - (split[idx_1] - tolerance)
          factor_max = 1.0 - (split[idx_1] + tolerance)
        }

        drift_min := +price[idx_0] * factor_min
        drift_max := +price[idx_0] * factor_max

        fmt.Printf ("  x#%v Drift%vMin  %v\n", idx_0, idx_1, drift_min)
        fmt.Printf ("  x#%v Drift%vMax  %v\n", idx_0, idx_1, drift_max)
      }
    }

    fmt.Println("RHS")
    fmt.Printf ("  RHS Budget     %v\n", available)

    for idx := 0; idx < count; idx += 1 {
      drift_min := alloc_total * (split[idx] - tolerance)
      drift_max := alloc_total * (split[idx] + tolerance)

      fmt.Printf ("  RHS Drift%vMin  %v\n", idx, drift_min)
      fmt.Printf ("  RHS Drift%vMax  %v\n", idx, drift_max)
    }

    fmt.Println("BOUNDS")
    fmt.Printf ("  LI BOUND       x#%v   1\n", count)
    fmt.Printf ("  UP BOUND       x#%v   1\n", count)

    for idx := 0; idx < count; idx += 1 {
      fmt.Printf ("  LI BOUND       x#%v   0\n", idx)
    }

    fmt.Println("ENDATA")
  }

The above script accepts the existing allocation, drift tolerance, target percentages, prices of each share, and the existing allocation, before generating an MPS file that can be fed to the PolySCIP tool. If it's not possible to achieve the desired target percentage within the given constraints, it reports that there is no possible solution for the problem. In such cases, try increasing the tolerance.

On a final note, this approach for computing the appropriate allocations is useful only when either the deviation between the existing percentages and target percentages is small or when the amount to invest is large. Put simply, if you want to turn two-fund portfolio from a 90%-10% allocation to a 10%-90% allocation, then you will need a large budget to invest in one of the funds to make it 90% of the total allocation. If you stay the course by avoid wild fluctuations in your target percentages, you should have no trouble using this approach to compute the appropriate allocation. Good luck!

Back to Notes