Assigning weights to portfolio assets is challenging when we have to consider multiple constraints. Asset allocation may be seen as a constraint satisfaction problem (CSP), and some algorithms allow us to define our own restrictions and look for an optimal weight distribution.

In this post, we will show how to define a CSP for your portfolio and how to use the Backtracking algorithm to obtain an optimal solution.

“Anyone who has never made a mistake has never tried anything new.”
― Albert Einstein

Making mistakes is human, and history has taught us that they are often necessary in order to find a solution. Many artificial intelligence algorithms also make mistakes as a means of learning how to solve a problem. As we saw in this post, backtracking is a classic search method used for problem solving with constraints, which allows you to return to a previous state (backtrack) if the path you were looking for does not lead to a solution.

Backtracking algorithms are recursive by nature (you can Google the definition of recursion and look for the easter egg), and have been used for solving problems such as Sudokus or crossword puzzles since the 1950s.

Defining the problem

Our colleague, José Leiva, taught us how we could maximise the benefit of accurately predicting returns over a period of time using the Viterbi algorithm. However, markets often give us a reality check and show us that, in most situations, we have to settle for an estimate of returns in a short period of time. This forces us to follow a myopic strategy under constraining scenarios.

The problem consists of making a weight distribution over the different portfolio assets, maximising the asset weights with greater estimation and respecting the constraints imposed by the manager. For this problem, we will define 4 assets with maximum and minimum weight restrictions per asset, and a total turnover constraint at portfolio level. We will establish a minimum investment of 0% and a maximum investment of 35% for all assets, with a maximum total turnover of 20%.

How do we solve this problem using Backtracking?

One of the main advantages of backtracking is its easy implementation. This simplicity is, in turn, its main disadvantage, since it is computationally very expensive to come up with a solution if any pruning procedure is carried out (which we will talk about later).

This algorithm focuses on searching for different solutions that we will call states. Each state represents a possible combination of asset weights and the restrictions that we define are the ones that decide whether a state is a valid solution or not. Apart from the restrictions we have previously defined, one restriction we must add is that all weights add up to 1.

We can think of this search as a tree (a data structure that we have already used multiple times) in which each node is a state. This tree has as many search levels as assets in our portfolio, and in each state belonging to a level, the asset’s weight in that level is modified. In this way, if we have in our portfolio assets A, B, C and D, in each state of level one, the weights of asset A will vary; in level two the weights of asset B and so on.

The first decision we have to make, when fine-tuning our algorithm, is to determine how exhaustive we want the search to be. The more detail we need, the longer it takes to find a solution. It is not the same to vary the weights from 10% to 10% than from 0.01% to 0.01% and the number of possible states increases exponentially as we increase the search range. For this example, we will set the variation of the weights to 1%.

Let’s get down to business

If we have understood the nature of the problem well, we will have realised that we are faced with a very broad search, in which the first solution we find would not necessarily be the optimal one we are looking for.

A first approach to reduce the number of possible states would be to remove those ones that breach any constraint from the search range of each asset. In this way, for each asset, we could remove all weights greater than 35% because they fail to comply with the maximum weight restriction. If we assume that all the assets start with the same weight, the total turnover restriction disables all the weights that are out of range [0.05, 0.55]. In this way, the search range for each asset would be as follows:

This significantly reduces the number of initial weights available for each state. On the other hand, we could solve the problem of optimisation by sorting the available asset weights from highest to lowest and placing the assets with the highest estimation at the highest levels of the tree. This way, the search tree would look like this:

If we start looking from top to bottom and from left to right (Depth-first search), we would always start by trying to assign more weight to assets with higher estimation. If we don’t find a solution, we would start to reduce possible weight to assets with lower estimation. The first solution found will be the optimal one, since it will be the one that gives more weight to the assets with the greatest estimation, respecting the constraints. We already have everything we need to start our search.

Evaluating the results

Launching our algorithm with the above considerations, we can see its course through the search space in the following graph:

The solution proposed by our algorithm is the following distribution:

To find the solution, we have had to go through a total of 10274 states. Depending on our computer, we could use this time to go for a glass of water in between. In a universe with four assets, this can be feasible, but the reality is that we usually look for a much wider universe distribution and this results in unacceptable waiting times when we run a simulation.

This is why the concept of “pruning” is so important in this type of algorithm, where there’s a need to reduce the number of branches to reduce the search space.

Pruning our search tree

Increasing the number of restrictions increases the pruning possibilities in our tree. We will take the most basic restriction: All weights must add to 1.

The nature of our algorithm tells us that if we dip to a lower level, we will add more weight to the assets in our portfolio, increasing the total amount. Therefore, we can discard all branches that start from states whose weight is greater than or equal to one. By implementing this improvement we obtain the following evolution:

The number of visited states has dropped to 3753 with this small optimisation. We can go one step further and say that if we are at the last level, we will only consider as candidate states those states whose total weight of all assets is exactly 1. This second pruning leads to the following evolution:

This time, the number of states visited has been 515.

Conclusion

As we saw with the Viterbi algorithm, exploring an entire set of solutions can be very expensive if we don’t reduce our search space. The approach to this problem using backtracking allows us to add all the restrictions that are convenient: portfolio volatility, maximum and minimum turnover per asset, minimum time in portfolio… If you are interested in seeing the code used in this post, you can find it in this notebook. Happy searching!