So there are even more things that integer programming may do with us. For example, there is something called fixed charge constraints. Okay, so what's that? A very typical example are setup cost or setup time. So consider the following example, let say we have several factories, we have one market and we have one product. Ki is the capacity of factory i, Ci is the union production cost at factory i. So different factory, you may have new factory, old factory, their union production cost may be different, big factories, more factory, their capacity may be different. There is a fixed demand for you to satisfy with the minimum cost, and now what's new is that we have the so-called setup cost. So what's this? This is a value such that if you use this factory to produce any single positive amount, then you need to pay that fixed setup cost. But if you don't produce anything, then you don't need to pay, it doesn't matter whether you produce 1 unit, 10 units, or 1 million units. The setup cost is just one time and one expense. Okay, so a typical example is that before you may start to run your machine, you need to do some switching. You need to clean your machine, you need to open your facility, and so on. That only takes one time and one time of cost. Afterwards, whatever amount you produce, then it has nothing to do with the setup cost. So a similar thing that is around our daily life is some kind of shipping cost. It is very typical that when you're shopping online, and if you purchase one thing, one item, two item three items, four items. Typically, the shipping cost is somewhat fixed, somewhat independent of the number of products you purchase, okay? So it doesn't matter whether you purchase one product or four products, you pay one shipping cost. Of course in practice, there are also some cases that after you purchase such an amount, you get some discount. There is no shipping cost, but we are talking about the auditing, all right? Okay, so the thing is that we need to have some way to formulate this. Let's say our decision variables are here. xi is the production quantity at factory i, yi is whether we produce anything at factory i. All right, so if that's the case, ideally we should do this. The objective function is to minimize the sum of production costs and the sum of setup cost. The production cost depends on how many items you produce, and the setup cost depends on whether you set up or not. You have capacity constraint, right? So your xi cannot be greater than ki, you have demand fulfillment constraint, so your xi must be sum to be at least capital D. So everything looks fine, and maybe you want to add some binary constraint, non negativity constraints. But if you take a look at this formulation, I guess you also agree this looks weird, why? If the formulation is like this, there is no reason to pay any setup costs, right? We need to somehow link x and y, so that when we make a positive xi, we need to pay that xi by setting yi to be 1, so how do we that? Well, it's actually very simple. So the thing is that if xi is greater than 0, we need to set yi to be 1. Otherwise, there's nothing we need to do. So the relationship may be written in this way. So in this case, we multiply yi to xi and then put it at the right-hand side of that constraint. So the effect will be the following. Suppose you say your xi wants to be positive, it doesn't matter whether it is 1 million, 10, 1, or 0.2, your yi then cannot be 0, right? So your yi cannot be 0, yi must be 1. So when your xi is positive, your yi must be 1. If your xi is 0, then yi can be either 0 or 1. Both will satisfy this constraint. Then the interesting thing is that actually when your xi is 0, you will see always that the server will say yi should be 0. Why is that? Because we are minimizing the total production cost plus the total of setup cost, okay? So, if your yi has a choice, if yy can be either 0 or 1, then in an optimal solution your yi must be 0, if both are feasible, okay? So you don't really need to worry about how to require yi to be 0 when x is 0 in the constraint. You don't need to write further constraints to impose this one, because your constraint will push your yi to be 0 whenever your xi is 0, okay? So, this is a very interesting example showing us that formulating constraint actually need to be aware of the objective function, okay. So finally, we have binary and the non negativity constraints. So this constraint xi less than or equal to Kiyi is known as a fixed charge constraint. In general, a fixed charge constraint is always in this shape, when x is 0, y can be anything. When x is positive, y must be 1, okay? Both x and y are decision variables. y typically is binary, y, somehow typically is fractional. Your M must be a natural upper bound of x, so that when your y is 1, this particular constraint does not impose unnecessarily strict limit to x, okay? And eventually, when x is binary, this is also possible. If that's the case, then if x is binary, your natural upper bound is 1, so you will see x less than equal to 1, that's okay enough. So let's do an exercise on choosing the value of M. In the previous example, basically we set M to be K, okay? Or if you put i there, we use Ki as the upper bound of xi. Why is that? Because Ki is the factory capacity, there's no way for you to set xi to be greater than Ki, right? So when you say yi is 1, the remaining part is not too strict is okay, it does not cut down the feasible region. So your Ki is good, is indeed an upper bound for your xi. So sometimes, you don't really have these natural upper bound. For example, in some cases your production has no capacity limit, okay? If that's the case, then maybe you would try capital D as your upper bound. Why is that? Because there's no reason for you to produce more than capital D, right? You only need to have all the products, all your production qualities to be greater than or equal to D, I mean the sum. So there's no reason for any of them to be greater than D. If that happens, that's not optimal. So your D is also an upper bound for xi. Also, somehow this is a case by case thing. If you are doing fixed charge, you need to find an upper bound for your left-hand side. If you want to select the constraints, you need to find upper bounds for the left-hand side. So different problems requires different consideration, but somehow we need to find an upper bound for the left-hand side, then we will be able to write down our fixed charge constraints or to select some constraints to be satisfied.
