Let's start our introduction of MCNF. We will first talk about the general ideas, and then we will look at the LP formulation, and then finally we'll, see how other type of network flow models are a special case of MCNF. We start our introduction by giving you some notations or terminologies. Very quickly let's see what are they. We're talking about, networks. In a network or a graph, we always have nodes and arcs. Sometimes nodes are also called vertexes. These are the nodes or points. Then when you connect nodes with arcs, edges, or links, then somehow we form a network. A typical interpretation is that, nodes are the locations for a market, for factory for distribution centers, and arcs are routes that you may go through. Arcs may be directed or undirected. When we say there is an arc from u to v, if we include u,v in a pair of parentheses, this means we say, "this is a directed arc". If we use instead, a pair of square brackets, then we say this is undirected. For this lecture, all the arcs are directed. Somehow that means, moving from a to b, and the moving from b to a is different. Maybe a to b is possible, but b to a is not. Maybe both are possible, but they have different costs, they have different capacity, they have different routing time. Somehow arcs from a to b and b to a, they are different. A network is directed, if its arcs are directed. In this lecture, we'll talk about directed networks. An undirected network by some people, are called graphs. For some people, a network is by nature a directed network. A graph is an undirected network. I won't say all the people are using this terminology, but sometimes you'll see it. Now with this definition, we are able to define the so-called path or route. Paths or route is a collection of links or arcs. A path from s to t is a set of arcs; s to V_1, V_1 to V_2, then to V_k minus 1 to V_k, and then V_k routes to t, something like this, s to V_1, V_1 to V_2, V_2 to V_3, and V_3 to t. So that all these things are connected. When we say connected, that typically means we are able to go from s to t by passing through all these arcs. In this case, this path has a source which is our s, and a destination which is our t, and obviously, the direction matters. A cycle which is sometimes also called a circuit, in some textbook, a cycle is a path where the destination and the source are the same one. If you go in this way, then you have a cycle. A path is a simple path, if it is not a cycle. When you say a simple path, it is not a cycle. Finally, a network is an acyclic network, if it's considered contains no cycle. What does that mean? Suppose we have a network like this. This network is acyclic, because there is no cycle. If you have this one, it has no cycle. How about this? It has no cycle. How about this? In this case you have a cycle. You may roll from here, to here, to here. In that case, this is acyclic network. Let's define more terminologies, flows, ways, and the capacities. A flow on an arc is the action of sending some items through that arc. If we will have an arc, you may have a flow on it. The number of units you will send through that arc, is called the flow size. If I ship five products through this arc, then the flow size is five. But network flow is a collection of all arc flows. Whenever you have a network, something like this, if you say, "I'm going to change ship through this route, five units, through that route, three units, then may be also through this route, two units". If that's the case, then in total from s to t, you stand at 10 units. Collecting all of this gives you a network flow. A network flow can be considered as a solution. Is a plan for making flows. Each arc may have, its weights. In many cases, it mentioned about distance, costs for unit flow, and so on and so on. Typically that represents how expensive it is for you to ship one unit from here to there, how much time it takes, and so on, so on. A weighted network is a network which you have weights on arcs. An arc may have a capacity constraint. That means there may be an upper bound or lower bound for it's flow size. It's possible that you may ship items from here to there, but you have only one truck, or you have only one flight. In that case, the number of items that you may ship, is upper bounded by the capacity of your carrier. The lower bound is seldom mentioned, is typically zero. But in some special applications you also have the lower bound limitations. Finally, a network is called capacitated. If there is any arc that having some capacity constraints. In that case, we say your network is capacitated. Now we are almost ready to define our minimum cost and network flow problem. Let's considered a weighted capacitated network. We call this network G as the collection of V and E. V and E are set of nodes and a set of arcs or edges. We somehow need to defy a graph by drawing the topology and by specifying the connections or the relationship between nodes and arcs. For each node i there is a supply quantity b_i. You may think about this, as supply quantity, demand quantity. When b_i is positive, there are some units on hand that you may ship out from this particular node. That's a supply node. Consider that as factories. When b_i is negative, that means you need to ship something into these node or you may consider them as market. Finally, there may be some transshipment nodes where you have no supply quantity. In that case this means they are just transshipment points. You go through here, you go through there. It's not a market, it's not a factory, but it's somewhere that you may, for example, a distribution center may help you do the transshipment or transportation. For each arc i, j, the weight is called c_ij. C_ij is typically set to positive, to be the cost of each unit of flow. It's not always that it is non-negative. Sometimes you may see a negative cost. But in general, in typical cases, you see a positive cost or zero cost. That's the cost you need to pay for each unit of flow on that particular arc. Now the question is clear. We somehow need to satisfy all the demands by having some shipping plan from our supply nodes to destination nodes. Then we want to do that in a minimum cost of low way. All these nodes are subject to your consideration. You may want to decide how to ship those products, but somehow there are costs. You want to avoid expensive links. Then cheap links may not also be useful because they may have capacity constraints. These overall, the consideration is forming you a minimum cost network flow problem, which is abbreviated as MCNF. Here is an example. In this particular example, these numbers put into inside a pair of parentheses, that labels the supply quantity. Very quickly we can see this is a supply node because there are 25 units to go from here. There are demand nodes. The first one demand nodes, the second one they require 10 and the 15 units. We also have this transshipment nodes, they don't require anything and they cannot generate anything. On each arc we have u_ij and c_ij, which means the upper bound and the cost. Here you may move at most 15 units. For each unit you pay four dollars and so on and so on. Sometimes you may see there are some arcs, they don't have capacity constrain. That means that route is very easy to move along and there's no capacity constrain on it, is possible. Between two nodes there may be two arcs of different directions as we previously mentioned. But you may see here between node three and node five, there are actually two links. It's possible that sometimes both links are used. You may see that their capacity are different and their costs are also different. It's always possible. By looking at this, maybe we would like to see whether there is any feasible plan we may found to complete this flowing plan. For example, here we needed 10 units, we have 25 here. How about we ship 10 units here and the 10 units here, so we may satisfy the demand at node four. Here we need 15 units. Maybe we ship 15 units here, that sounds good. But note that here, along the arc from three to five, we cannot ship 15 units. We don't have that amount of capacity. Maybe from here to here, we may ship only 10 units. Well, if that's the case, what should we do? Don't worry too much. Because from three to four, there's another link, and through here, we may ship another five units. Then we also move from four to five. Then this is a feasible flow. But of course, may be this is not an optimal flow. Because there are always other options that we may find. Here we need somehow a formulation, may be an integer program that help us solve this problem. To find the minimum cost network flow. Later we will see how to do this.
