Let's take a look at linear programming formulation. Let's see how this may be done with a linear program. Pretty much our decision variable are x_ij. This would be the flow size on arc i, j, or of arc i, j. This should be determined for all your possible arcs. This is going to be, for example, we decide this will be 10, this will be 10, this will be 15, this would be five, this will be 10, and then this will be five. Some others are zero, zero and zero. For each arc, we determine the amount of flow on it. That's going to create a plane. Then our objective function would be to minimize the total cost. For this link, if you ship the amount x_12, then you need to pay the total cost of 4 times x_12 and so on. For each arc, we have a capacity constraint which says x_12. x_12 here, your shipping quantity cannot be greater than 15. x_13, here you cannot be greater than 20, and so on. Besides all of this, we have the so-called flow balancing or flow conservation constraints are set. Flow balancing means on each arc, the amount that comes in equals the amount goes out. For transshipment nodes, for example, this one, the amount that ships in should equals to the amount that ships out. You will see that x_12 should equal to this, x_23 plus x_24 plus x_25. Similarly for Node 3, you will see that here x_13 should be equal to x_34 plus x_35. This somehow seems to be easy, but sometimes it's actually hard, because if you take a look at here or actually for Node 3, we actually have a lot of things. There are three incoming arcs and we also have two outgoing arcs. It's the incoming arcs, sum to the outgoing arcs. You need to carefully collect all of them, so that your constraint makes sense. For supply nodes, you actually don't need to have so many variables. Because for supply nodes, in some cases, you would replace some numbers by the value bi. Like in this case, you are 25 should equal to your total outgoing arcs. This is sometimes somewhat true for also demand nodes. For example, for this one you have incoming, incoming, outgoing, and some value would be consumed there. Somehow you may see x_24 plus x_34. These are the incoming nodes. Whatever amount you ship into Node 4, 10 units would be deducted because some people eat there. Then the remaining need to be sent to Node 5. For Node 5 is pretty much the same thing. For all the nodes, pretty much we may write down this flow balancing constraints. That's going to help us make sure that items do not disappear randomly. Items would be there as long as they are under our plane. Flow balancing constraints also ensures that all the demands are satisfied. When you specifically write down these 10, these 15, this somehow means the amount of shipping in should equal to the consumption there and the amount of shipping out. This actually satisfies all the demands. Then finally, if we want to satisfy everything here. Obviously, the total supplies needs to be equal to the total demands if we want the formulation to be able to be found a solution. In that case, sometimes you may ask, well, what's going to happen if actually my total supply does not meet my total demand? Well, the answer is very simple. Suppose you actually have 250, but your demand only needs 25. Then all you need to do is to assume that you only have 25 and then solve the problem. If your supply's less than demand, well, there's no way to satisfy all the demands, so you need to find some items more. Collectively, this is our complete formulation. Here to make it easier to understand, I simply put numbers there. This is a simple formulation instead of a compact formulation. But anyway, we want to minimize the total cost subject to five flow balancing constraints, several capacity constraints, and non-negativity constraints. We may somehow estimate the size of this model. The number of nodes is the number of equality constraints. For each node, we have these flow balancing constraints. You should be correct. The number of arcs is the number of variables here, and also the number of arcs would give you that number of capacity constraints. Make sense. Once we put all the formulations into all the constraints into one formulation, very quickly we will see in each column of these equality constraints. In each column, there is exactly one 1 and one minus 1. What does that mean? If you look at x_12 column, one 1 and one minus 1. For this column, one 1 and the one minus 1. Somehow it means each variable appears exactly in two equality constraints. In one equality constraint, the coefficient is 1, in the other, it must be negative 1. Is that a coincidence? Well, is not. It's always the case. Why is that? Because each node or each variable represents an arc, and each constraint represents a node. Here for x_25, it somehow means the amount you move from 2-5. For Node 2, you will see x_25 and for Node 5, you will also see x_25. Obviously, one is shipping out, one is the shipping in. That's why they are coefficients would just be 1 or minus 1. Each column must have exactly one 1 and one minus 1 in this LP formulation. I guess you will also agree this is not a coincidence. This must be the case. This is the formulation. Here, I want to add just two quick notes. The first thing is that when we do not require our x_ij to be integers, we have this linear programming formulation. This is an LP? Correct. Second, when we mentioned there is one 1 and one minus 1 in each column, we don't really include those capacity constraints inside for some reason that we will tell you later. Then obviously, this property is special for MCNF. Then later, we will see how it helps us understand and analyze this problem.