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.