# Assignment Problem Network Flow Algorithms

Here’s a problem: Your business assigns contractors to fulfill contracts. You look through your rosters and decide which contractors are available for a one month engagement and you look through your available contracts to see which of them are for one month long tasks. Given that you know how effectively each contractor can fulfill each contract, how do you assign contractors to maximize the overall effectiveness for that month?

This is an example of the assignment problem, and the problem can be solved with the classical Hungarian algorithm.

The Hungarian algorithm (also known as the Kuhn-Munkres algorithm) is a polynomial time algorithm that maximizes the weight matching in a weighted bipartite graph. Here, the contractors and the contracts can be modeled as a bipartite graph, with their effectiveness as the weights of the edges between the contractor and the contract nodes.

In this article, you will learn about an implementation of the Hungarian algorithm that uses the Edmonds-Karp algorithm to solve the linear assignment problem. You will also learn how the Edmonds-Karp algorithm is a slight modification of the Ford-Fulkerson method and how this modification is important.

## The Maximum Flow Problem

The maximum flow problem itself can be described informally as the problem of moving some fluid or gas through a network of pipes from a single source to a single terminal. This is done with an assumption that the pressure in the network is sufficient to ensure that the fluid or gas cannot linger in any length of pipe or pipe fitting (those places where different lengths of pipe meet).

By making certain changes to the graph, the assignment problem can be turned into a maximum flow problem.

## Preliminaries

The ideas needed to solve these problems arise in many mathematical and engineering disciplines, often similar concepts are known by different names and expressed in different ways (e.g., adjacency matrices and adjacency lists). Since these ideas are quite esoteric, choices are made regarding how generally these concepts will be defined for any given setting.

This article will not assume any prior knowledge beyond a little introductory set theory.

The implementations in this post represent the problems as directed graphs (digraph).

### DiGraphs

A digraph has two attributes, setOfNodes and setOfArcs. Both of these attributes are sets (unordered collections). In the code blocks on this post, I’m actually using Python’s frozenset, but that detail isn’t particularly important.

(Note: This, and all other code in this article, are written in Python 3.6.)

### Nodes

A node is composed of two attributes:

• : This represents any data object.

### Arcs

An arc is composed of three attributes:

• : This is a node, as defined above.

• : This is a node, as defined above.

• : This represents any data object.

The set of arcs in the digraph represents a binary relation on the nodes in the digraph. The existence of arc implies that a relationship exists between and .

In a directed graph (as opposed to an undirected graph), the existence of a relationship between and does not imply that a similar relationship between and exists.

This is because in an undirected graph, the relationship being expressed is not necessarily symmetric.

### DiGraphs

Nodes and arcs can be used to define a digraph, but for convenience, in the algorithms below, a digraph will be represented using as a dictionary.

Here’s a method that can convert the graph representation above into a dictionary representation similar to this one:

And here’s another one that converts it into a dictionary of dictionaries, another operation that will be useful:

When the article talks about a digraph as represented by a dictionary, it will mention to refer to it.

Sometimes it’s helpful to fetch a node from a digraph by it up through its (unique identifier):

In defining graphs, people sometimes use the terms node and vertex to refer to the same concept; the same is true of the terms arc and edge.

Two popular graph representations in Python are this one which uses dictionaries and another which uses objects to represent graphs. The representation in this post is somewhere in between these two commonly used representations.

This is my digraph representation. There are many like it, but this one is mine.

### Walks and Paths

Let be a finite sequence (ordered collection) of arcs in a digraph such that if is any arc in except for the last, and follows in the sequence, then there must be a node in such that .

Starting from the first arc in , and continuing until the last arc in , collect (in the order encountered) all nodes as defined above between each two consecutive arcs in . Label the ordered collection of nodes collected during this operation .

• If any node appears more than once in the sequence then call a Walk on digraph.

• Otherwise, call a path from to on digraph.

### Source Node

Call node a source node in digraph if is in and contains no arc such that .

### Terminal Node

Call node a terminal node in digraph if is in and contains no arc such that .

### Cuts and s-t Cuts

A cut of a connecteddigraph is a subset of arcs from which partitions the set of nodes in . is connected if every node in and has at least one arc in such that either or , but .

The definition above refers to a subset of arcs, but it can also define a partition of the nodes of .

For the functions and , is a node in set G.setOfNodes of digraph, and is a cut of :

Let be a cut of digraph.

