topic Re: Looking for Literature for Center of Gravity problem in Mathematical Optimization, Discrete-Event Simulation, and OR

Looking for Literature for Center of Gravity problem

Santha — Tue, 17 Mar 2020 16:07:46 GMT

Hi.

I am trying to see if I can solve the center of gravity location problem using SAS. So I am looking for articles / literature to set my model.

As an overview, I have a bunch of nodes , each of them with its own demand (weight). I have latitudes and longitudes of them.

I am looking to find a center of gravity point that will minimize the "weighted-distance" from this center of gravity point to all nodes.

And as an extension, want to see if i can choose from a list of candidates that will minimize the weighted-distance.

Any help is appreciated

Re: Looking for Literature for Center of Gravity problem

RobPratt — Tue, 17 Mar 2020 16:19:00 GMT

This is known as the Weber problem and can be solved as an unconstrained convex nonlinear optimization problem. See this SAS Global Forum 2008 paper, which also discusses the (nonconvex) multisource Weber problem.

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 17 Mar 2020 16:31:05 GMT

Thanks Rob. I will look into it.

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 17 Mar 2020 17:51:18 GMT

Rob

I did see that. It gave me a good insight. Thank you.

I was going to ask you for any example models in SAS related to this that I can learn so that I could better formulate it.

Thanks again

Re: Looking for Literature for Center of Gravity problem

RobPratt — Tue, 17 Mar 2020 18:29:00 GMT

I happened to already have code for this:

proc optmodel;
   set DIMS = 1..2;
   set CUSTOMERS;
   num a {CUSTOMERS, DIMS};
   num demand {CUSTOMERS};
   read data indata into CUSTOMERS=[_N_] {d in DIMS} <a[_N_,d]=col('a'||d)> demand;

   var X {DIMS};
   min Z = sum {i in CUSTOMERS} demand[i]*sqrt(sum {d in DIMS}(a[i,d]-X[d])^2);

   solve;
   print X;

   create data sganno from [i]=CUSTOMERS x1=a[i,1] y1=a[i,2] x2=X[1] y2=X[2]
      drawspace='datavalue' function='line';
quit;

proc sgplot data=cdata sganno=sganno;
   scatter x=a1 y=a2;
run;

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 17 Mar 2020 18:37:01 GMT

Rob that is really amazing.thank you

Re: Looking for Literature for Center of Gravity problem

Santha — Thu, 19 Mar 2020 19:02:29 GMT

Rob.

I went into your model and also did some research to understand basic concepts about these types of problems.

Now I am ready to deploy SAS and test it on my small model. I have two columns called Sitename (that are nothing but customer names ) and Demand. I have 6 Sitenames and demand for each 6 of them. My objectives is to pick "n" points that will minimize the sum of the weighted distance to all the customers. Once this is set up correctly, I shall go on with choosing from a list of candidate facilities.

Sitename	SiteParameter1
DEN	800
SFO	150
EWR	300
SEA	200
MIA	50
MCI	500
ORD	1000

I will have a set of customers (set CUSTOMERS;)

I will have a numeric parameter called demand that is indexed over CUSTOMERS (num demand {CUSTOMERS};)

The other numeric parameter that I see in your code num a{CUSTOMERS,DIMS} and your read data I am not quite sure I follow it. I am understanding that to be another parameter which will be like Customer1, Customer2 etc?

read data indata into CUSTOMERS=[_N_] {d in DIMS} <a[_N_,d]=col('a'||d)> demand;

Can you help me how to read data / understand read data ? Also, model will give the optimum X,so that will be one of the 7 sites. Correct?

Re: Looking for Literature for Center of Gravity problem

RobPratt — Thu, 19 Mar 2020 21:27:05 GMT

In the example code I provided, the indata data set has two columns (a1 and a2) that correspond to the location coordinates of each customer. For you, these would be latitude and longitude, and you would probably want to use the GEODIST function to compute distance instead of the SQRT formula that I used to compute Euclidean distance. Solving the optimization model yields the coordinates (X[1] and X[2]) for a new location that minimizes the demand-weighted sum of distances from customers to this new location. It will not be the same location as an existing customer unless that customer happens to be located at the center of gravity.

Re: Looking for Literature for Center of Gravity problem

Santha — Thu, 19 Mar 2020 21:30:00 GMT

Thank you Rob for the insights. I am clear now. I will set up the model and let you know.

This is very interesting. Thank you again.

Re: Looking for Literature for Center of Gravity problem

Santha — Mon, 23 Mar 2020 23:11:40 GMT

Rob

I wanted to let you know that I was able to adapt the code to my needs. and was able to get what I exactly wanted.

Thank you very much.

Re: Looking for Literature for Center of Gravity problem

