How we, at Vivriti Capital, solved a product requirement using Linear Programming

Hello World! Nitish, this side. Currently, I work as a Software Development Engineer at Vivriti Capital. Today, I will discuss an interesting problem we encountered while developing our product and how we solved it using Linear programming. So, Let’s get started …

First a brief introduction

We, at Vivriti Capital, are in the business of debt financing. While we deal in several debt products, complex structured finance products such as Pass-Through Certificates (PTCs) and Direct Assignments (DAs) constitute most of our business. In both cases, we bundle together a set of retails loans and sell as an aggregated set of cash flows.

Loaning money is an easy task but collecting it back is another story and not many companies can be very good at it. Macro and microeconomic events and/or regulatory changes can also lead to disturbances. Investors in such products seek to reduce risk through various means including diversifying the geography of the loans they buy, eliminating loans from branches with a high PAR (Portfolio At Risk) amongst others.

The Pool concentration criterion

One such risk reduction mechanism is to reduce the concentration of loans (limit exposure) in a pool from a single branch, district and/or state. This allows investors to limit the risk to their total investment if there is a localized disruption such as the recent Kerala floods. Building an algorithm to seek to meet such a goal in one dimension (eg. reduce state concentration) is an easy task. Seeking to do this in three dimensions simultaneously is a tad harder and interesting problem to solve. I outline how we achieve this in this article.

Problem Statement

Problem: Given a pool of N loans with different outstanding principals, where each loan in the pool belongs to some state, district, and branch. Our problem is to structure the pool in such a way that we maintain x% of state concentration i.e. no state in the pool has more than x% contribution to the total principal, y% District concentration and z% of Branch concentration.

Constraint: Obviously, we have to remove certain loans from the pool but we also want to do it in a way that we maximize the total pool size and hence, can securitize a bigger pool size.

Our Approach to Solve it

We first tried to deal with the problem in a single dimension i.e. in this case just balancing state concentration. We figured out a greedy algorithm that was the optimal solution for a single dimension :

Our Algorithm :

Step 1: Maintain a Priority Queue (P) containing all distinct states (priority-key being the aggregated concentration ratio)

Step 2: Poll out the leading state P and remove the exact principal to satisfy the x% of concentration. We did this by using the below expression :

(p-d)/(t-d) = x/100

p = total principal of the leading state

d = principal to be deducted

t = total principal of the pool

Step 3: Update the Priority Queue P with the new principal.

Step 4: Repeat step 3&4 till the concentration of leading state is satisfied.

Voila! we solved it but when combined it with all other dimensions of aggregations it will mess up. Though we can execute the above algorithm iteratively for all the dimensions until everything gets balanced, this is bound to be non-optimal depending on the order in which we proceed and the distribution of the loans that is we may end up removing too many loans. In the worst case, we might end up removing all the loans. Since our goal is to maximize the pool size but limiting the risk, we couldn’t use this approach.

Bringing the boss: Linear Programming

Alright, let’s write some mathematical inequalities to represent the concentration satisfaction problem:

Consider 5 loans with principals p1, p2, p3, p4, p5. Each of these loans belongs to some state, district, and branch. Our problem is to maintain the state, district and branch concentrations by x, y, and z percentage respectively.

For simplicity consider the below distribution (loans are named p1, p2…):

p1, p2, and p3 belongs to state 1, district 1 and branch1

p4 and p5 belongs to state 2, district 2 and branch 2

Now we define a function f(x1,x2,…,x5) as

Objective Function

We call the above function f() as Objective Function, where x1, x2, … , x5 are factor variables.

Now, let’s represent the concentration constraints :

inequality constraints

Wait, we are missing one more constraint. This is because we have only options either choose the loan (multiply factor 1) or remove the loan (multiply factor 0) and hence, the constraint :

variable scope constraint

Now, we will call a black box and pass him our objective function f() along with the inequality constraints and the variable scope constraint as listed above. This black box then accepts our objective function along the constraints and returns a state {v1, v2, v3,…, v5 } corresponding the value of x1, x2, x3, … , x5 which when put in our objective function maximizes the output with the subject to the fed constraints.

This Black Box is nothing but an LP Solver and returns us a <vector> solution. In our case, as we deal with integer LP problem, So it returns us a binary vector like <0, 1, 1, 0, 1> denoting the multiple factors. Zero means removing the corresponding loan and one means taking the specific loan.

The worst case Time Complexity of LP Solver is exponential as it performs (n+m)C(n) iterations, n being the number of variables and m is the number of constraints. But in real life cases, it performs a lot better.

Takeaways from our experience

One should not only look at the worst time complexity when going for a solution. It depends on your use case. It could be the case that your use case never feds input that results in the worst case performance of your algorithm.

Stay tuned to our channel. Next time we will drop some light on our black box and see how an LP Solver works.