is a cut of digraph if: is called an x-y cut if . When the node in a x-y cut is a source node and node in the x-y cut is a terminal node, then this cut is called a s-t cut.

### Flow Networks

You can use a digraph to represent a flow network.

Assign each node, where is in an that is a :

Assign each arc, where is in and that is a .

and are positivereal numbers.

and are also positive real numbers.

For every node node in :

Digraph now represents a flow network.

The flow of refers to the for all arcs in .

### Feasible Flows

Let digraph represent a flow network.

The flow network represented by has feasible flows if:

1. For every node in except for source nodes and terminal nodes : .

2. For every arc in : .

Condition 1 is called a conservation constraint.

Condition 2 is called a capacity constraint.

## Cut Capacity

The cut capacity of an s-t cut with source node and terminal node of a flow network represented by a digraph is:

## Minimum Capacity Cut

Let be an s-t cut of a flow network represented by a digraph.

is the minimum capacity cut of the flow network represented by if there is no other s-t cut in this flow network such that:

## Stripping the Flows Away

I would like to refer to the digraph that would be the result of taking a digraph and stripping away all the flow data from all the nodes in and also all the arcs in .

## Maximum Flow Problem

A flow network represented as a digraph, a source node in and a terminal node in , can represent a maximum flow problem if:

Label this representation:

Where , , and is an identifier for the problem instance.

## Maximum Flow Solution

Let represent a maximum flow problem. The solution to can be represented by a flow network represented as a digraph.

Digraph is a feasible solution to the maximum flow problem on input if:

1. .

2. is a flow network and has feasible flows.

If in addition to 1 and 2:

1. There can be no other flow network represented by digraph such that and .

Then is also an optimal solution to .

In other words a feasible maximum flow solution can be represented by a digraph, which:

1. Is identical to digraph of the corresponding maximum flow problem with the exception that the , and the of any of the nodes and arcs may be different.

2. Represents a flow network that has feasible flows.

And, it can represent an optimal maximum flow solution if additionally:

1. The for the node corresponding to the terminal node in the maximum flow problem is as large as possible (when conditions 1 and 2 are still satisfied).

If digraph represents a feasible maximum flow solution : this follows from the max flow, min cut theorem (discussed below). Informally, since is assumed to have feasible flows this means that flow can neither be ‘created’ (except at source node) nor ‘destroyed’ (except at terminal node) while crossing any (other) node (conservation constraints).

Since a maximum flow problem contains only a single source node and a single terminal node, all flow ‘created’ at must be ‘destroyed’ at or the flow network does not have feasible flows (the conservation constraint would have been violated).

Let digraph represent a feasible maximum flow solution; the value above is called the s-t Flow Value of .

Let:

This means that is a successor state of , which just means that is exacly like with the exception that the values of for arcs in may be different than for arcs in .

Here’s a visualization of a along with its associated . Each arc in the image has a label, these labels are , each node in the image has a label, and these labels are .

## s-t Cut Flow

Let represent a and let represent a cut of . The cut flow of is defined:

s-t cut flow is the sum of flows from the partition containing the source node to the partition containing the terminal node minus the sum of flows from the partition containing the terminal node to the partition containing the source node.

## Max Flow, Min Cut

Let represent a maximum flow problem and let the solution to be represented by a flow network represented as digraph.

Let be the minimum capacity cut of the flow network represented by .

Because in the maximum flow problem flow originates in only a single source node and terminates at a single terminal node and, because of the capacity constraints and the conservation constraints, we know that the all of the flow entering must cross any s-t cut, in particular it must cross . This means:

## Solving the Maximum Flow Problem

The basic idea for solving a maximum flow problem is to start with a maximum flow solution represented by digraph. Such a starting point can be . The task is then to use and by some greedy modification of the values of some arcs in to produce another maximum flow solution represented by digraph such that cannot still represent a flow network with feasible flows and . As long as this process continues, the quality () of the most recently encountered maximum flow solution () is better than any other maximum flow solution that has been found. If the process reaches a point that it knows that no other improvement is possible, the process can terminate and it will return the optimalmaximum flow solution.

The description above is general and skips many proofs such as whether such a process is possible or how long it may take, I’ll give a few more details and the algorithm.

## The Max Flow, Min Cut Theorem

From the book Flows in Networks by Ford and Fulkerson, the statement of the max flow, min cut theorem (Theorem 5.1) is:

