I'm trying to follow the syllabus of 6-251j at MIT OCW and need to understand whether I'm doing fine with the exercises.
This is what Ex. 1.11 says:
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.
At first, this seems to be a quirky version of a minimal cost flow problem, so we could construct something like the following.
Let $x_i$ for $i=1..N$ be the total amount of currency $i$ that goes through our hands this day. Let $y_{ij}$ for $i,j=1..N$ be the total amount of currency $i$ exchanged to currency $j$ this day. Then, we want to maximize $x_N$, under constraints that
- $x_1 = B$ (start with $B$ units of currency 1);
- $\sum_{j=1}^N y_{ij} = x_i$ for $i=1..N\!-\!1$ (all the amount of currencies 1 to $N\!-\!1$ is traded away);
- $x_j = \sum_{i=1}^{N}r_{ij}y_{ij}$ for $j=2..N$ (currencies 2 to $N$ are gained by buying them);
- $y_{Nj} = 0$ for $j=1..N$ (do not trade away currency $N$);
- $\sum_{j=1}^{N}y_{ij} \leq u_i$ for $i=1..N$ (obey the laws);
- $y_{ij} \geq 0$ (common sense).
The problem with this formulation is that it admits spurious cycles. E.g., we may decide to exchange 1 unit of currency 'a' into 1 unit of currency 'b'; 1000 units of currency 'b' into 1000 units of currency 'c'; 999 units of 'c' back into 999 units of 'b; and finally 1 unit of 'c' into 1 unit of 'd'. Minimal cost flow problem does not have this issue as such cycles add cost, and a solution with a spurious cycle would not be optimal.
Still I would claim that solving this problem yields genuine maximal amount of currency $N$. This is due to constraint 4 saying that we should not trade away currency $N$. Is this claim correct?
Now, given a genuine maximal $x_N$, we can construct a second LP problem to find such $y_{ij}$ that would produce this $x_N$ in the end and also minimize the total amount of currency exchanged ($\sum y_{ij}$). This does not have to be an LP problem though, we could come up with another way to find genuine $y_{ij}$, e.g., by building the tree of transactions starting from currency 1 and ignoring any attempts to exchange into a currency that is an ancestor in the tree.
Still I have a feeling that I'm not on the right track. Do you know a better (or a canonical) LP formulation of this problem?
