Mixed Integer Linear Programming for Allocation of Collateral within Securities Lending

Abstract: A mixed integer linear programming formulation is used to solve the problem of allocating assets from a bank to its counterparties as collateral within securities lending. The aim of the optimisation is to reduce the cost of allocated collateral, which is broken down into the components opportunity cost, counterparty risk cost and triparty cost. A solution consists of transactions to carry out to improve the allocation cost, each transaction consisting of sending a quantity of some asset from a portfolio to the bank or from the bank to some portfolio. The optimisation process is split into subproblems to separate obvious transactions from more complex optimisations. The reduction of each cost component is examined for all the subproblems. Two subproblems transform an initial collateral allocation into a feasible one which is then improved by the optimisation. Decreasing opportunity cost is shown to be an easier task than decreasing counterparty risk and triparty costs since the latter costs require a comparatively large number of transactions. The optimisation is run several times in a row, performing the suggested transactions after each solved iteration. The cost reduction of k optimisation iterations with 10 transactions per iteration is shown to be similar to the cost reduction of 1 optimisation iteration with 10k transactions. The solution time increases heavily with the number of iterations. The suggested transactions may need to be performed in a certain order. A precedence constrained problem takes this into account. The problem is large and the execution time is slow if a limit is imposed on the number of allowed transactions. A strategic selection of portfolios can limit the number of suggested transactions and still reach a solution which comes close to the optimal one. This can also be done by requiring that all suggested transactions must reduce the cost by a minimum amount. The final model is ready to be used in a semi-automatic fashion, where transactions are verified by a human who checks if they are sound. A fully automated process requires further testing on historical and recent data.