OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

The approach we follow in dealing with network flow is not common in
the textbooks. Essentially we adopt a *unified* approach to a number
of different problems whereas most of the textbooks (for historical reasons)
treat these problems *separately*.

We shall first consider the general network flow problem and then show how a number of common practical problems are variants of this general problem.

To illustrate the general network flow problem consider the diagram
below where we have a number of *sources* of material and a number
of *sinks* (or demand points) for material. Typically each source
has an upper limit on the amount of material it can supply and each demand
point has an associated number indicating the amount of material it needs.

Between the sources and the sinks are intermediate *nodes* through
which material can be shipped (flows) to other intermediate nodes or to
the sinks. We also have *arcs* (essentially directed from the sources
to the sinks) where each arc has associated with it:

- an upper limit (or
*capacity*) on the amount of material which can flow down the arc; and - a
*cost*per unit of material sent down the arc.

Hence the problem is one of deciding how to supply the sinks from the
sources at minimum cost. This problem is known as the *minimum cost network
flow problem*.

Ford and Fulkerson developed an algorithm (called the "out of kilter" algorithm) for this problem in the early 1960's and this original algorithm has been revised and improved since then. Algorithms for minimum cost network flow are widely available on computers. The minimum cost network flow problem is a linear program with a special structure. As such specialised algorithms can solve very large problems.

Any problem which can be represented in the form of a picture such as shown above can be regarded as a minimum cost network flow problem (and hence easily solved).

Below we consider the practical problems which can be regarded as minimum cost network flow problems.

Consider the table below which shows the cost of allocating 5 jobs to 5 machines.

Machine A B C D E Job 1 22 30 26 16 25 2 27 29 28 20 32 3 33 25 21 29 23 4 24 24 30 19 26 5 30 33 32 37 31

Which jobs should be allocated to which machines so as to minimise the total cost?

It is clear that this problem can be viewed as a minimum cost network flow problem as below where:

- each source (job) can supply one unit
- each sink (machine) demands one unit
- each arc has a capacity of one unit of flow and a cost taken from the table above.

Problems of this type are called *assignment* problems since they
involve the assignment of n (in this case n=5) distinct entities to another
n distinct entities. For example in the area of production planning we
might be interested in assigning operators to machines, or in assigning
operators to jobs, or (as above) in assigning jobs to machines.

This problem was solved using the package, the input being shown below.

The output is shown below.

Three factories can supply any of six customers with a particular product. The demand for this product from each of the customers 1, 2, 3, 4, 5 and 6 is 40, 35, 25, 20, 60 and 30 tons respectively. Maximum production at factories A, B and C is 60, 70 and 80 tons respectively. The variable production cost per ton is 11.3, 11.0 and 10.8 (£) at factories A, B and C respectively and the transportation cost per ton from each factory to each customer is as shown below.

Transportation cost (£) per ton to customer 1 2 3 4 5 6 From factory A 1.5 1.8 3.1 4.2 2.5 3.0 B 2.2 4.6 3.5 2.4 1.8 4.0 C 3.6 4.8 1.6 4.4 2.8 2.0

Determine the quantity of product to be supplied from each factory to each customer so as to minimise total costs.

In order to treat this problem as a minimum cost network flow problem
we need first to find the cost for each factory/customer pair of producing
*and* transporting one ton from the factory to the customer. These
costs are obtained by adding the variable production costs to the transportation
costs and are tabulated below.

Production and transportation cost (£) per ton to customer 1 2 3 4 5 6 From factory A 12.8 13.1 14.4 15.5 13.8 14.3 B 13.2 15.6 14.5 13.4 12.8 15.0 C 14.4 15.6 12.4 15.2 13.6 12.8

It is now clear that this problem can be viewed as a minimum cost network flow problem as below where:

- each source (factory) can supply as much as the factory can produce
- each sink (customer) has demand equal to the associated customer demand
- each arc has a capacity equal to the demand of the customer it goes to and a cost taken from the table above of combined production and transportation costs.

Problems of this type are called *transportation* problems and
typically involve minimising the cost of transporting goods from production
facilities to customers.

