[MUSIC] In the last lecture we have defined an integer program for the facility location problem. In this lecture I would like to start from this integer program from the linear programming relaxation. And to obtain the dual of this linear program. So let's recall the linear program. So the objective is made of two sums, sum concerning the xij and the variable xij and the sum concerning the variable yi. And we have two kind of constraints. We have the constraint that ensure that each client is assigned to some facility and the constraint that ensure that the facility to which the client is assigned is open. So let's go from these linear program to the dual. So we have here two kind of constraints in the primal. So we'll have two kind of viables in the dual. First, we'll have the viable alpha j, which will be associated to the constraint concerning the client. Then we'll have viable betaIJ which are corresponding, which corresponds to the constraint entering the facilities or for client that is assigned to this facility. So let's go to the dual. First, look at the objective of the dual. The objective only concerns the variable alpha J. This is because in the primal the coefficient for the variable b dot i-j is zero. Here. Then let's now look at the constraints of this dual. We have also two kinds of constraints, the constraints that are associated to the variable XIJ, and these are the constraints. One can be convinced that this is really the good constraint. There is no mistake here. We have also the constraint corresponding to the variable Yi. And these are the constraints. Okay, so this is the dual. So now let's go to the complimentary slackness condition. Recall, what are the complimentary slackness condition. So, if you have an optimal solution for the primal and an optimal solution for the dual then. We have the dual constraint is tight or the primal variable is 0. And also, primal constraint is tight or the dual variable is 0. These things have to be true if we have a optimal solution for the primal and an optimal solution for the dual. So what are the complementary slackness conditions in this case? Let's look at the dual and the primal. Look at the complimental slackness condition and find a nice interpretation for the two. Since we have two kind of constraints and two kind of variable, in the primal we have four kind of condition in the complementary slackness. So let's first look at the first one, for example. The first one tells us that, if the viable xij is positive, slightly positive, better than zero, then the constraint, alpha j minus beta ij is tight, is equal to cij. Okay. So, let's find a nice interpretation. Let's see beta IG as the contribution of client and J for opening facility I, let's assume that client's are paying for opening a facility. So beta ij is the amount of money client j is willing to pay for facility i. What does the complimentary slackness condition 2 tell us? It tells us that for all facility i, if yi is greater than zero, meaning yi is one say, so facility i is open, then the sum of all client of beta ij is equal to the opening cost of phi. So, if Yi is one, then the sum, this sum, is equal to fi. So we say that facility i is fully paid. Like the amount of money that the client puts to open facility i is actually the cost of facility i. Let's look at another complementary slackness condition. The fourth one. This tells us that for each facility i each, each client J if beta ij is greater than zero, then yi is equal to xij. Let's see it in another way. If for all facility i, for all, this is equivalent to say that for all facility i for all for K and J if yi is different from xij, then beta ij is 0. But recall that yi is greater than xij for whole inj. So if xij is different from yi, then beta ij is zero. So if xig zero and yi is one then, client G does not contribute to opening any facility except the one it is connected to, except the one for which XIJ is positive is one. So, client G only pays for opening the facility it is connected to. Finally, let's look at complementary slackness condition 1. This tells us that for all facility i, for all client j, if xij is positive, then alpha j minus beta ij is equal to cij. Thus if client j is assigned to facility i. Right? We have xi of j is equal to 1. And then we have the alpha j minus beta ij is equal to cij. So let's define alpha j as the total price paid by client j. So this price is made of two things. The first thing is the cost of connecting client j to facility i. This cost is cij. Then the second part of the cost is made of the contribution for opening facility i, the contribution of client j for opening facility i is beta i, j. And this is exactly what this equation tells us, that the total costs, the total price paid by client j, alpha j, is equal to cij plus beta ij. Here we have seen a nice interpretation of the duel. And in the next section we'll see that this interpretation can help us design a prime algebra algorithm and to analyze it.