For any network, the maximal flow value from to is equal to the minimum cut capacity of all cuts separating and .

Using the definitions in this post, that translates to:

The solution to a represented by a flow network represented as digraph is optimal if:

I like this proof of the theorem and Wikipedia has another one.

The max flow, min cut theorem is used to prove the correctness and completeness of the Ford-Fulkerson method.

I’ll also give a proof of the theorem in the section after augmenting paths.

## The Ford-Fulkerson Method and the Edmonds-Karp Algorithm

CLRS defines the Ford-Fulkerson method like so (section 26.2):

## Residual Graph

The Residual Graph of a flow network represented as the digraph can be represented as a digraph:

• returns the sum of for all arcs in the subset of where arc is in the subset if and .

• returns the sum of for all arcs in the subset of where arc is in the subset if and .

Briefly, the residual graph represents certain actions which can be performed on the digraph.

Each pair of nodes in of the flow network represented by digraph can generate 0, 1, or 2 arcs in the residual graph of .

1. The pair does not generate any arcs in if there is no arc in such that and .

2. The pair generates the arc in where represents an arc labeled a push flow arc from to if .

3. The pair generates the arc in where represents an arc labeled a pull flow arc from to if .

• Each push flow arc in represents the action of adding a total of flow to arcs in the subset of where arc is in the subset if and .

• Each pull flow arc in represents the action of subtracting a total of flow to arcs in the subset of where arc is in the subset if and .

Performing an individual push or pull action from on the applicable arcs in might generate a flow network without feasible flows because the capacity constraints or the conservation constraints might be violated in the generated flow network.

Here’s a visualization of the residual graph of the previous example visualization of a maximum flow solution, in the visualization each arc represents .

## Augmenting Path

Let be a max flow problem, and let be the residual graph of .

An augmenting path for is any path from to .

It turns out that an augmenting path can be applied to a max flow solution represented by digraph generating another max flow solution represented by digraph where if is not optimal.

Here’s how:

In the above, is some tolerance value for rounding the flow values in the network. This is to avoid cascading imprecision of floating point calculations. So, for example, I used to mean round to 10 significant digits.

