# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**154**> 155 .. 156 >> Next

Further, we will take the maximum amount qll00 of a currency i that can be sold spot for any other currency j without affecting the above exchange rates to be given by: for i representing Dollar5 m; Sterling1 m; Mark 5 m; French Franc15 m; Swiss Franc10m. Thus qlj00 = 5m, / = 2,..., 5, etc.

We require to find the maximum amount of dollars that can be generated by circulating currencies within the spot market and the optimum transactions involved.

By applying the algorithm for flows in graphs with arc gains (Christofides, 1975) to the complete five-vertex graph with arc gains as shown in Table 15.1, arc capacities as given above, and s = t = x20, the optimum flow pattern is found and is shown graphically in Figure 15.1.

The optimum set of transactions then involves seven deals as follows:

Sell$ 3 109 646 Buy Fr 15 000 000

Sell Fr 15 000 000 Buy DM 8 133 000

Sell DM 5 000 000 Buy Sw Fr 5 878 000

Sell DM 3133 000 Buy ? 513 812

Sell Sw Fr 3 475 254 Buy ? 486 188

Sell ? 1 000 000 Buy $ 2 342 500

Sell Sw Fr 2 402 746 Buy $ 786 899

Net inflow of $ 3 109 646 Net outflow of $ 3 129 399 Net gain of $ 19753 (i.e. 0.635% of input)

414 Nicos Christofides, Robin D. Hewins, and Gerald R. Salkin

19753

15.3.2 Model lor Arbitrage of Type A2

Let us suppose that only some subset of the currency nodes is

acceptable for the final currency holdings, but that the intermediate dealings can include the rest of the currencies.

Once again we form the graph G = {X, A, (p)} corresponding to the arbitrage problem (Figure 15.2). In addition we now introduce a reference vertex x0p and arcs (x,p, x0p) from every vertex x,p e S to x0p. The capacity of an arc (XjP, x0p) is set to /3lp, the maximum allowable final position of currency i that can be held at date p, and the gain gi0pp is the notional exchange rate for evaluation purposes.

Figure 15.2 Sink vertex arcs for type A2 arbitrage. O Vertices eS; vertices & S

Graph Theoretic Approaches to Foreign Exchange Operations

415

We can now set s = xkp, t = x0p, and what is required is the optimum s-to-r flow in this graph with input value ak, i.e. the input arc has capacity ak with gain value 1.

The arbitrage problem of type A2b can be transformed into a network flow problem in an exactly analogous way to that described above for the problem of type A2a.

15.3.3 Model for Arbitrage of Type A3

Where a holding of a set T s X of two or more currencies is to be changed to maximize the evaluation we introduce two extra vertices to the basic graph G = {X, A, (p)}; the reference vertex x0p = t and. a source vertex s. We also introduce arcs from s to every other vertex x,p e T and arcs from every xjp to x0p (Figure 15.3). If gi0pp is the notional exchange rate between a currency i and the reference for date p, set the gain of an arc (XjP, x0p) to g,opp and the gain of an arc (s, x,p) to g0j0p (where g0i0p is the present notional forward date p exchange rate from reference to currency i) for all vertices X(p e T.

If aLp is the position of currency i initially held for date p we set the capacity of arcs (s, XjP) to ajg0i0p. The capacity of arcs (x.p, x0p) is set to (3[p, where /3jp is the maximum allowable position of currency i for forward date p that can be held at the end of all the transactions.

Taking the inflow into s to be

asp ^ (^ip/goiOp)

the optimum flow pattern from s to t will then correspond to the optimum sequence of transactions, and the net outflow from t will be the evaluation of the new currency holding.

Figure 15.3 Network for type A3 arbitrage

416

Nicos Christofides, Robin D. Hewins, and Gerald R. Salkin

15.3.4 Models for Arbitrage of Types Bl, B2, B3

The problems Bl, B2, and B3 can be formulated in the same way as for types Al, A2, and A3 respectively. It is usual practice in the market to quote for forward v spot swops by simply quoting the difference (margin) in the spot and forward rates; the forward rate may therefore be at a premium or discount with respect to the spot rate (Einzig, 1969). It can be shown that it is irrelevant (to first order) exactly which spot rate we base the forward margin on and hence it is only the margin which is important in quoting for spot v forward swops. Consequently, we can assume that all forward margins quotations are based on the same, consistent (in that we assume no spot arbitrage possibilities) spot rate and hence treat the spot v forward arbitrage problems simply by considering the forward part in the same way as Types A above.

15.3.5 Models for Arbitrage of Types Cl, C2, C3

To permit spot v forward swop deals (the usual method of forward dealing) as well as outright spot and forward deals then we require several dummy nodes denoting the currency held temporarily as the result of a spot v forward swop deal. Thus, if we may convert currency i into currency j spot with a reverse transaction in the future we denote this by including an additional node xj p between the nodes x,0 and xip. Otherwise we construct two type A arbitrage network systems (one spot and one for the forward date) with connecting arcs between the corresponding nodes, the gains on which will be one plus the requisite interest rate, i.e. we have separate complete graphs {X, A, (0)} and (X', A', (p)} for the loan period date p and the nodes x,0, XjP are joined by arcs with gain 1 + 1, where /, is the p period placement rate of interest. These interest arcs will, in general, have an upper limit associated with them beyond which the requisite interest rates no longer hold (Aliber, 1969; Einzig, 1966). For the additional nodes we have giji0p = 1 + 1, (where I, is the p period placement rate of interest for currency j),

**154**> 155 .. 156 >> Next