[MUSIC] Let's see now another primal dual algorithm for Facility Location. Reminder, this is the primal, that is the dual. We're not here to solve the primal and the dual LP exactly. But instead, we will start from all zero solutions, and then we will gradually increase them until we have a feasible primal solution. So how will this work? We're going to start particularly from the dual solution. Let's focus on the dual solution at first. We start from value o for all the alphas. Value 0 for all the Betas. And then we increase them, increase them, increase the alphas that we're trying to maximize, until they're blocked. We increase the amount until they're blocked. Why are they blocked? They might be blocked because aj = cij. But then, that's not too much of a problem. We can continue increasing aj, and it's pulling Bij along with it. So, aj will continue increasing and Bij along with it until something is blocked. Until we can longer increase Bij because this constraint is a hit. So, at that point, what happens is that Bij is blocked. It cannot increase anymore. Therefore, the right-hand side here is blocked. Therefore, al cannot increase anymore. So, we say the facility i is blocked if the sum of a Bij is exactly = fi. And j is blocked if it's greater than or equal to cij for some i, which is blocked, such that we can no longer increase the Bijs. So these are definitions of blocked variables, variables that we can no longer increase, dual variables. So with this, we can greedily try to build a maximal solution. Initially, the alphas and betas are all zero. We repeat. In parallel, we raise simultaneously every aj that can be raised, that is unblocked. And along with them, every Bij that has to follow. That is, such that aj is greater than or equal to cij. So Bij needs to go up along with aj. For some aj that is increasing. That is, unblocked. We keep doing that, then something's become blocked. Continue for whatever is unblocked, then something else becomes blocked. And so on, until every client has a blocked variable, dual variable aj. So in this way, we course checked a particular feasible dual solution. It remains feasible throughout, and we tried greedily to maximize the sum of the alpha js. So, this is a maximal dual solution. So, that's the dual. Now the primal. How do we get the primal? Well, let's see. We use a certain graph. Here are the clients, the blue circles are clients. Here are the facilities, the green squares are the facilities. Actually, I'm wanting you to look at the blocked facilities. These are the only ones that we might buy, so I don't draw the other ones. And what are the edges? Draw an edge between facility i and client j. If aj is greater than or equal to cij. If this constraint came into play, the constraint associated to facility i, the dual constraint associated to facility i and client j. Notice that if there is an edge between i and j, then aj must be exactly equal to Bij + cij. Why is that? Because, it's true throughout. Aj increases until it becomes equal to cij. Until then, Bij remains equal to zero. At that point, an edge appears. At that point, alphaj is equal to zero plus cij, and Bij is zero. Then, alpha j will increase, and beta ij will increase with it at the same rate, so the equality will remain. Then what happens? At some point, one of those blocked. Either Beta ij gets blocked, so facility i is blocked. In that case Beta ij stops growing, alpha j stops growing and at the time when this happened the equality was holding. So aj was equal to Bij + cij. And then they're blocked. They never change anymore. So, we are done with this. This equality remains throughout, or perhaps alpha j is blocked because of some other facility. Some other facility i prime becomes blocked and blocks j, because it has reached its value f i prime. At that point, we can no longer increase aj. Right when that happens, alpha j = Bij + cij and then what happens, aj can no longer increase. Alpha j stays put at this current level. And then what happens to Beta ij? Beta ij is not blocked right then, but there's no reason for it to increase. The only reason for Beta ij to increase would be to keep following alpha j. Alpha j stays put, therefore Beta ij stays put. Therefore, this equality remains throughout. So we have this graph of all edges such that alpha j is created and, or equal to cij, which is also the graph where alpha j Is equal to Beta ij plus cij. Then, where is the primal solution that we're going to build using the dual solution? So, I left the second part of my description of the algorithm, but it might actually be helpful to think of it as being built at the same time as the dual solution is being built. So over time, the dual solution increases, increases, and then occasionally, we open facilities and assign clients. Initially, all the facilities are pending. They are neither open nor closed. They may or may not get opened. The clients are unassigned. We do not know yet which facility they will go to. We have to wait until a facility is open before assigning the client to that facility. So as long as some client is still unassigned, what do we do? We need to open another facility. We take a pending facility. Which one? The first one that is blocked in the execution over time as we raise all the alphas. That's the one we open. Then what do we do? We close the pending facilities that are within distance 2 of i sub c in the graph. And what do we do then with the clients? We assign to that facility all the clients that are adjacent to that facility and adjacent to facilities that were closed because of ic adjacent to facilities that are adjacent to clients that are adjacent to i sub c. All clients with a distance three of i sub c. And that's how you can build a particular set of facilities that will be opened and a particular assignment of clients to facilities. So, that's the algorithm. Let's try it on an example. Let's think about this graph here, where I only drew the facilities that are blocked and the clients they all blocked in the end. And the edges, aj is greater than or = to cij. First iteration. So, the numbers next to the facilities are the opening cost of the facilities, which are actually not directly related to the execution. So you can ignore those numbers. We open the first facility that is blocked, maybe this one. I mark it in red. Then, what does the algorithm do? If the algorithm closes, the facilities within distance two of that one in the graph. Distance two, this one and that one. Let's close them, close. There, they're closed. Next, what do we do? We do an assignment of clients to this facility that we just opened. Who do we assign to that facility? Eevery client who is adjacent to this facility. Plus the ones at distance three. One, two, three, one, two, three, one, two, well, from this client, one, two, three, etc. There you go. Direct neighbors with solid lines and the indirect neighbors with dotted lines, basically. Okay, so that was the first iteration. Then, second iteration, we take the facility that was the next one to be blocked. Let's say, for example, this one. What do we do with it? We open it, that's why I drew it in red. Then what do we do? We close the facilities within distance two from it. There, these two are closed, they turned gray. Then, we take all the clients within distance three of that new facility that are not yet assigned, and we assign them to it. There. All the remaining clients, actually, this one, this one, this one, were direct neighbors, and that client was within distance three of the new facility. Then we stop, and we say, well, at this point, every client is assigned. So we can stop, and we have our final solution. So that's our new algorithm for the Facility location problem, a primal dual algorithm that is purely combinatorial.