Let , then represents a feasible max flow solution for . For the statement to be true, the flow network represented by must have feasible flows (not violate the capacity constraint or the conservation constraint.

Here’s why: In the method above, each node added to the new flow network represented by digraph is either an exact copy of a node from digraph or a node which has had the same number added to its as its . This means that the conservation constraint is satisfied in as long as it was satisfied in . The conservation constraint is satisfied because we explicitly check that any new arc in the network has ; thus, as long as the arcs from the set which were copied unmodified into do not violate the capacity constraint, then does not violate the capacity constraint.

It’s also true that if is not optimal.

Here’s why: For an augmenting path to exist in the digraph representation of the residual graph of a max flow problem then the last arc on must be a ‘push’ arc and it must have . An augmenting path is defined as one which terminates at the terminal node of the max flow problem for which it is an augmenting path. From the definition of the residual graph, it is clear that the last arc in an augmenting path on that residual graph must be a ‘push’ arc because any ‘pull’ arc in the augmenting path will have and from the definition of path. Additionally, from the definition of path, it is clear that the terminal node is only modified once by the method. Thus modifies exactly once and it increases the value of because the last arc in the must be the arc which causes the modification in during . From the definition of as it applies to ‘push’ arcs, the can only be increased, not decreased.

## Some Proofs from Sedgewick and Wayne

The book Algorithms, fourth edition by Robert Sedgewich and Kevin Wayne has some wonderful and short proofs (pages 892-894) that will be useful. I’ll recreate them here, though I’ll use language fitting in with previous definitions. My labels for the proofs are the same as in the Sedgewick book.

Proposition E: For any digraph representing a feasible maximum flow solution to a maximum flow problem, for any .

Proof: Let . Proposition E holds for directly from the definition of s-t flow value. Suppose that there we wish to move some node from the s-partition () and into the t-partition , to do so we need to change , which could change and invalidate proposition E. However, let’s see how the value of will change as we make this change. node is at equilibrium meaning that the sum of flow into node is equal to the sum of flow out of it (this is necessary for to represent a feasible solution). Notice that all flow which is part of the entering node enters it from the s-partition (flow entering node from the t-partition either directly or indirectly would not have been counted in the value because it is heading the wrong direction based on the definition). Additionally, all flow exiting will eventually (directly or indirectly) flow into the terminal node (proved earlier). When we move node into the t-partition, all the flow entering from the s-partition must be added to the new value; however, all flow exiting must the be subtracted from the new value; the part of the flow heading directly into the t-partition is subtracted because this flow is now internal to the new t-partition and is not counted as . The part of the flow from heading into nodes in the s-partition must also be subtracted from : After is moved into the t-partition, these flows will be directed from the t-partition and into the s-partition and so must not be accounted for in the , since these flows are removed the inflow into the s-partition and must be reduced by the sum of these flows, and the outflow from the s-partition into the t-partition (where all flows from s-t must end up) must be reduced by the same amount. As node was at equilibrium prior to the process, the update will have added the same value to the new value as it subtracted thus leaving proposition E true after the update. The validity of proposition E then follows from induction on the size of the t-partition.

Here are some example flow networks to help visualize the less obvious cases where proposition E holds; in the image, the red areas indicate the s-partition, the blue areas represent the t-partition, and the green arcs indicate an s-t cut. In the second image, flow between node A and node B increases while the flow into terminal node t doesn’t change.:

Corollary: No s-t cut flow value can exceed the capacity of any s-t cut.

Proposition F. (max flow, min cut theorem): Let be an s-t flow. The following 3 conditions are equivalent:

1. There exists an s-t cut whose capacity equals the value of the flow .

2. is a max flow.

3. There is no augmenting path with respect to .

Condition 1 implies condition 2 by the corollary. Condition 2 implies condition 3 because the existence of an augmenting path implies the existence of a flow with larger values, contradicting the maximality of . Condition 3 implies condition 1: Let be the set of all nodes that can be reached from with an augmenting path in the residual graph. Let be the remaining arcs, then must be in (by our assumption). The arcs crossing from to then form an s-t cut which contains only arcs where either or . If this were otherwise then the nodes connected by an arc with remaining residual capacity to would be in the set since there would then be an augmenting path from to such a node. The flow across the s-t cut is equal to the s-t cut’s capacity (since arcs from to have flow equal to capacity) and also to the value of the s-t flow (by proposition E).

This statement of the max flow, min cut theorem implies the earlier statement from Flows in Networks.

Corollary (integrality property): When capacities are integers, there exists an integer-valued max flow, and the Ford-Fulkerson algorithm finds it.

Proof: Each augmenting path increases the flow by a positive integer, the minimum of the unused capacities in the ‘push’ arcs and the flows in the ‘pull’ arcs, all of which are always positive integers.

This justifies the Ford-Fulkerson method description from CLRS. The method is to keep finding augmenting paths and applying to the latest coming up with better solutions, until no more augmenting path meaning that the latest maximum flow solution is optimal.

## From Ford-Fulkerson to Edmonds-Karp

The remaining questions regarding solving maximum flow problems are:

1. How should augmenting paths be constructed?

2. Will the method terminate if we use real numbers and not integers?

3. How long will it take to terminate (if it does)?

The Edmonds-Karp algorithm specifies that each augmenting path is constructed by a breadth first search (BFS) of the residual graph; it turns out that this decision of point 1 above will also force the algorithm to terminate (point 2) and allows the asymptotic time and space complexity to be determined.

First, here’s a BFS implementation:

I used a deque from the python collections module.

To answer question 2 above, I’ll paraphrase another proof from Sedgewick and Wayne: Proposition G. The number of augmenting paths needed in the Edmonds-Karp algorithm with nodes and arcs is at most . Proof: Every augmenting path has a bottleneckarc- an arc that is deleted from the residual graph because it corresponds either to a ‘push’ arc that becomes filled to capacity or a ‘pull’ arc through which the flow becomes 0. Each time an arc becomes a bottleneck arc, the length of any augmenting path through it must increase by a factor of 2. This is because each node in a path may appear only once or not at all (from the definition of path) since the paths are being explored from shortest path to longest that means that at least one more node must be visited by the next path that goes through the particular bottleneck node that means an additional 2 arcs on the path before we arrive at the node. Since the augmenting path is of length at most each arc can be on at most augmenting paths, and the total number of augmenting paths is at most .

The Edmonds-Karp algorithm executes in . If at most paths will be explored during the algorithm and exploring each path with BFS is then the most significant term of the product and hence the asymptotic complexity is .

Let be a .

The version above is inefficient and has worse complexity than since it constructs a new maximum flow solution and new a residual graph each time (rather than modifying existing digraphs as the algorithm advances). To get to a true solution the algorithm must maintain both the digraph representing the maximum flow problem state and its associated residual graph. So the algorithm must avoid iterating over arcs and nodes unnecessarily and update their values and associated values in the residual graph only as necessary.

To write a faster Edmonds Karp algorithm, I rewrote several pieces of code from the above. I hope that going through the code which generated a new digraph was helpful in understanding what’s going on. In the fast algorithm, I use some new tricks and Python data structures that I don’t want to go over in detail. I will say that and are now treated as strings and uids to nodes. For this code, let be a

Here’s a visualization of how this algorithm solves the example flow network from above. The visualization shows the steps as they are reflected in the digraph representing the most up-to-date flow network and as they are reflected in the residual graph of that flow network. Augmenting paths in the residual graph are shown as red paths, and the digraph representing the problem the set of nodes and arcs affected by a given augmenting path is highlighted in green. In each case, I’ll highlight the parts of the graph that will be changed (in red or green) and then show the graph after the changes (just in black).

Here’s another visualization of how this algorithm solving a different example flow network. Notice that this one uses real numbers and contains multiple arcs with the same and values.

**Also notice that because Arcs with a ‘pull’ ResidualDatum may be part of the Augmenting Path, the nodes affected in the DiGraph of the Flown Network _may not be on a path in .

## Bipartite Graphs

Suppose we have a digraph, is bipartite if it’s possible to partition the nodes in into two sets ( and ) such that for any arc in it cannot be true that in and in . It also cannot be true that in and in .

In other words is bipartite if it can be partitioned into two sets of nodes such that every arc must connect a node in one set to a node in the other set.

## Testing Bipartite

Suppose we have a digraph, we want to test if it is bipartite. We can do this in by greedy coloring the graph into two colors.

First, we need to generate a new digraph. This graph will have will have the same set of nodes as , but it will have more arcs than . Every arc in will create 2 arcs in ; the first arc will be identical to , and the second arc reverses the director of ( ).

## Matchings and Maximum Matchings

Suppose we have a digraph and is a subset of arcs from . is a matching if for any two arcs and in : . In other words, no two arcs in a matching share a node.

Matching, is a maximum matching if there is no other matching in such that . In other words, is a maximum matching if it is the largest set of arcs from that still satisfies the definition of matching (the addition of any arc not already in the matching will break the matching definition).

A maximum matching is a perfect matching if every for node in there exists an arc in where .

## Maximum Bipartite Matching

A maximum bipartite matching is a maximum matching on a digraph which is bipartite.

Given that is bipartite, the problem of finding a maximum bipartite matching can be transformed into a maximum flow problem solvable with the Edmonds-Karp algorithm and then the maximum bipartite matching can be recovered from the solution to the maximum flow problem.

Let be a bipartition of .

To do this, I need to generate a new digraph () with some new nodes () and some new arcs (). contains all the nodes in and two more nodess, (a source node) and (a terminal node).

will contain one arc for each . If an arc is in and is in and is in then include in (adding a ).

If is in and is in , then include in .

The definition of a bipartite graph ensures that no arc connects any nodes where both nodes are in the same partition. also contains an arc from node to each node in . Finally, contains an arc each node in to node. for all in .

First partition the nodes in the two disjoint sets ( and ) such that no arc in is directed from one set to the same set (this partition is possible because is bipartite). Next, add all arcs in which are directed from to into . Then create a single source node and a single terminal node and create some more arcs

Then, construct a .

## Minimal Node Cover

A node cover in a digraph is a set of nodes () from such that for any arc of this must be true: .

A minimal node cover is the smallest possible set of nodes in the graph that is still a node cover. König’s theorem states that in a bipartite graph, the size of the maximum matching on that graph is equal to the size of the minimal node cover, and it suggests how the node cover can recovered from a maximum matching:

Suppose we have the bipartition and the maximum matching. Define a new digraph, , the arcs in are the union of two sets.

The first set is arcs in , with the change that if and then and are swapped in the created arc give such arcs a attribute to indicate that they were derived from arcs in a matching.

The second set is arcs NOT in , with the change that if and then and are swapped in the created arc (give such arcs a attribute).

Next, run a depth first search (DFS) starting from each node in which is neither nor for any arc in . During the DFS, some nodes are visited and some are not (store this information in a field). The minimum node cover is the union of the nodes and the nodes.

This can be shown to lead from a maximum matching to a minimal node cover by a proof by contradiction, take some arc that was supposedly not covered and consider all four cases regarding whether and belong (whether as or ) to any arc in matching. Each case leads to a contradiction due to the order that DFS visits nodes and the fact that is a maximum matching.

Suppose we have a function to execute these steps and return the set of nodes comprising the minimal node cover when given the digraph, and the maximum matching:

## The Linear Assignment Problem

The linear assignment problem consists of finding a maximum weight matching in a weighted bipartite graph.

Problems like the one at the very start of this post can be expressed as a linear assignment problem. Given a set of workers, a set of tasks, and a function indicating the profitability of an assignment of one worker to one task, we want to maximize the sum of all assignments that we make; this is a linear assignment problem.

Assume that the number of tasks and workers are equal, though I will show that this assumption is easy to remove. In the implementation, I represent arc weights with an attribute for an arc.

## Kuhn-Munkres Algorithm

The Kuhn-Munkres Algorithm solves the linear assignment problem. A good implementation can take time, (where is the number of nodes in the digraph representing the problem). An implementation that is easier to explain takes (for a version which regenerates DiGraphs) and for (for a version which maintains DiGraphs). This is similar to the two different implementations of the Edmonds-Karp algorithm.

For this description, I’m only working with complete bipartite graphs (those where half the nodes are in one part of the bipartition and the other half in the second part). In the worker, task motivation this means that there are as many workers as tasks.

This seems like a significant condition (what if these sets are not equal!) but it is easy to fix this issue; I talk about how to do that in the last section.

The version of the algorithm described here uses the useful concept of zero weight arcs. Unfortunately, this concept only makes sense when we are solving a minimization (if rather than maximizing the profits of our worker-task assignments we were instead minimizing the cost of such assignments).

Fortunately, it is easy to turn a maximum linear assignment problem into a minimum linear assignment problem by setting each the arc weights to where . The solution to the original maximizing problem will be identical to the solution minimizing problem after the arc weights are changed. So for the remainder, assume that we make this change.

The Kuhn-Munkres algorithm solves minimum weight matching in a weighted bipartite graph by a sequence of maximum matchings in unweighted bipartite graphs. If a we find a perfect matching on the digraph representation of the linear assignment problem, and if the weight of every arc in the matching is zero, then we have found the minimum weight matching since this matching suggests that all nodes in the digraph have been matched by an arc with the lowest possible cost (no cost can be lower than 0, based on prior definitions).

No other arcs can be added to the matching (because all nodes are already matched) and no arcs should be removed from the matching because any possible replacement arc will have at least as great a weight value.

If we find a maximum matching of the subgraph of which contains only zero weight arcs, and it is not a perfect matching, we don’t have a full solution (since the matching is not perfect). However, we can produce a new digraph by changing the weights of arcs in in a way that new 0-weight arcs appear and the optimal solution of is the same as the optimal solution of . Since we guarantee that at least one zero weight arc is produced at each iteration, we guarantee that we will arrive at a perfect matching in no more than |G.setOfNodes|^{2}=N^{2} such iterations.

Suppose that in bipartition, contains nodes representing workers, and represents nodes representing tasks.

The algorithm starts by generating a new digraph. . Some arcs in are generated from nodes in . Each such node

## J E Beasley

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.

#### Network flow

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.

#### 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.

#### Assignment problem

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.

#### Transportation problem

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).

#### Transhipment 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 D1 and D2 below) - D1 representing goods in to the depot (the "front door") and D2 representing goods out of the depot (the "back door")
• an arc between D1 and D2 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 D1 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,D1 capacity 60 cost 11.3 + 0.1 = 11.4
arc B,D1 capacity 70 cost 11.0 + 0.3 = 11.3
arc C,D1 capacity 80 cost 10.8 + 0.7 = 11.5
• arcs from D2 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 D2,1 capacity 40 cost 0.7
arc D2,2 capacity 35 cost 0.9
arc D2,3 capacity 25 cost 1.1
arc D2,4 capacity 20 cost 0.8
arc D2,5 capacity 60 cost 0.6
arc D2,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.

#### Comment

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.

#### Maximum flow problem

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.

#### Foreign exchange management

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 (rij) where

rij = 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 r14.

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

Whilst we would expect r14(r41) < 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 £[r13r32r24r41 ] 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.

#### Network flow - state of the art

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.