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.