RobPratt — Mon, 23 Mar 2020 23:17:59 GMT

Glad to hear that, Santha!

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 24 Mar 2020 18:41:50 GMT

I have a full model with 11,000 customers. Its been like 45 minutes and is still running.

I want model to pick 1 answer.

How do I set the tolerance / relative gap so that I can live with that % . Also, a time limit until the model can run like an hour or so and give the answers after 1 hr mark.?

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 24 Mar 2020 19:04:18 GMT

Trying FEASTOL and MAXTIME based on NLP options. Any other ideas?

Re: Looking for Literature for Center of Gravity problem

RobPratt — Tue, 24 Mar 2020 19:19:03 GMT

Yes, MAXTIME=3600 will stop the solver after one hour. You can also use FEASTOL and/or OPTTOL. Are you able to share code and data?

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 24 Mar 2020 19:43:13 GMT

Rob - here is the code.

%let p=2;
proc optmodel;

set DIMS=1..2;
set CUSTOMERS;
set FACILITIES = 1..&p;
num a {CUSTOMERS,DIMS};
num demand {CUSTOMERS};

read data STDOPT.COGModelingData into CUSTOMERS=
[_N_] {d in DIMS} <a[_N_,d]=col('a'||d)> demand;

print demand;
print a;

num Xlb {d in DIMS} = min {i in CUSTOMERS} a[i,d];
num Xub {d in DIMS} = max {i in CUSTOMERS} a[i,d];
**print Xlb; **print Xub;

var X {FACILITIES, d in DIMS} >= Xlb[d] <= Xub[d];
var W {CUSTOMERS, FACILITIES} >= 0;

impvar Distance {i in CUSTOMERS, j in FACILITIES} = sum{d in DIMS} GEODIST(a[i,1],a[i,2],X[j,1],X[j,2]);

min Z = sum {i in CUSTOMERS, j in FACILITIES} W[i,j]*Distance[i,j];
con DemandCon {i in CUSTOMERS}: sum {j in FACILITIES} W[i,j] = demand[i];

solve with nlp / ms FEASTOL=1e-1;
print X;
put _OBJ_=;

/* post-processing: assign each customer to closest facility */
set CUSTOMERS_j {FACILITIES} init {};
num minDistance, argminDistance;
for {i in CUSTOMERS} do;
minDistance = constant('BIG');
argminDistance = .;
for {j in FACILITIES} do;
if minDistance > Distance[i,j] then do;
minDistance = Distance[i,j];
argminDistance = j;
end;
end;
for {j in FACILITIES} W[i,j] = 0;
W[i,argminDistance] = demand[i];
CUSTOMERS_j[argminDistance] = CUSTOMERS_j[argminDistance] union {i};
end;
put _OBJ_=;

/* post-processing: solve each facility separately */
min SingleFacilityObjective {j in FACILITIES} = sum {i in CUSTOMERS_j[j]} demand[i]*Distance[i,j];
problem SingleFacilityProblem {j in FACILITIES} include
{d in DIMS} X[j,d]
SingleFacilityObjective[j];
for {j in FACILITIES} do;
put j=;
use problem SingleFacilityProblem[j];
solve;
end;
put (sum {j in FACILITIES} SingleFacilityObjective[j])=;
print X;

Re: Looking for Literature for Center of Gravity problem

RobPratt — Tue, 24 Mar 2020 20:07:37 GMT

Are you able to share the data?

One way to speed things up might be to exclude customer-facility pairs that are too far apart. The most efficient way to do this is to use sparse modeling to omit the corresponding variables, as illustrated in the Sparse Modeling example in the documentation.

Re: Looking for Literature for Center of Gravity problem

Santha — Tue, 24 Mar 2020 20:44:18 GMT

here is the data. thank you

let me look at sparse modeling as well.

Re: Looking for Literature for Center of Gravity problem

Santha — Thu, 26 Mar 2020 15:05:16 GMT

Hi Rob.

Were u able to see what was the problem in the data? I noticed that the MAXTIME of 600 seconds does not seem to be respected as it tries to solve more than that and would never finish. Not sure if something inherently problematic with dataset or sthg.

I am going to try to do sparse modeling today. But if you can let me know about anything to speed the solve it would be great.

Re: Looking for Literature for Center of Gravity problem

RobPratt — Thu, 26 Mar 2020 20:45:13 GMT

I don't see anything wrong with the data. Can you please show the SOLVE statement you used, with the MAXTIME= option?

Re: Looking for Literature for Center of Gravity problem

Santha — Thu, 26 Mar 2020 20:47:49 GMT

Rob

Here you go.

solve with nlp / ms feastol=1E-01 maxtime=600 timetype=real;