The following file shows how Linear Programming can be used to detect arbitrage in a network of foreign exchange rates.

In [1]:
from pyomo.environ import *
from pyomo.opt import *
opt = solvers.SolverFactory("glpk")

We consider eight different currencies and selected exchange rates which were obtained from http://www.xe.com/currencyconverter/ on March 10, 2016.

In [2]:
C = ['EUR', 'USD', 'CNY', 'AUD', 'BRL', 'GBP', 'JPY', 'RUB']

R = {('EUR','USD'):1.11147,  
     ('USD','CNY'):6.50135,   
     ('CNY','AUD'):0.204864, 
     ('AUD','BRL'):2.73332,  
     ('BRL','GBP'):0.192399, 
     ('BRL','CNY'):1.78939,  
     ('GBP','EUR'):1.28408,  
     ('GBP','JPY'):162.818,   
     ('JPY','RUB'):0.612633, 
     ('JPY','AUD'):0.0116600,
     ('RUB','EUR'):0.0129012,
     ('BRL','USD'):0.275413, 
     ('RUB','BRL'):0.0522003}

A = list(R.keys()) # list of arcs in the transaction network

The decision variables are the value $v_i$ of each currency $i \in C$ and the arbitrage $a_{ij}$ on each possible transaction $(i,j) \in A$.

In [3]:
model = ConcreteModel()
model.v = Var(C, within=NonNegativeReals)
model.a = Var(A, within=NonNegativeReals)

We fix the value of the Euro to 1 so that the value of all other currencies will be computed relative to the Euro.

In [4]:
model.anchor = Constraint(expr =  model.v['EUR']==1.0)

Arbitrage arises when the value resulting from a transaction $v_i\,r_{ij}$ is larger than the value of the target currency $v_j$ so that the transaction is generating extra value, the arbitrage $a_{ij}$. Thus, the arbitrage constraint reads $$ v_i \, r_{ij} - a_{ij} \leq v_j \,. $$

In [5]:
def arbitrage_rule(model, s, d):
    return model.v[s]*R[(s,d)]-model.a[(s,d)] <= model.v[d]
    
model.arbitrage = Constraint(A, rule=arbitrage_rule)

The true values $v_i$ of the currencies $i\in C$ are those for which the total arbitrage in the system is minimal. Note that it would be more natural to minimize arbitrage relative to the value of the target currency, i.e. to minimize the sum of $a_{ij}/v_j$, but this would lead to a nonlinear programming problem, so we choose to simply minimize the total absolute arbitrage.

In [6]:
model.minarbitrage = Objective(expr = sum(model.a[t] for t in A), sense=minimize)

Now we solve the model. The currency values we obtain are pretty close to the ECB reference rates for that day.

In [7]:
results = opt.solve(model)
model.v.get_values()
Out[7]:
{'AUD': 1.47742623567244,
 'BRL': 4.0382786784882,
 'CNY': 7.2260554845,
 'EUR': 1.0,
 'GBP': 0.775569076519022,
 'JPY': 126.276605900674,
 'RUB': 77.3612159027477,
 'USD': 1.11147}

And we find a small amount of arbitrage on certain network arcs. Not that this only means that there is arbitrage along some cycle involving this arc.

In [8]:
model.a.get_values()
Out[8]:
{('AUD', 'BRL'): 0.0,
 ('BRL', 'CNY'): 0.0,
 ('BRL', 'GBP'): 0.00139170294342888,
 ('BRL', 'USD'): 0.000724445678470796,
 ('CNY', 'AUD'): 0.00293239510416575,
 ('EUR', 'USD'): 0.0,
 ('GBP', 'EUR'): 0.0,
 ('GBP', 'JPY'): 0.0,
 ('JPY', 'AUD'): 0.0,
 ('JPY', 'RUB'): 0.0,
 ('RUB', 'BRL'): 0.0,
 ('RUB', 'EUR'): 0.0,
 ('USD', 'CNY'): 0.0}