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
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.