We mentioned that this is a linear program. This is a linear programming formulation. We also know that sometimes we hope the solution, the flow size are integers. It may be you are shipping an air conditioners. You are shipping laptops. You hope your solution are integers. We also understand that this may not always be required. Even if you are talking about concrete units, you may still use a linear program to approximate. If you get fractional solution, you still are able to do some rounding whatever. Integer variables should be used, should be seriously used only when first, your approximation by rounding is too inaccurate and should not be allowed. In that case, you really need to talk about integer variables. Or second, when you are having binary variables using them to model laws if else either or select at least two, at most two or fixed charge. When you use binary variables, then typically they should not be replaced by fractional values. Suppose we are having these two situations, then sometimes we hope we may have integer solutions for free. The interesting thing for MCNF is that, well, we get integer solutions for free. What does that mean? As long as your supply quantities and upper bounds are all integers, then a solution for the LP would just be an integer solution. Your uij and the your bi should all be integers. When that happens, then you have integer solutions. Or say in another way, suppose you have an IP formulation. You set those xij to be integers. Then if you solve the LP relaxation, you solve your IP because your LP relaxation must give you an integer solution. This is a special property. In the past that you have solved all linear programs. Typically, your coefficients are all integers, but you don't get integer solutions. Somehow you get fractional solutions typically. This must because the problem is special and for the formulation this means that co-efficient is special. That's, what's that? To understand that, we need to first to introduce this idea called total unimodularity or totally unimodular matrices. What's the definition? The definition is that a square matrix is called unimodular if its determinant is either one or negative one. Cannot be two, cannot be 1.5. It is determinant must be one or negative one. That allows us to define a totally unimodular matrix. A matrix is totally unimodular or sometimes we abbreviate it as TU. This guy is totally unimodular, if all it squares submatrices are either singular or unimodular. Unimodular means the determinant is one or negative one. Singular means the determinant is zero. Somehow that means, if you'll give me a matrix, for example this matrix A. If you give me a matrix and then I can choose any way to get a square submatrix. If that's the case and whenever I choose one, I would see is determinant either zero, one or negative one. If that's true for all submatrices, then this matrix is totally unimodular so that's the two examples. For example A, if you choose your submatrix to be one times one. For each number here, you must satisfy these unimodular constraint. In this case, you understand that if a matrix can be totally unimodular, all it's elements must be either one or zero or negative one, and so that's the first criteria. Then for example if you pick a matrix here, well it's determinant is negative one. If you pick another one for example here is negative one. If you pick another one like this, very quickly you may calculate that is determinant is zero, zero, zero minus zero, minus zero, minus zero this determinant is zero. You may try to see all the possible squares submatrices are either singular or unimodular. For B this is not true. We may see that for example, if you consider the whole matrix B, then you will see that is determinant is zero plus zero plus zero minus one minus zero minus one. The determinant of B is actually negative two. This violates the requirement of unimodularity, so B is not totally unimodular. There must be a reason to talk about totally unimodular matrix. The reason is here. Because total unimodularity gives us integers solutions. But that mean read this proposition. Consider a standard form linear program where you want to minimize C transpose x subject to Ax must be equal to bx non-negative. For a standard form linear program, if your coefficient matrix A is totally unimodular, and if your B are all integers, then for any optimal basic feasible solution, you must have it satisfies the fact that all the values must be integers. Somehow this idea applies to basic feasible solutions. Optimal basic feasible solutions, are those things obtained by the simplest method. That's why it is true. Whenever we are solving a linear program with the simplex method, always we have bases and the set of non-basic variables. Actually even if you don't use the simplex method, eventually your solution based pretty much are extreme points solutions, corner points. Still you may separate them into basic, and non-basic. If you have that, then your solution x may be split to x_B and x_N. Your x_B would be A_B inverse b, which is the values for your basic variables. All we need to do is to convince you that A_B inverse b indeed are all integers. This comes from a fact from linear algebra. Whenever you have a matrix A or matrix A_B, so A_B, as you know, is a square matrix, it's inverse may be determined in this formula. Well, you first find its determinant, put it as the denominator, and then for a numerator, it should be a square matrix. In the numerator, this is the adjugate matrix for A_B. What's that? That's a A_B has nine values. How about A_B inverse? For A B inverse, each element for example, A_B 1, 2, A_B 1, 2, would be the determinant of the matrix obtained by removing row j in the column i from A_B, what does that mean? For A_B, if this is talking about 1, 2, then I'm going to eliminate row 2 and column 1. Then for the remaining four values, they form another square matrix, I'm going to calculate its determinant and put it here. Also that's how we define the adjugate metrics for A_B. Also you feel tired because these things all look so weird, but the proof is almost complete, why is that? Because pretty much all we need to do is to use the following argument. If A is totally unimodular, A is the original matrix, A_x equals B our A is the original coefficient matrix. If A is totally unimodular, then whatever basis B you choose, you know its determinant, must be either one or negative one. First it cannot be zero because if it's singular, then that does not form a basis. It must be one or negative one. If that's the case, then whatever thing you obtain here its denominator is one or negative one. You are not going to get fractional value due to this division. Then lastly, all the numbers here are also integers, so then we guarantee your x_B would be an integer vector as long as the given B is also integer and A is totally unimodular. I will say this seems to be weird if this is the first time for you to see it. But to understand this is not too difficult. The definition of totally unimodular was there, and for simplex method, there is a basis is in set of non-basic variables, and then you also know something about this linear algebra thing, or at least you trust me. If all these things are connected, then you are able to prove this. The implications for IP is here. If we have a standard form linear program that has a totally unimodular coefficient matrix, and optimal basic feasible solution would always be integer. Or we are talking about IP then is linear relaxation always gives us an integer solution. The branch-and-bound tree would be finished by just solving one node. That means whenever you have a problem where your coefficient matrix is totally unimodular, then you may feel free to set the variables to be integers. That does not create any complexity to your problem, the problem may still be solved very easily. In general, this help us to tackle an integer program in a different way. When you have an integer program, it would be difficult to solve it, and you may be hesitate to use a branch-and-bound to solve it. But actually, if you understand that the coefficient matrix is totally unimodular, then actually branch-and-bound becomes an efficient good algorithm, because we have done the analysis, we know its coefficient is totally unimodular, and then using the branch-and-bound is good enough. There's no reason to consider other algorithms. This is again, another example showing us that good algorithms for solving a problem starts from a good analysis.