Note here that:

- imposing a limit on the amount supplied from a particular factory to a particular customer is merely a matter of setting an arc capacity appropriately
- arcs can be deleted to ensure that particular factories do not supply particular customers.

This problem was solved using the package, the input being shown below.

The output is shown below.

Note here that customer 1 receives shipments from both A and B. This is normal in solving transportation problems. If we wish each customer to be sourced (supplied) from just a single factory then the problem becomes a much more difficult problem (in fact it becomes an integer programming problem).

Frequently goods are not transported directly from factories to customers but are shipped (transhipped) via intermediate locations (such as depots or warehouses). For example suppose we take the problem we considered above and add the additional information that a new depot has become available where:

- the depot has a cost per ton of throughput of £0.7
- the cost of shipping from factories A, B and C to the depot is 0.1, 0.3 and 0.7 (£ per ton) respectively
- the cost of shipping from the depot to customers 1, 2, 3, 4, 5 and 6 is 0.7, 0.9, 1.1, 0.8, 0.6 and 0.9 (£ per ton) respectively.

This depot can be incorporated into the network flow representation as below .

Here we have *added* to the graph shown before:

- two new nodes (labelled D
_{1}and D_{2}below) - D_{1}representing goods in to the depot (the "front door") and D_{2}representing goods out of the depot (the "back door") - an arc between D
_{1}and D_{2}with capacity equal to the total factory capacity (representing the maximum amount of throughput that can reach the depot from the factories) and cost 0.7 (representing the cost of throughput) - arcs from the sources (factories) to D
_{1}of capacity equal to the factory production capacity and cost equal to the combined production and transportation (factory to depot) cost, i.e. - arc A,D
_{1}capacity 60 cost 11.3 + 0.1 = 11.4

arc B,D_{1}capacity 70 cost 11.0 + 0.3 = 11.3

arc C,D_{1}capacity 80 cost 10.8 + 0.7 = 11.5 - arcs from D
_{2}to the customers of capacity equal to the customer demand and cost equal to the cost of shipping from the depot to the customer, i.e. - arc D
_{2},1 capacity 40 cost 0.7

arc D_{2},2 capacity 35 cost 0.9

arc D_{2},3 capacity 25 cost 1.1

arc D_{2},4 capacity 20 cost 0.8

arc D_{2},5 capacity 60 cost 0.6

arc D_{2},6 capacity 30 cost 0.9

Problems of this type are called *transhipment* problems since
they involve the transhipment of goods via intermediate locations rather
than directly from factories to customers.

This problem was solved using the package. The input is shown below. Note here that this problem is entered as a network flow problem.

The output is shown below.

It can be seen that 155 units flows through the depot (from D1 to D2). If we (for example) restrict that to say 100 units (because the depot cannot cope with more than that) we merely need to edit the Flows Bounds in the package appropriately. The solution with this capacity limit imposed is shown below.

As both the transportation and transhipment problems are (computationally) easy to solve "what-if" questions can be asked and answered relatively rapidly, both at the strategic level and at the tactical level. For example:

- what if the capacity of a factory is substantially increased, how will this affect the overall production and transportation cost?

Increasing factory capacity is a strategic decision and presumably an increase in factory capacity reduces the variable costs involved in production and transportation. Hence this variable cost reduction should be set against the capital required to increase the factory capacity (a typical investment decision, balance cost savings against capital investment)

- any tactical changes e.g. in arc costs/capacities or in customer demands can be easily incorporated and the problem resolved.

Both the transportation problem and the transhipment problem are quite widely used for planning bulk distribution, especially in the USA where the (road) distances travelled are large.

A variation on the general minimum cost network flow problem is the problem of finding the maximum flow that can be sent between a single source and a single sink (as in the diagram below) where each arc has a capacity (shown in the diagram below next to the arc) which limits the amount of flow which can be sent down it (there being no cost associated with using the arc).

