next up previous
Next: Conclusions Up: Network Optimization for Consultants Previous: Unifying Model: Minimum Cost

Generalized Networks

The final model I would like to familiarize you with is called the generalized network model. In this model, there may be gains or loses as flow goes along an arc. Each arc has a multiplier to represent these gains and loses. For instance, if 3 units of flow enter an arc with a multiplier of .5, then 1.5 unit of flow exit the arc. Such a model can still be represented as a linear program, and there are specialized techniques that can solve such models much faster than linear programming (but a bit slower than regular network flow problems). The optimal solution need not be integer however.

The standard example of a generalized network is in power generation: as electricty moves over wires, there is some unavoidable loss along the way. This loss is represented as a mutliplier. Here is another example on how generalized networks might be used:

Consider the world's currency market. Given two currencies, say the Yen and the USDollar, there is an exchange rate between them (currently about 110 Yen to the Dollar). It is axiomatic of a arbitrage-free market that there is no method of converting, say, a Dollar to Yen then to Deutsch Marks, to Francs, the Poinds, and to Dollars so that you end up with more than a dollar. How would you recognize when there is an arbitrage possiblity?

For this model, we use a node to represent each currency. An arc between currency i and j gives the exchange rate from i to j. We begin with a single dollar and which to send flow through the network and maximize the amount we generate back at the USDollar node. This can be drawn as in figure 4.

   figure174
Figure 4: Financial Exchange Network

These are actual trades made on November 10, 1996. It is not obvious, but the Dollar-Yen-Mark-Dollar conversion actually makes $0.002. How would you formulate a linear program to recognize this?


next up previous
Next: Conclusions Up: Network Optimization for Consultants Previous: Unifying Model: Minimum Cost

Michael A. Trick
Mon Nov 11 15:13:01 EST 1996