Going With the Flow

Last week in a talk given by Prof Adam Letchford I was introduced to some optimisation problems which come under the title of "network flows". As you might have guessed, these concern problems relating to movements of flows through networks (think of water through pipes). In this blog post I will outline the two network flow problems presented:

1. Maximum flow problems
2. Minimum-cost flow problems

Maximum flow problems

To model networks, we use terminology from graph theory. We think of the network as a directed graph with vertices \(V\) and arcs \(A\), where we say \(a = (i, j)\) to mean that \(a\) is an arc going from vertex \(i\) to \(j\). An example can be seen below.

For a network flow problem we are interested in sending some 'flow' along each arc. If you think of the arcs in the diagram above as pipes then the flow is perhaps a certain volume of water being sent per second. You can think of other examples, such as traffic on roads, electricity through wires or data through telecommunications networks. In all these examples it is reasonable to assume that what represent the arcs, be it the pipes, roads or cables, have some maximal capacity. A question you can then ask is what is the maximal amount of flow I can send from one vertex in the network to another? For example, referring to the diagram above, you may wonder what is the maximum volume of water you can send from the tap to the glass per second, subject to the capacity constraints of the pipes. This the premise of the so called maximum flow problem. 

This problem can be formulated as a linear program by considering two main sets of constraints; the flow in and out of a vertex must be the same, and the flow along any arc must not exceed its capacity. We then look to maximise the amount of flow that can be sent whilst these constraints hold. With this formulation one can then use algorithms relevant to linear programming to solve the problem, such as the simplex method. However, there are specialised algorithms for solving this problem which make use of its specific features to improve the speed.

Minimum-cost flow problems

Now assume that sending flow down a certain arc incurs some cost, possibly different for each arc. In a practical setting it may then not be that beneficial to simply know the maximum amount of flow that can be sent. Instead you may have a desired amount of flow  \(d\)  you would like to send from one point to another, and you would like to do this at the smallest cost possible. For example, you may want to send 100 litres of water per second from the tap to the glass, and would like to know how to do this in the cheapest way possible. This is the motivation for the so called minimum-cost flow problem.

This can similarly be formulated as a linear program but in this case we need to introduce some notion of cost. We do so by assigning a cost per unit of flow to each arc in the network. The constraints in this case are similar to the max flow problem, however, there is the additional requirement that we must have the total flow to equal to  \(d\). Then we look to minimise the total cost, calculated using the assigned values, whilst satisfying the required constraints. Practically, this problem can also be solved with linear programming algorithms or there are many potentially faster methods which capitalise on its unique structure.

Other problems and uses

Another interesting problem is the multi-commodity flow problem [1]. In this problem we assume that we have multiple types of flows we would like to send to and from different pairs of vertices in our network. We can then similarly look to maximise the total flow or minimise the cost of some desired flows. 

Other problems that may not appear to immediately be related to flows can actually be formulated from this perspective, leading to a reduction in constraints. Examples include the traveling salesman problem (TSP), where you look to visit a certain set of vertices in a network exactly once whilst minimizing some associated cost, for example, a salesman visiting their customers whilst minimizing the distance traveled. Prof Letchford presented a formulation of the TSP in terms of flows (due to Claus (1984)) which resulted in the number of constraints going from  \(2^{n-1}\)  down to \(\mathcal{O}(n^3)\)  , where  \(n\)  here is the number of vertices in the network. This means that the problem scales better as  \(n\)  gets large which can make computation of the solution faster.

References

[1] https://en.wikipedia.org/wiki/Multi-commodity_flow_problem

[2] R. Ahuja, T. Magnanti & J. Orlin (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall.