[MUSIC] So, far we have defined the bin packing problem. We have designed the next fit algorithm. We have analyzed it and proved that it's asymptotically a 2-approximation. Can we do better than this? Can we do better than the next fit algorithm. In this part to try to do better we will design a linear programming relaxation from the problem. Let me reveal all ready out ultimate goal for in this course. Our goal is to get approximation scheme. Our wish is to design an algorithm that for each epsilon is by epsilon and outputs packing into bins, a number of bins that is at most 1+epsilon times plus some lower order terms. For this we will first try what is fast becoming our standard approach to coming at all optimization problems. Model them as an integer program and try a linear programming relaxation. So, we now need to come up with an integer program for bin packing. Recall that in bin packing, you have n items. You want to pack them into the minimum number of unit capacity bins. We will find an integer program for a slightly different version of the problem, the decision version of the problem. Given n items. And given K, the number of unit bins, the goal is to decide whether or not there exists a packing of the n items into the K bins. Whether they fit into K bins. Clearly, if you can solve one problem, you can solve the other. The two problems are equivalent. How do we get an integer program for this problem? We're going to use some variables. Zero one variables. What do we need to know? A packing is a positioning of the items into the bins. A packing is a way to decide for each item in which bin it's going to go. So, this suggests defining a variable, xij, for each item i and each bin j. It's a two dimensional set of variables. Xj will be equal to 1, if and only if, item i Can be placed into bin j. That's the definition of our variables. Xij will be one if item i goes into bin j. Xi equals zero if not. Let us go back to the example we talked about originally. Let the items be called A-B-C-D-E-F. In the case of the packing you see on the screen, item A goes into bin 1. So Xa1 is 1. Our terms b and f go into bin 2. So, Xb2 and Xf2 are both equal to 1. Similarly, Item d goes into bin 4. So x d 4 equals 1. The other two items go into bin 3. So x e 3 and x f 3 are both equal to 1. And for all the other possibilities, x i j is equal to 0. This defines correspondents between placements of items into bins, packings, and zero one values to the variables, XIJ. I ranges all over possible items. J ranges all over possible bins, 1 through K. Now, we have our variables. To define the integer program, we need constraints. How do we define our constraints? What are the constraints? The first constraint is easy to phrase in English. Every item Must go somewhere. Every item must go into one of the bins. Item B for example, must go into bin one, two, three, or four. How can we express this algebraically? It's simple, if we look at the variables xb1, xb2, xb3 and xb4, exactly one of them must be equal to one and the others equal to zero. The sum of these four variables must be equal to one. We can write similar constraints for all the other items in our input. So, we have one constraint for each item. Expressing the fact that the item must go into one of the bins. What other constraints do we have for the integer program? The bins have a capacity. The items that go in the same bin, must not exceed the bin capacity. How can we write this? If we look at all the items that go into bin number j their sizes must sum to at most one, the bin capacity. How can we express this algebraically? If we look at Xaj times the size of item a This is equal to zero if item a doesn't go in j, and is equal to s of a, the size of item a, otherwise. Some, this and similar expressions for all the items, what do you get? You get a contribution of zero for every item that is not in bin j. And the contribution of the item size otherwise. The sum is equal to the total item sizes in bin j. So, that sum must be less than, or equal to, 1. That's how to express the constraint that the bin capacity must not be exceeded. There is one such constraint For each bin. J equals 1, 2, 3, through k. So, all together, this defines our integer program for bin packing. N items, k bins. Variables x i j, whether item i goes into bin j For every item i, it must go somewhere. The sum of all [INAUDIBLE] of xij must be equal to 1. For every bin j, the bin capacity must not be exceeded. The sum of xijsi over all items i Musty less than capacity. Finally XIJ for every time IN bin J must be equal to 0 or 1. This integer program is feasible, has a solution, if and only if there exists a packing of the times not K bins. This is an integer program for bin backing. So, I started by saying that we would try to find a linear programming relaxation. From this, it is easy to deduce a relaxation. We just replace the constraint that x i j must be equal to zero or one by the constraint... That XRJ is a real number between 0 and 1. That is, The Linear Programming Relaxation. Observe that it is exactly the same as before, except that the last line is replaced by XIJ is between 0 and 1. Now, we want to use this Linear Programming relaxation to design an algorithm for bin packing. To fin how to pack items. The first thing to design such a algorithm is to check that the Linear programming relaxation is good. Good meaning it's close enough to the integer program. So, we turn to this linear program and we ask ourselves. We lost something some accuracy when we replaced the condition X I J equal to 0 1 by the condition X I J between O and 1. How much did we lose? What is the gap of this linear programming relaxation? I have some bad news. Here's a bad example. Five items 3 bins. All the items have size 0.6. The bins have unit capacity. If you have 5 items that each have size equal to 0.6, you need 5 bins to pack them. Obviously, OPT is equal to 5. 5 bins are necessary. What about the linear program? I claim that it is possible according to the linear programming relaxation to solve the linear program. And find the solution when k is equal to 3. 3 bins. Let's see how to do this. j equals 1, j equals 2, j equals 3. K is 3. 5 identical items, we need to define Xji for every i between 1 and 5 and for every j between 1 and 3. Every item, every bin. Let's define every xij to be equal to 1/3 uniformly over all items and all bins. We can check that every item fractionally is packed somewhere. For example, the first item is packed for 1/3 into bin 1. One-third into bin two, one-third into bin three. The sum of the Xi,js for item one is equal to one-third plus one-third plus one-third, one. Next, we need to check that the bin capacity is not exceeded. Let's look at bin one for example. We sum the X,I,J's times their sizes. Times .6. We have a sum with 5 terms, each term is 1/3 times .6. 5 times 1/3 times .6 that's 1. This constraint is also satisfied. So, what we have just given here is a value of the X,I,J's That satisfies all the constraints of the linear programming relaxation. According to the linear program, it seems that it should be possible to pack these items into three bins. In reality, five bins are necessary. This means that we are off by a factor of five-thirds, at least. No matter what our algorithm will do, If it tries to use this LP, it risks being off by a factor of five-thirds. And so, what we have seen here is our first attempt to design a linear programming relaxation to get the better solution for bin packing Has failed. So, we have to have some better idea, we have to explore more structure, more properties of inpacking. And that is what we will proceed to do in the next part.