Networking is Everything (Nearly)
18th March 2016
Today was the first day of another Masterclass organised for the STOR-I students. This one is actually given by a speaker that I have already
talked about in my blog, Professor Pitu Mirchandani, from the School of
Computing, Informatics, and Decision Systems Engineering at Arizona State University. He spoke to us at the STOR-i Conference about the routing
problems with electric cars, which I discussed in STOR-i Conference 2016. One of the key parts of such a problem is
the idea of a network and this is the topic of the current Masterclass, entitled “Network Flows and Algorithms”. In this blog, I intend to
discuss the basic features of networks and go through some of the material covered by Prof. Mirchandani in the first day of the Masterclass.
Networks are everywhere. Prof. Mirchandani actually claimed that in order to solve most real world problems, one simply needs knowledge of
probability and of networks. I am not quite sure as to how accurate this statement is but they are certainly quite prominent. For example, in
my current research topic I am partly exploring networks of queues in the Health Service (see Infinitely Many Doctors? Hmmm...
and Descrete Hopsital Queues for more details of this). He did fail to put
Lucy Morgan's PhD on input uncertainty for simulation into the network category though. There are a lot of problems that can be formulated as network
problems and not just ones where something is physically moving. Orders for products, scheduling what jobs to do next, or even storage problems
can also be considered as network problems.
So, what does a network actually consist of? If $G$ is our network then it requires a set of nodes, $N=\{v_1,…,v_n\}$, which are points that are
static, and a set of arcs $A=\{a_1,…,a_m\}$ which are links between the nodes. If an arc connects node $v_i$ to node $v_j$, then it is often denoted
$[i,j]$ and can be more helpful than the somewhat arbitrary notation $a_i$.Nodes are also known as vertices and arcs are also known as edges, which
are normally used by Mathematicians in Graph theory. Arcs often have a weight associated with them. This can represent the distance between two
places or the time it takes to traverse it or even the cost of traversing the arc. It is quite normal to have such problems in Operational Research.
Equally, they may have a capacity which means that there is an upper limit as to how much can flow along an arc.
Some networks have directed arcs. This means that one can only move one way down an arc and so $[i,j]$ can be distinguished from $[j,i]$ if they both exist.
This is not the case with undirected networks, those these are equivalent to having both $[i,j]$ and $[j,i]$ with equal weights. The network shown here is
directed, indicated by the arrows, with node set
$$ N=\{v_1, v_2, v_3, v_4, v_5, v_6,v_7\}$$
and arc set
$$A = \{ [1,2],[1,6],[2,3],[3,6],[3,7],[4,5],[4,6],[5,7],[6,1],[7,6]\}.$$
There are different problems one might want to so solve with such a graph. One of the most obvious ones is the Shortest Path Problem. Suppose we wanted to
get from node $v_s$ to a destination node $v_t$. If each of the arcs are given a weight representing the distance between its adjacent nodes, then one can
formulate a linear programme to solve this problem quite easily. However, linear programmes can be NP hard. This means that as the number of nodes increases,
the time to solve increases exponentially. Can one use the structure of the network to reduce the time to solve it?
A different problem might be to work out how many units it is possible to transport between two nodes given that all arcs have a maximum capacity. As one is
not interested in the cost it would take to traverse an arc, it is normal to set all weights to zero. There are a number of possible ways to attack this problem.
One simply involves going a long each route, crossing off the used capacity and leaving the same problem with a different set of capacities for each arc. This
can continue until all the capacity of the arcs incident on $v_t$ have no capacity left. An alternative is to link $v_s$ and $v_t$ with an arc of weight $-1$.
Then, one can simply solve the shortest route problem as the restrictions will occur due to the capacity.
Even allocation problems can be formulated as a network problem. In this case a “bipartite” graph is used. Each worker is one node is a set $N_1$ and each job
is a node in the set $N_2$. Arcs only exist between points in different sets, that is, between workers and jobs. The weights could now represent the costs of
allocating a worker to a job.
More efficient methods to solve these sorts of problems exploit the additional structure of a network over a standard Linear Programme and are called network
flow algorithms, which the remainder of the Masterclass will be on. I may be able to enlighten you on this next week.