I have been learning about investments lately and encountered a concept called rebalancing. Rebalancing means exchanging assets to achieve a target allocation. For instance, suppose you resolve to hold 80% of your investments in stock and 20% in bonds. If you buy assets in those proportions and let them grow, the stock is likely to outperform the bonds. Your mix might drift to something like 90/10, and you need to rebalance.

In a typical investment portfolio, it’s not hard to figure out how to do this: In the example above, you would exchange 1/9th of the stocks for bonds. But the complexity escalates if your target allocation has more than two categories, or you hold a large number of mutual funds which themselves span multiple categories (consider a catalog of retirement strategy funds that contain different mixes of stocks and bonds).

For this post, let’s overthink things a bit and consider the general case of portfolio rebalancing with $n$ funds and $m$ asset categories. What’s the “cheapest” way to rebalance—how can you do it in the fewest transactions? And can we make “AI” (note: not actually AI) find the answer for us instead of eyeballing it?

Example

Funds are investment products we can buy and sell. Imagine our portfolio is currently invested in $n = 5$ funds as follows:

Fund	Holding
Whole-World Stock	$100.00
US Tilt Equity	$100.00
Strategy 90/10	$500.00
Ex-US Fund	$250.00
Bond Fund	$50.00

We want to (re)balance the portfolio above to achieve a target mix across US equities, foreign equities, and bonds—our $m = 3$ asset categories. With some research, we can look up the asset composition of each fund to produce a table like this:

Fund	US equities	Foreign equities	Bonds
Whole-World Stock	60%	40%
US Tilt Equity	90%	10%
Strategy 90/10	90%		10%
Ex-US Fund		100%
Bond Fund			100%

Our rebalancing objective consists of a target allocation across the asset categories. The table below shows our current allocation (which you can calculate using the holdings and asset composition data above) alongside the target allocation for comparison.

Component	Current allocation	Target allocation
US equities	60%	70%
Foreign equities	30%	25%
Bonds	10%	5%

How can we achieve the target allocation? Perhaps by working backwards. Among the funds on offer, we have two “pure” funds that are easy to work with: Ex-US Fund for foreign equities, and Bond Fund for bonds. We also have a nearly pure US equity fund in US Tilt Equity. A bit of algebra shows that putting 7/9ths of our portfolio into US Tilt Equity will achieve our goal for US equities, and then we can split the remaining budget across the two pure to round the portfolio out:

Fund	Current holding	Rebalanced holding
Whole-World Stock	$100.00
US Tilt Equity	$100.00	$777.78
Strategy 90/10	$500.00
Ex-US Fund	$250.00	$172.22
Bond Fund	$50.00	$50.00

This portfolio is balanced. However, to convert our current portfolio into this one will take at least three exchanges; one such sequence is this:

Exchange amount	From fund	To fund
$500.00	Strategy 90/10	Whole-World Stock
$77.78	Ex-US Fund	Whole-World Stock
$677.78	Whole-World Stock	US Tilt Equity

Is it possible to balance our portfolio using shorter sequence of exchanges?

Yes

It’s possible to rebalance this portfolio in two transactions:

Exchange amount	From fund	To fund
$61.11	Ex-US Fund	US Tilt Equity
$50.00	Bond Fund	US Tilt Equity

This results in the following holdings, which you can verify meet the target allocation:

Fund	Current holding	Rebalanced holding
Whole-World Stock	$100.00	$100.00
US Tilt Equity	$100.00	$211.11
Strategy 90/10	$500.00	$500.00
Ex-US Fund	$250.00	$188.89
Bond Fund	$50.00

Maybe you were able to identify the two-transaction solution to this problem by staring at the data and thinking about it. But in the general case, with large numbers of funds or allocation categories, that’s impractical. Instead, we can find the shortest rebalancing sequence using a mixed-integer linear program.

The linear program

Let $x_{ij} \geq 0$ denote the amount of fund $i$ that we exchange for $j$. This variable can’t go negative; $x_{ji}$ represents an exchange in the other direction.

Let $h_i$ denote our initial holdings of fund $i$. After applying the transactions $x_{ij}$, our rebalanced holdings of $i$ are

$$y_i(X) = h_i + \sum_{j=1}^n x_{ji} - \sum_{j=1}^n x_{ij}$$

which is a linear function of $X$.

We’ll use a matrix $C$ to denote the composition of the various funds on offer: $c_{ki}$ is the proportion of fund $i$ that aligns to category $k$. ($C$ is the transpose of the asset composition table from earlier.)

Let $t_k$ denote our target allocation for category $k$. Actually, it will be easier to work with $d_k = t_k \sum h_i$, which is just $t_k$ rescaled to currency units, or the number of “dollars” we have invested in each of the $m$ asset categories.

We want to minimize the number of nonzero entries in $X$. To model this, we apply the standard integer programming trick of introducing a helper binary variable $z_{ij}$ which is zero only if $x_{ij}$ is. The objective function is then just the sum of $Z$’s elements.

Here is the completed linear program:

$$\begin{aligned} \text{minimize} \quad & \sum z_{ij} \\ \text{subject to} \quad & Cy(x) = d & \text{(portfolio is balanced)}\\ & y(x) \geq \mathbf{0} & \text{(final holdings nonnegative)}\\ & X \leq MZ & \text{(}z_{ij}\text{ behave as intended)} \\ & X \geq \mathbf{0} \\ & z_{ij} \text{ binary} \end{aligned}$$

The $M$ in $X \leq MZ$ is a large constant; I used $M = \sum h_i$.

To avoid taking ourselves too seriously, we’ve used typical sloppy operations researcher notation: $a \geq b$ for vectors or matrices means the inequality holds between corresponding elements, $X$ and $Z$ are technically not matrices because they aren’t defined on the diagonal, etc.

The code

The rest is just coding. At that link, I implemented the integer program in Python using the PySCIPOpt bindings for the SCIP solver. Pyomo is the more popular Python library for this kind of work, but I thought the simplicity of PySCIPOpt was a better match to this task.

My human-written code specifies the problem as above, solves it, and renders the results as Markdown tables that I pasted above.