[SOUND] In the last lecture, we have seen a formal definition of the problem, the facility location problem, and in this lecture, I would like to define an integer programming formulation of the public. Let's first look at the variables. Remember we want to output a set of facilities for which will be the opening cost. Also we want to assign each client to the closest open facility. So we have two kinds of variables, the first kind of variable is as follows. We have 4H client J in each facility I, the variable XRJ which is equal to 1. If on the eve, client J is assigned to facility R. We have also a second kind constraints, a variable sorry. Variable Yi indicates where the facility i is open. Yi is equal to one if and only if facility i is open. Now let's look at the constraints. Also we have two kind of constraints. So first we want to ensure that each client is assigned to some facility, at least one. So it means that for the sum of all facility i of XIJ is at least 1. We have also certain kinds of constraints. So this is a bit more interesting. We want to ensure that if client is assigned to a facility, then this facility is open. So for each client J, each facility I, we want to be sure that if XIJ is 1, meaning each client J is assigned to facility I, then YI Is also one, at least one, meaning that facility i is open. Now, if client J is not assigned to facility I, this constraint doesn't force to open facility I, so this is fine. Now, let's look at the objective. The objective is two fold. We have on one side, the cost of opening the facilities here. And on the other side, the cost of connecting the clients to each facility. Each open facility. So the cost of opening the facilities is to pay for H variable YI is equal to 1, the cost of the facility. And for each client we want that if the client J is assigned to facility I to pay the cost connecting client J to facility I. This is the objective. So let's summarize. We have the objective here that we just described and the two kind of constraint that we discussed in the previous slide. We want to be sure that it's client is assigned to some facility, and we want to be sure that if a client is assigned to a facility then this facility is open. Obviously the variable are zero and one. And now lets look at the relaxation. And for the relaxation, we relax the for the variables. And we want to be sure they are between 0 and 1. Actually we want to be sure that they are greater than zero because the minimization will ensure that they are plus one. So this is for a linear program for this problem. And in the next lecture I would like to take the dual of this linear program, look at the complimentary [INAUDIBLE] conditions and then define a primal dual algorithm which achieve a three approximation for this problem.