0:00

Okay guys, so this discrete optimization and facility location assignment.

Â Okay?

Â So what I'm going to do is go over the assignment, okay?

Â And go over the details of the input output.

Â Okay?

Â So this is a very intuitive assignment in the sense, so

Â what you have is a bunch of customers, so this is

Â the black dots that you see on the cree, the screen,

Â and what, so, and this is data, this is given to you.

Â Right?

Â And so the second thing is that you get a set of location that you see there.

Â These are location for the facilities, and your goal

Â is to actually find out where you build these facilities.

Â Okay?

Â And there are two cost that will come into play.

Â Every time you open a facility, it will cost you a fixed cost.

Â And then obviously, there will be also the cost of

Â delivering goods from that facilities to the various customers, okay?

Â And that's the variable cost, which depends

Â on how far the customer is located.

Â Okay?

Â And so in a sense, you have this tension between the fixed cost, if

Â there would be no fixed cost, you would open many of these warehouses, okay?

Â And this, you know, and the variable cost, the, the distribution

Â cost of actually shipping the good to the particular customers, okay?

Â Now, every one of these facilities will also have a particular capacity and

Â that will tell you how many of these customers it can actually serve, okay?

Â So basically tension between the fixed and

Â the variable cost, and also tension, because

Â every one of these facilities will have a, will have a fixed capacity, okay?

Â A fixed number of customers that it can serve.

Â Okay?

Â So this is a solution, okay?

Â We open two of these facilities, and you

Â see the customers are located to these two facilities.

Â Okay?

Â So that's the goal.

Â Of course we want to do that for thousands

Â and thousands of customers and hundreds and hundreds of facilities.

Â Okay?

Â So this is a description of the problem, okay, I'm going to go over it.

Â It's a terrible model, okay?

Â There are actually very few [UNKNOWN] who can

Â actually express this model, as I'm stating it here.

Â And the reason I'm doing this is because I don't want to influence you

Â on the kind of formulations that you will want to use for solving this problem.

Â Okay?

Â So we'll have n facilities and m customers.

Â Okay?

Â So every customers will have a demand dc.

Â Okay?

Â For customer c.

Â Okay?

Â That's how much good the customer c wants

Â to get delivered to, to, to his facility, okay?

Â To his, you know, ware, you know, to, to his, its location.

Â And then you will have for every facility where you can actually build a warehouse.

Â Okay?

Â For every site where you can build a facility in a sense.

Â Okay?

Â So you have a cost, that's the cost of the building the facility.

Â Okay?

Â And then you have a capacity which is the,

Â how many customers that capa, that facility can actually serve.

Â Okay?

Â So this is sf and then cap, capf, okay, that you see over there.

Â Okay?

Â Then there will be a cost, you know, for

Â transporting goods from the facility to the customer, okay?

Â And we're going to use this thing here to actually

Â model that cost, so this is dist(f,c), which tells

Â you the distance between the, the distance and also

Â the cost, between the facility and the customer c, okay?

Â And then, essentially the only decision variables

Â in the model that I'm showing you

Â here is going to be the set of customers which are allocated to facility f, okay?

Â So af is going to be the set of customers that are allocated to facility f.

Â Once you have that, once you have all

Â these decision variables, essentially you have all you

Â need to actually compute a cost and you

Â know, things, and, and verify the constraints are satisfied.

Â Okay?

Â So the, the, so I'm going to go over the, over the mathematical formulation.

Â Once again, keep in mind that, you know, this

Â is probably not something that you want to use, okay?

Â So what we are trying to do is minimize

Â for every one of the facilities two things, okay?

Â The fixed cost and then the variable cost, okay?

Â The fixed cost is what?

Â Well, you pay it, you pay the fixed cost, so you build

Â a facility if at least one customer is assigned to the facility, okay?

Â So if you know that the set of customers

Â assigned to that particular facility is not empty, okay?

Â So that particular expression here is going to

Â be true, okay, you multiply that by

Â the, by the cost of the fixed cost and you get essentially the fixed cost.

Â If no customer is allocated to that facility, this expression is 0, okay?

Â So that's the fixed cost.

Â When you actually assign something to a facility, you

Â have to open it and you pay the fixed cost.

Â And then the second part is essentially looking at all

Â the customers which are allocated to that particular facility and

Â you compute a distance between that customer and the particular,

Â and the particular facility and you get the variable cost.

Â Okay, so that's the objective function.

Â Two part, once again.

Â The fixed cost and the variable cost.

Â And then you have the two constraints.

Â The first one is making sure that no capacity constraints are violated.

Â For every one of the facility, you make sure that all the customers

Â which are allocated to that popular facility

Â ever demands which doesn't exceed the capacity.

Â So you take all the customer associated with

Â the facility, you sum the demand of all these

Â customers, and you make sure that this is small

