Books in black and white
 Main menu Share a book About us Home
 Books Biology Business Chemistry Computers Culture Economics Fiction Games Guide History Management Mathematical Medicine Mental Fitnes Physics Psychology Scince Sport Technics
Ads

# Combinatorial Optimization - Cristofides N.

Cristofides N. Combinatorial Optimization - Wiley publishing , 2012. - 212 p.
Download (direct link): čüombinatorialoptimi2012.pdf Previous << 1 .. 148 149 150 151 152 153 < 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 DollarŚ5 m; SterlingŚ1 m; MarkŚ 5 m; French FrancŚ15 m; Swiss FrancŚ10m. 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), Previous << 1 .. 148 149 150 151 152 153 < 154 > 155 .. 156 >> Next 