An algorithm for solving this problem was developed by Ford and Fulkerson
in the mid 1950's (i.e. before they developed their "out of kilter"
algorithm for solving the minimum cost network flow problem). Problems
of this type are called *maximum flow* problems and appear, for example,
in communication network planning and pipeline (gas/oil/water) network
planning.

The problem shown above was solved using the package, the input being shown below.

The output is shown below.

We can see from that output that the maximum flow that can be sent between the source and the sink is 7.

Note here that there is a theorem (**the min-cut max-flow theorem**)
that says that the maximum flow possible is equal to the capacity of the
minimum cut disconnecting the source and the sink (i.e. a cut that disconnects
source and sink and has the minimum (smallest) possible capacity over all
such cuts). In the above problem the min-cut corresponds to the arcs (1,2),
(3,2), (3,6) and (4,5) - removing these disconnects the source and the
sink (see below) and their total capacity is 7.

One other area in which network flow is extensively used is in the management of foreign exchange dealings for banks, large companies, etc. To illustrate this consider the (simple) problem shown below where there are 4 currencies (£, Swiss franc, US dollar and Japanese Yen).

On the international money market rates are constantly available for
converting between any pair of these (commonly traded) currencies and these
rates can be represented by the matrix (r_{ij}) where

r_{ij} = the amount of currency j obtained in return for one
unit of currency i

For example the amount of Yen (currency 4) obtained in return for one
£ (currency 1) is r_{14}.

Consider first a simple deal in which we convert one £ to Yen
and back again. We will end up with £[r_{14}(r_{41})]
(ignoring transaction costs). The key point is that almost always r_{14}(r_{41})
is not equal to 1. This arises principally because rates are only quoted
to a certain number of decimal places.

Whilst we would expect r_{14}(r_{41}) < 1 (i.e. we
lose money on the deal) it is not so clear that a deal representing a complex
series of transactions will necessarily be unprofitable (e.g. would converting
one £ to US dollars to Swiss francs to Yen to £ - yielding
£[r_{13}r_{32}r_{24}r_{41} ] necessarily
be unprofitable?)

In fact, given that a large number of currencies are commonly traded, that rapid changes in rates occur, that rates are decided by people and are quoted to a certain number of decimal places it is almost inevitable that profitable deals can (occasionally) be found.

Foreign exchange transactions (such as those above) can be modelled
as a *network flow with gains* problem and algorithms exist which
enable profitable deals to be identified within seconds (necessary when
rates are constantly changing). Note too the number of currencies that
are commonly traded, think of the major trading blocs around the world
for example:

- Europe
- Japan
- North America
- South America
- Middle East
- Far East
- Australasia

Whilst the above has considered just the *spot* market (converting
currency immediately) the same basic approach can be extended to have a
time dimension, including both the *forward* market (converting currency
at a given point in the future) and deposits (depositing currency for a
certain time to gain interest).

To include the time dimension we simply repeat the same picture shown
above for *each* time period and then we have that the arcs between
currency nodes in different time periods naturally represent forward transactions
and deposits. This is shown below.

Note that there can be two types of arcs in the above problem:

- these which are effectively
**risk-free**; - and those which are not.

For example a risk-free arc might be investing £ in the current time period (period 1) for a fixed time in an fixed interest instrument (issued by a reputable issuer). A risky arc might be changing money on the spot market in period 2 (as we do not yet know what the spot market rate in period 2 will be). Apart from pure "speculation" to make money, such models can be used, for example, to balance the currency holdings of a company so as to meet its future requirements for foreign currency at minimum cost.

Note here that problems concerned with the management of foreign exchange
are often referred to as *arbitrage* problems.

Note too that the opportunities for profitable speculation diminish as more and more players in the foreign exchange market have powerful computers and sophisticated software at their fingertips.

Commercial computer codes for the minimum cost network flow problem are readily available and able to solve large problems. In solving such problems it is the number of arcs which (essentially) determines the solution time.

Computational results presented in the literature indicate that problems involving thousands of arcs can be solved within seconds (on a powerful computer).

For example I have solved transportation problems involving 10 sources and 1000 demand points (10,000 arcs) in about 5 seconds.