Okay, welcome back. Supplemental assignment on Warehouse
Location. Are there any of you left?
so, this is an assignment where the actual data format is a little bit more
challenging and we'll review that. But this is the Warehouse Location
problem. It's, once again, one of these beautiful
problems that everybody should try at least once in his or her life.
Okay, so you have basically a bunch of Warehouse Location, Okay?
And you have a bunch of customers. And the key point in this particular
assignment is to find out where you open the warehouses, okay, so that you can
allocate the customers to them. And you minimize two types of costs,
okay. The fixed cost, okay, of, for the
warehouses, okay, and the transportation costs from the customers to the
warehouses, okay. So we have a lot of things that we need
to describe. We need to describe the various
Warehouses, we need to describe the customers, and especially the cost.
Okay? The cost of a particular warehouses, and
then the cost of moving, you know, goods from one warehouse to a particular
customer. Okay?
So, so the ultimate solution here, okay, is going to be you know, choosing some
particular warehouses. Okay?
We choose which one to open and which one not to open.
Okay? And then obviously afterwards, the
customers you know, we left to choose. Which warehouse to associate which
warehouse to associate with each customer.
Okay? So, you see that this customer here has
been associated to that warehouse. You see that that customer here has been
associated to that warehouse. Okay?
So, in a sense what we need to do is basically choose, you know, where the
warehouse, you know, choose which warehouse to open, and then which
customer to assign to which warehouse. Okay, so this is a formalization of the
problem. Okay, it's the most contrived, and I can
tell you it's really contrived. I had to repeat this slide three times,
okay. So this is a very, very contrived,
formulation of the problem. Probably nobody will ever want to use it
in practice, but it's a correct formalization, and it basically models
all the constraints, so in a sense, it tells you what your problem, what, what
you, what your solution will have to satisfy.
We're not giving you any inch whatsoever of what is a good formulation for this
problem, okay? So in this particular problem, we'll
always have n you know, a number of warehouses, a number of customers, okay,
we'll have n warehouses and m customers, okay?
Now the warehouses are going to be characterized by two data points, okay?
One of them is going to be the cost, the cost of opening that warehouse, when you
open that warehouse, you pay that fixed cost, okay?
And then we have a capacity, that's the capacity of goods.
That that particular warehouse can actually serve.
Okay? So that's the two pieces of information
that you need for a particular warehouse, okay.
For the customers you need essentially the cost of transporting the good from
that customer to every, to a warehouse, okay.
And so for every customers, we'll have the cost for every, the transportation
cost to every other warehouse. Now you can think of this as a big matrix
and obviously the data, the input data, will have that, will store that input
matrix, okay. Now one of the things that we'll use in
the formalization is the value a w, the set a w.
And that's the set of customer which are allocated to warehouse w.
Okay, now let me a little bit go over the formulations, such that you understand
the problem very well, because this is not a problem that we have seen in the
slides. There is additional constraints.
Okay. So let's look at the optimization
function first. The first thing that you will do is, you
know, compute both the fixed and the transportation costs.
The fixed costs are pretty easy. If a warehouse is open, okay, you have to
essentially, you know, pay a fixed cost. How do we know that the warehouse is
open? Well at least one customer has to be
associated with it. Which basically means that the size of a
w, the set of customers allocated to warehouse w, has to be greater than one.
So, if that set is greater than one, you have to pay the fix cost.
Okay? So, that's the first thing that you have
to sum. The second thing that you have to sum is
the transportation cost. Okay?
If a customer c is allocated to warehouse w.
What you need to do is make sure that you paid a cost t c w.
Okay? And that's this transportation cost that
you see here. Okay?
So, your formulation will have to compute exactly that cost.
Okay? Now, the second thing that you need to
take into account are the constraints of this problem.
The first one, okay, is basically limiting the capacity.
Okay? Is basically the capacity constraints for
the warehouses. Okay?
So if you look at all the customers that are associated to a warehouse, okay?
Every customer c associated to warehouse w.
You want to be sure that if you sum their demand, it doesn't exceed the capacity of
the network, of the, of the warehouse, okay?
So this is what you see there, it's basically the capacity constraints.
When we discussed the warehouse location, and during the lecture, we didn't have
that capacity constraints, we have one. In this particular, you know this
particular assignment. Okay.
So pay attention, because it may be really critical in how you design your
algorithm. The last constraint that you see here is
making sure that every a customer is served by only one warehouse, okay.
It would be a very different problem is we are allowed to split the demand of a
particular customer. So what this constraints is basically
saying is that, if you look at the particular warehouse, okay, and if, and
if you, if you, if you get particular warehouse and try to find if a customers
belongs to it, okay. This expression is going to be zero one.
And what you want to be sure is that for all the warehouses that you consider
there is exactly one of these warehouses that is actually that, that c actually
belongs to. So, this is constraint that we, we, that
is essentially a very contrived way of saying a particular customers is
allocated to only one of the warehouses. So once again you know, the formulation
that you see is really, really not intended to be used in any system, okay.
You can actually use it in some system, okay, there are very few systems that
support this, but there are some, okay. But it's probably a terrible, terrible
formulation. It just, you know, we are trying to
confuse you as much as we can, because in this particular problem, the particular,
the particular model has a really strong influence on the quality of the solution.
Okay. Now let me go back to the, the, from the
formulation to the, the input data. Okay, so the input data will start, you
know, as usual, by giving you some particular constant that tells you how
many inputs you have. Okay, so we'll specify the number of
warehouses and the number of customers. Okay.
And then we list, you know, the values for the warehouses and then list the
values for the customers. Okay.
For the warehouses, we need to, you know, to give you two pieces of information.
We need to give you the capacity of that warehouse and then the fixed cost of that
warehouse. So what you see is a list of pairs, you
know, for every one of these line, you know, you have you know every one of
these lines is associated with one warehouse.
Okay, and every one of the, and every one of these lines is giving you first a
capacity of that warehouse and then the, the fix, its fixed cost.
Okay? So once we have done that.
We have all the data for the particular warehouse.
And we have to specify essentially all the data for the particular, for the
particular customers. And a customer says two important piece
of information. The first one is its demand and you will
see one data, you know, data value. For that particular, that particular
demand. And then you will see the transportation
costs for, from that particular customers, to all the warehouses.
And that's going to be a list, which can be, you know, ki-, qui-, ki-, kind of
long for some of the, for some of the benchmarks that tell, that is basically
telling you what is the transportation cost for that particular customers to,
you know, to the warehouse zero and then to warehouse one, to warehouse two and so
on and so forth. Okay.
And so essentially your list is here, this is essentially giving you two pieces
of information. This big transportation matrix.
Interleaved with some of the demands of everyone of these customers, okay?
The output here is going to be also very interesting, okay?
So, what you're going to output is obviously the value of the objective
function, okay? The objective value of the optimal
solution, and then a flag telling you whether you have proved that this
solution was optimal or not. And then, what you will say is that for
every one of the customers. You will specify which warehouses it is
associated with, okay. So for every one of the customers, you
basically specify the warehouse it is allocated to, okay.
Now, once again okay, this is the input data, this is the output data, but don't
assume that this is actually telling you how you have to model the problem.
It doesn't mean that because this is the output data, that you have to have
decision variables for these c's. Okay, think about that, maybe there is,
there are modelings which are, you, you know, the models that are actually not
using the c's as decision variables. Once again, you know, the fact that this
is the output doesn't you know, doesn't prescribe a particular way of modeling
the problem, and that's important. Okay?
So don't, you know, distinguish what the output is, okay?
And what the decision variable can be. Okay?
I've usually found the decision variables, you have to be able to compute
the output, and that output is probably something that the decision maker, in
practice, will want to have, but the optimization problem may be modeled with
different variables, okay? So this is a particular example.
Okay, a particular instance. Okay.
So you see that in this instance we have three warehouses four customers.
Okay. The three lines there are basically
describing the warehouse data. Okay.
So you see that you know the first two warehouses essentially have a capacity of
100. The next one is a capacity of 500, and
then you see the various cost of these warehouses here, as the second value for
each one of these lines. And then what you see are basically the
description of all the customers. You see the demand 50, 50 and then 75
afterwards. Okay, that's the demand of every one of
these customers, and what you see here is also the various lines, you know,
specifying the transportation cost, okay. And these lines have to have three
entries, because we have three warehouses, okay.
So the first is one is 1, you know, 101, 202, and 300 and, and 2000.3, okay.
And so on and so forth. And that's describing all the data you
need for the various customers, okay. So the output here, you see the various
output here. You see the value of the objective
function, okay. You see that is not proven optimal, and
then you see 1 1 0 2, which basically means that the first two customers were
assigned to warehouse one, the next one to warehouse two, and the third one to
warehouse the third one to warehouse zero, and the last one to warehouse two.
Okay? So this is the output.
Once again, you know, this doesn't necessarily correspond to decision
variables, but it may be. Okay?
And this is essentially the input data, okay?
One of the things that I'm trying to do always is trying to confuse you, trick
you into the various modelings, right? Okay, so Warehouse Location, as I said
many times during this supplemental material, they are different formulation.
And the way you model the problem is really critical, okay?
So, think about how you can formulate this problem.
So, what are the decision variables? What are the constraints?
Okay? Now this is also an interesting problem,
because different approach are going to be a very differently.
Okay. So, if you use local search or if you use
branch and bound. Think about, you know, when they are
best, what kind of problems they are best for?
You know, are the limitation to some of, for some of the instance of these
techniques. Okay.
Do thy get stuck on some of these problem classes or not, okay?
And if you do local search, think once again of a way to actually have a FAST
neighborhood computation, okay. So, you know, Local Search is about
exploring as many, as many, as many, you know, points in a graph as possible.
Noting the graph is possible. And the faster your neighborhood
computation is, you know, even if it's complex, even if it does interesting
things, okay? The fast, the more, the higher the
quality of your solution will be. So even if your neighborhood is complex,
think about ways to speed up, okay? that's it.
I mean, this is a very interesting assignment, okay?
and I'm very curious to see the solutions, and, you know, good luck.