Â or equal to the capacity of that facility, okay?

Â That's the first constraint.

Â The second constraint is obvious.

Â You want to serve every one of your customer, okay?

Â So you make sure that for a particular customer, if you look at all the

Â facilities, at least one of them has the

Â customer as one of its served customer, okay?

Â So that's what this constraint is doing, okay?

Â Once again, you know, don't implement that mode, it's terrible, okay?

Â But this is a mathematical expression, precise expression of the problem, okay?

Â Now let me go over the input output, okay?

Â So this is the input that we are giving you, okay?

Â It is pretty simple in this problem, okay?

Â So you have the number of facilities, the number of customers, okay?

Â So that's the first two numbers that you're going to get, okay?

Â And then essentially afterwards you get all the information about

Â the facilities, and then all the information about the customers, okay?

Â For the facilities, what do you get?

Â Well you get the fixed cost, you get

Â the capacity, and then you get the location, okay?

Â The geographic location, which is, you know, a point in Euclidean space here.

Â Okay?

Â So that's what you get.

Â And you get that, obviously, for, you know, all the

Â particular facilities that you have, and they are n of them.

Â And then afterwards, you'd have the same,

Â well, roughly the same information for the customers,

Â what you get for them is essentially the demand that they have in terms of goods.

Â And then the location once again or where they are in the plane.

Â Okay?

Â And so this is essentially the input.

Â So the input is very simple, right?

Â The capacity and the fixed costs for every one

Â of the l, for the facilities including their location.

Â And then for the customers, the same thing.

Â You have the demand in terms of the goods.

Â Okay?

Â And then you have the locations of the various customers.

Â Okay?

Â So that's our input.

Â The output is what you see there, so we want something very, very simple.

Â We want the objective function and whether it's optimal or not, okay?

Â Many of these problems here, you will be

Â able to prove optimality, so this is important.

Â Not all of them, probably, but almost all of them.

Â And then, what you see there is basically the list of the customer, the, the list

Â of the cust, way the customers, which facility

Â are assigned to every one of the customers.

Â So for every one of the customers who want

Â to know which facility they are assigned to, okay?

Â So that's the output, okay?

Â For every one of the customer, which is the facility that the customer is

Â assigned to, and we can deduce obviously from that which facilities are being used.

Â Okay?

Â So this is an example of a particular instance, okay?

Â So you have three facilities for customers, okay?

Â Really baby instance here.

Â You see the various numbers for the fixed costs,

Â for the capacity, and the locations of these two things.

Â And for the customers that the same thing, you see the demand, 50, 50, 75, 75.

Â And you see the location in the plane, okay?

Â In this particular case, this is the out, this is one of the output, okay?

Â One possible output.

Â You see the value of the objective function there

Â 250, you know, 2550.013, okay, and then it's not optimal.

Â And then you see a, you know you see where this particular customers are located.

Â You see that customer 0 and customer 1 are located to facility 1.

Â Customer 2 to facility 0.

Â Customer 3 to facility 2.

Â So the, the, essentially the assignments that you have

Â here is the one that you see over there.

Â Which basically tells you that the facility 0 is serving customer 2.

Â Facility 1 is serving customer 0 and 1.

Â And facility 2 is serving customer 3, that's the last thing that you see there.

Â Okay?

Â So this is

Â 8:11

this is a description of input/output, okay?

Â Now we talked a lot about warehouse location

Â in the lecture, look at this as one, okay?

Â They are different formulation, okay?

Â Whatever you do, there will be different way of

Â modeling this problem, whatever the approach that you take, okay?

Â And different formulation will have different efficiency.

Â So this is an interesting problem in actually the modeling the various point.

Â Okay, so you have to think about what is

Â a good formulation in every kind of the models, right?

Â So what is a good formulation for mathematical programming system?

Â Okay, remember, you know, we talked about that.

Â What is a good formulation for a local search algorithm?

Â Okay, so the two main approach that I would

Â suggest looking at are local search and mathematical programming, okay?

Â And if you do local search, one of the critical thing in this particular

Â assignment is going to be the speed at

Â which you can actually explore the neighborhood.

Â Okay?

Â So the faster you can explore this

Â neighborhood, the more configuration you can explore, okay?

Â And in this particular example, there is a beautiful data

Â structure that you can use to speed this up tremendously, okay?

Â So think about that, okay?

Â So good luck.

Â Okay?

Â So this is an amazing assignment, very interesting assignment, okay?

Â It's sufficiently simple, such that you can understand it completely, but it's

Â also challenging, and various approaches with

Â give you different, you know, trade-offs.

Â So it's a very interesting assignment, okay?

Â Have fun, good luck.

Â And so, you know, we'll see how, how well you do,

Â and we'll just get that in some of the mailbox later on.

Â Okay?

Â Bye, guys.

Â Thank you.

Â