topic Re: Constraining Sites_Facilities using distance in Mathematical Optimization, Discrete-Event Simulation, and OR

Constraining Sites_Facilities using distance

Santha — Thu, 25 Jun 2020 20:31:57 GMT

Hi Rob.

I am trying to use sparse modeling as suggested by you few months back. https://go.documentation.sas.com/?docsetId=ormpug&docsetTarget=ormpug_optmodel_examples07.htm&docsetVersion=15.1&locale=en

Here is my code. I want to pick p number of facilites that satisfy my customer demand. The following code is an adapted version of the code that you had earlier but the only thing is that I added the CUSTOMERS_SITES to cull out those customers_facilities pairs that has less than 1000 miles as the distance. When I ran the model, I got error that said " A set expression may not depend on a variable". That was my first question. Second question is if my objective function and constraints are right.

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;

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} = GEODIST(a[i,1],a[i,2],X[j,1],X[j,2]);

set CUSTOMERS_SITES = {i in CUSTOMERS, j in FACILITIES: Distance[i,j] <= 1000};

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

expand;

solve with nlp ;

Re: Constraining Sites_Facilities using distance

RobPratt — Thu, 25 Jun 2020 20:57:53 GMT

The ERROR message is because your set CUSTOMERS_SITES depends on Distance, which is an implicit variable. Sets must depend on constants and not variables.

It looks like you are mixing two related facility location problems. For both of them, the input includes a set of customers, each of whose demand must be satisfied by a fixed number (p) of facilities. The difference between the two problems is where the facilities can be built:

If the facilities can be built anywhere, this is an NLP problem (the multisource Weber problem).
If the facilities must be built at locations that are chosen from among a finite set of candidate sites, this is a MILP problem (the p-median problem).

The sparse modeling approach applies only to the MILP problem. Which problem do you want to solve?

Re: Constraining Sites_Facilities using distance

Santha — Thu, 25 Jun 2020 21:12:10 GMT

Hi Rob

Thank you very much. I am trying to solve multi source Weber problem. Can i then, just add a constraint saying someghing like

con radius {i in CUSTOMERS, j in FACILITIES} Distance [i,j]<=1000;?

Re: Constraining Sites_Facilities using distance

RobPratt — Thu, 25 Jun 2020 21:56:01 GMT

Yes, that is legal if you include a colon:

con radius {i in CUSTOMERS, j in FACILITIES}: Distance [i,j]<=1000;

But I suspect that these additional nonlinear constraints will make the problem much harder to solve.

Re: Constraining Sites_Facilities using distance

Santha — Thu, 25 Jun 2020 22:25:31 GMT

Rob. I tried that con radius even before i was experimenting sparse modeling without knowing that sparse modeling was for MILP.

The con radius constraint con radius {i in CUSTOMERS, j in FACILITIES}: Distance [i,j] <=1000;

does not give any error. But it also does not seems to respect the constraint because in the answer I do see some customer-Facility site pairs that have more than 1000 mile as distance.

Re: Constraining Sites_Facilities using distance

RobPratt — Thu, 25 Jun 2020 23:56:33 GMT

What were the values of Solution Status and Infeasibility in the Solution Summary when you were seeing constraint violations?

Re: Constraining Sites_Facilities using distance

Santha — Fri, 26 Jun 2020 01:11:24 GMT

Rob - Solution Status is "Failed" as you can see in the below Solution Summary

Solution Summary SolverNLP

Algorithm Interior Point

Objective Function Z

Solution Status Failed

Objective Value 3796957.4976

Optimality Error 1394.3093905

Infeasibility702.52192689

Iterations 2245

Presolve Time 0.00

Solution Time 9.44

Re: Constraining Sites_Facilities using distance

Santha — Fri, 26 Jun 2020 01:18:32 GMT

When i don't have that con radius, the solution status is "Iteration Limit Reached".

Solver NLP

Algorithm Interior Point

Objective Function Z

Solution Status Iteration Limit Reached

Objective Value 1675638.2436

Optimality Error 0.1991496343

Infeasibility 2.5283975E-7

Iterations 5000

Presolve Time 0.00

Solution Time 18.67

Re: Constraining Sites_Facilities using distance

RobPratt — Fri, 26 Jun 2020 02:26:29 GMT

Yes, Infeasibility > 0 implies that some constraints are violated.

Re: Constraining Sites_Facilities using distance

RobPratt — Fri, 26 Jun 2020 02:31:17 GMT

Infeasibility is essentially 0 here, so all constraints are satisfied within tolerance. Iteration Limit Reached means that the solution might not be locally optimal. Multisource Weber is a difficult problem, so you might consider solving it approximately by first solving a p-median problem (MILP) with the customers as the candidate locations and then solving a single-source Weber problem for each resulting cluster (p independent NLP problems).

Re: Constraining Sites_Facilities using distance

Santha — Fri, 26 Jun 2020 19:40:45 GMT

Rob

Thank you very much for your feeback. Let me try to implement that and get back to you. Thanks