# Optimal currency conversion Linear Programming

I have a question about Ex 1.11 of "Linear Optimization" by Bertsimas, Tsitsiklis:

Suppose that there are $$N$$ available currencies, and assume that one unit of currency $$i$$ can be exchanged for $$r_{ij}$$ units of currency $$j$$. (Naturally, we assume that $$r_{ij} > 0$$.) There also certain regulations that impose a limit $$u_i$$ on the total amount of currency $$i$$ that can be exchanged on any given day. Suppose that we start with $$B$$ units of currency $$1$$ and that we would like to maximize the number of units of currency $$N$$ that we end up with at the end of the day, through a sequence of currency transactions. Provide a linear programming formulation of this problem. Assume that for any sequence $$i_1, \dots, i_k$$ of currencies, we have $$r_{i_1 i_2} r_{i_2 i_3} \dots r_{i_{k-1} i_k} r_{i_k i_1} \leq 1$$, which means that wealth cannot be multiplied by going through a cycle of currencies.

I think I am probably misunderstanding the question, but we have B units of currency 1 at the start and at most $$u_1$$ of currency 1 can be exchanged so I think the most of currency N we can get is $$min(u_1, B)*r_{1N}$$. This is because if B > $$u_1$$ then at most $$u_1$$ can be exchanged and there is no point in converting to any other intermediate currency and then currency N because this leads to at most the same amount of currency N as without converting to intermediate currencies, as otherwise we are profitting by arbitrage. And if B <= $$u_1$$ then we convert all B units of currency 1 to N in a single transaction. Can anyone tell me if I am missing something?

The idea is that by converting via one or more intermediate currencies, you could end up with a larger amount of the target currency N than you would get if you were to convert directly from currency 1 to currency N. If there was no limit $$u_i$$ then there would exist exactly one chain that maximizes the total amount of currency N and you would use your full budget B to follow this chain. But because there's a limit you will have to split the money over multiple chains including chains with lower profits.

Hint: there can never be more than N conversions in a single chain.

• Why at most N conversions?
– prubin
Nov 17 at 15:55
• @prubin there are only $N$ currencies available. Let's say $N=3$. Then the longest chain would be $i_1$ -> $i_2$ -> $i_3$. A longer chain would involve converting back to an earlier currency, e.g $i_1$ -> $i_2$ -> $i_1$-> $i_3$. But that would imply that I can infinitely repeat this cycle and continue to increase my value. Perhaps I should have written 'the longest chain contains at most N conversions', because technically you could split the budget and have several parallel flows of money, e.g. $i_1$->$i_3$ and $i_1$->$i_2$->$i_3$ if $u_2$ = $B/2$, thereby having 4>N conversions. Nov 17 at 16:38
• Suppose that $N=6,$ $B=10,$ and $r_{ij}=1$ for $(i,j)\in\left\{ (1,2),(1,3),(2,4),(2,5),(3,5),(4,6),(5,6)\right\}$ and $r_{ij}=\epsilon$ otherwise, where $\epsilon$ is very close to 0. The best we can hope for is to end up with 10 units of currency 6. Suppose further that $u=(10,5,5,1,9,\infty)$, noting that $u_{6}$ is irrelevant. ...
– prubin
Nov 18 at 19:50
• ... The optimal solution is $1\rightarrow2:5,$ $1\rightarrow3:5,$ $2\rightarrow4:1,$ $2\rightarrow5:4,$ $3\rightarrow5:5,$ $4\rightarrow6:1$ and $5\rightarrow6:9$, where $i\rightarrow j:k$ means convert $k$ units of currency $i$ into currency $j$ (with exchange ratio 1 to 1). That has 7 transfers.
– prubin
Nov 18 at 20:01