The next problem that we want to introduce is this shortest path problem. This is somehow different from the previous ones. Given a network on which each arc has a weight d_ij. Here d_ij somehow does not means cost, it means a distance or the time you need to travels through that particular arc. We want to find a shortest path from node s to node t. It's a path that collects a few arcs. By passing through all the arcs, we are able to get to node t in the fastest way, in the shortest path. We're going to assume d_ij are non-negative in this particular lecture. In practice or in some other situations, in some cases, your d_ij may be negative and then you'll need to deal with a weird situation. But let's assume we are only talking about non-negative d_ijs. This is a figure that shows the idea. Your s is here, your t is there. You have all ways to go from s to t. For example, 3, 2, 3, 7, 2. This is also one route 2, 3, 8, 9. This is another route or path. Among all the possible paths, we want to find one that is the shortest. But I don't know which one is the shortest or maybe you want to spend a few minutes to find the answer. I just want to formulate this formulation and then I may solve any shortest path instance that you input to me. I want to get a shortest path problem formulation and this somehow I need to first convince myself that I may formulate it, I may consider it as an MCNF problem. Pretty much is the way. We are going to send one unit of product from s to t. So we want to send one unit from s to t. Then we may consider those d_ij as the cost for each arc. The arc costs are arc distances. We have only one supply node where the supply quantities plus one, one demand node where we have a negative one here. All others are transshipment nodes. We have zero as the supply quantity. Then here, this negative one is the supply quantity. In that case, we are able to consider this as an MCNF problem. Naturally, we may write down an IP formulation. Let that be the set of transshipment nodes. Then we have three different sets of flow balancing constraints. At the initial point, s is going to be the case that among all those outgoing links, one of them must be selected, and then for a destination t is pretty much the same. Among all those incoming arcs, we would have one to be selected as our route. Finally, for each of those transportation nodes, all those incoming things and all those outgoing things must equal each other. If you say I want to choose the path to go into this node, there must be another outgoing link selected to be the outgoing direction. This happens if you have an entering link or it's also possible that you have nothing enter, then you cannot have anything outgoing. After all of this, we may set our x_ij to be binary. Then basically, we are saying that we want to select a few arcs to get connected to satisfy loss flow balancing constraints and eventually minimize the total distance. Then again, this would be totally unimodular if we split one group to have node t and another group for node s and T, capital T. Also we understand that if we have this formulation for shortest path, we need to take care of these binary constraints because we cannot just randomly linearize it with no further analysis. If we just randomly linearize it, we need to make sure that it does not generate a solution that we cannot execute. We can now say with 20 percent probability, I'm going to go in this direction and with 80 percent of probability I'm going to go in that direction. No, you can't. Then luckily, if you relax this integer or binary constraints, your solution will still be integer solutions. Why is that? Because of total unimodularity. The last thing we want to introduce is the maximum flow problem. For maximum flow problem is the following. We have a network where arcs have capacity instead of cost, so they don't have cost, they have capacity. We want to ask, how many units may we send from a given source node to a destination node? The idea is from s to t. You may consider, for example, s, as a village, there are several persons there, and that you know, very quickly there will be some tsunami or some typhoon coming to this particular village. You need to send those citizens of that village to move out to some safe place. You need to do that as quickly as possible. You need to determine a flow plan, so that you may ship all the persons to the safety place. But there are capacity constraints along all the links. In this particular example you can see the capacity cost here is 4,8,2,6 and so on. What we plan to do is that, for example, four persons, please move along this direction, three persons please move along that direction, and we still have several persons there. Don't worry too much because maybe two may move along this direction, two in this direction, two in this direction, and then another two in this direction. This will become our maximum flow solution or maximum flow problem in general. Anyway, how is the maximum flow problem also an MCNF and problem? Actually in this problem, there is no requirement on demand fulfillment. We want to send as many units as possible. We are solving a maximization problem rather than a minimization problem. We really need some careful design for these formulation. The interesting thing is that here, what people do in formulating a maximum flow problem is to try to send some virtual units from t to s to pay negative costs. We're going to say a long this new arc, the cost is negative 1. There is no capacity constraint. All other links, they don't have cost. What we should do is to try to push as much as possible from s to t so that when they go back from t to s we are able to earn some money. We are able to minimize negative cost. In that case, we will be able to formulate this one as MCNF problem with only transshipment nodes. If we write down the formulation is pretty much the same as previous ones. Now, what we care the most is x_ts as the flow size for the added arc t, s and the cost is considered to be negative 1. We try to minimize negative x_ts. But you cannot get x_ts for free. From t to s, if you want some flow, you need to have some entering flow, entering into node t and so on and so on. All the nodes are transshipment nodes. For all the nodes, you have the same format of flow balancing constraints. You now have lost capacity constraints, and then you will require all the values to be integers. That's fine because you will get integer solutions for free. Lastly, I want to complete our reduction map or reduction relationship. Previously we're here. We say assignment is a special case of transportation, transportation is a special case of transshipment, and transshipment is a special case of MCNF. By some analysis, we may still say that the shortest path problem is a special case of our transshipment problem. Why is that? So first, in the shortest paths problem, you will have one supply node, one demand node, and all others are transshipment nodes. This is one kind of transshipment problem where you'll supply and the demand nodes are special. You have only one supply nodes, one demand nodes and the supply and demand quantities are just one. In that case, you are still solving a transshipment problem. Then finally, a maximum flow problem is not a special case of transshipment, not a special case for shortest paths. It is a special case for MCNF. All your original links they don't have cost. You have one additional link where you have negative 1 as the cost, and then you minimize the total cost by trying to send as much as possible from s to t. That's pretty much the end for today's lecture. We are talking about all these network flow things. Our main focus is on two things. First, we want to introduce all these formulations, all these problems because in many cases you'll use them. Transshipment, transportation, shortest paths, maximum flow, MCNF. A second, the most important thing for today's lecture is that we show you that MCNF satisfies that totally unimodular idea. Then once we solve this problem, by relaxing those integer or binary constraints, we still get integer or binary solutions. Only with this property MCNF and all those variants may be applied successfully and the widely in practice. Hopefully after today's lecture, we all appreciate these nice property. That's it. Thank you.
