topic Re: Minimizing Facilities and Distance to Sites in Mathematical Optimization, Discrete-Event Simulation, and OR

Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 17:21:52 GMT

I'm struggling to frame this problem. I want to utilize the minimum number of facilities to meet the constraints, and then assign the closest sites to those facilities.

First I thought I would minimize distance, and then come back around and minimize the cost to use the facility. The second minimization does not seem to re-assign anything because there is flow assigned, so must use the facility.

So, that had me thinking I would minimize the facilities and then the distance. Which does not really seem to change much.

If I minimize the number of facilities that seems to get me the minimum number of facilities, but then associated long distances between facilities and sites.

		set <str,str> ARCS;
		num distance {ARCS};
		read data GREEN_ARC_DATA into ARCS=[source target] distance;
	
		set <str> RDC;
		num rdc_lat {RDC};
		num rdc_lon {RDC};
		num cost {RDC};
		read data GREEN_RDC_DATA into RDC=[fdb_id] rdc_lat rdc_lon cost;
		
		set <str> ZIP3;
		num zip3_demand {ZIP3};
		num pct_population {ZIP3};
		num zip3_lat {ZIP3};
		num zip3_lon {ZIP3};
		read data GREEN_ZIP3_DATA into ZIP3=[zip3] zip3_lat zip3_lon zip3_demand pct_population;
	
		set NODES = RDC union ZIP3;
	
		var Flow {ARCS} >= 0 <= 500000;
		var assignFlow {ARCS} binary;
		var Build {RDC} binary;
	
		/* ZIP3 Demand must be met */
		con zip3_flow_con {i in ZIP3}:
			sum {<j,(i)> in ARCS} Flow[j,i] = zip3_demand[i];

	
		/* Assign separations to DDUs based on assigned FLOWS */
		con assign_flow_con {<i,j> in ARCS}:
			Flow[i,j] <= Flow[i,j].ub * assignFlow[i,j];

		/* If ZIP3 assigned to a RDC it must be built */
		con zip3_rdc_con {<i,j> in ARCS}:
			assignFlow[i, j] <= Build[i];

		/* Population goals */
		/*con next_day_pop_con {i in RDC}:
			sum {<(i),j> in ARCS} pct_population  <= &rdcBinCap;*/

		/* Constrain separations in an RDC */
		con rdc_bin_con {i in RDC}:
			&rdcMINZip3Cap <= sum {<(i),j> in ARCS} assignFlow[i,j] <= &rdcMAXZip3Cap;
	
		min green_rdc_min_build = sum{i in RDC} cost[i] * Build[i];
		save mps green_rdc_min_build;
		min green_rdc_min_dist = green_rdc_min_build + sum{<i,j> in ARCS} distance[i,j] * assignFlow[i,j];
		save mps green_rdc_min_dist;

Kind of a mess right now, as I am trying to understand the right way to approach this.

Re: Minimizing Facilities and Distance to Sites

RobPratt — Fri, 21 May 2021 18:07:14 GMT

It sounds like you want to use primary and secondary objectives like this:

   /* primary objective */
   min green_rdc_min_build = sum{i in RDC} cost[i] * Build[i];
   solve;
   num min_build;
   min_build = green_rdc_min_build;
   con ObjectiveCut:
      green_rdc_min_build <= min_build;

   /* secondary objective */
   min green_rdc_min_dist = sum{<i,j> in ARCS} distance[i,j] * assignFlow[i,j];
   solve with milp / primalin;

Note the use of the PRIMALIN option to warm start the second solver call with the first solution.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 19:43:35 GMT

That, I believe, is what I am trying to do in my code. I tend to use optmodel to setup the problem and then call a solver seperately (in this case optmilp). I was using primalin, but it did not seem to do what I expected.

I changed my code to do the solving in OPTMODEL, and from the looks of the output with PRINT it appears to be doing what I was hoping. I seem to be a create data idiot, as I can't seem to get the RDC value, ZIP3 value and the FLOW between those.

This seems to get the pairs out:

create data green_rdc_sol from  [i j]={i in RDC, j in ZIP3: Flow[i,j].sol > 0.5};

But struggling how to get the value in Flow[i,j].sol out too.

My follow on question would be if I wanted to do this primary/secondary approach and call proc optmilp outside of optmodel do you have any guidance or examples? I seem to be much better dealing with the output data from there.

Re: Minimizing Facilities and Distance to Sites

RobPratt — Fri, 21 May 2021 19:56:24 GMT

You almost had it. Just add Flow to the end:

create data green_rdc_sol from  [i j]={i in RDC, j in ZIP3: Flow[i,j].sol > 0.5} Flow;

Regarding SAVE MPS + PROC OPTMILP, that approach of course works but is inefficient because you are adding two extra writes and reads for each solve. I recommend instead using PROC OPTMODEL for both problem generation and the solver calls. If you strongly prefer calling the solver from PROC OPTMILP, you might consider using a SUBMIT/ENDSUBMIT block so you don't need to exit PROC OPTMODEL.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 20:18:32 GMT

Thanks!

Now that I got the results out, it appears to be doing the same thing my code was. The initial "build" solve puts me at 36 facilities, connected to sites that are really far away (in almost all cases it prefers things far away). Then if I add in the code that would minimize distance, it explodes the facilities up to 176 (but now the sites are much closer).

Feel like I have to be missing something simple here....

Re: Minimizing Facilities and Distance to Sites

RobPratt — Fri, 21 May 2021 20:25:38 GMT

Was the build cost of the 176 facilities the same as for the 36 facilities? If so, what don't you like about the second solution? If it builds too many facilities, you might want to include another objective cut to convey that information in the optimization model.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 21:01:08 GMT

The 36 are in the 176, so it was higher for the 176. It's not so much that I do not like the answer as I do not understand why it is changing.

If I minimize the number of facilities, and it drops down to 36....why is it doing it in such a way as to pick sites so far away from the facility?

Clearly my current set of constraints would let it do it with 36 facilities....without adding any other constraints why would it not just minimize the distance between those facilities and sites. Adding in the other facilities certainly reduces the distance, but it has re-inflated the cost.

Re: Minimizing Facilities and Distance to Sites

RobPratt — Fri, 21 May 2021 21:08:36 GMT

It sounds like you are not imposing the objective cut in the second solve. Are you able to share your full code and data? If you don't want to share publicly, you can send it to me privately.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 21:21:35 GMT

Code and data attached.

Re: Minimizing Facilities and Distance to Sites

RobPratt — Fri, 21 May 2021 22:24:10 GMT

I am not able to replicate your results with the data you sent. Instead, I get all 184 facilities built in both solves. Did you maybe run with rdcMINZip3Cap = 0?

In any case, you have the wrong objective cut:

      con ObjectiveCut{<i,j> in ARCS}:
         assignFlow[i, j] <= min_build;

It should instead be:

      con ObjectiveCut:
         green_rdc_min_build <= min_build;

Re: Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 22:33:26 GMT

Sorry about that. Was playing with different ideas with the ObjectiveCut and did not put it back.

You get all 184 if you run just the build solve?

I don't change anything just comment out the distance solve.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Fri, 21 May 2021 22:45:46 GMT

Results for build solve:

i
1352485	25
1353588	25
1358063	25
1360697	25
1360742	25
1360762	25
1367260	25
1368208	25
1372672	25
1380388	25
1380428	25
1380602	25
1382577	25
1432873	25
1432887	25
1433257	25
1433414	25
1433529	25
1433530	25
1433589	25
1434840	25
1435567	25
1435750	25
1436570	25
1438171	25
1439777	25
1440140	25
1440579	25
1440968	25
1440974	25
1440977	25
1441024	25
1441025	25
1441026	25
1441029	25
1441030	16

Results for both running:

i
1352485	6
1353588	1
1358063	6
1360697	7
1360742	5
1360762	5
1367260	5
1368208	5
1372672	4
1380388	6
1380428	3
1380602	3
1382577	6
1432873	6
1432887	6
1433529	5
1433530	5
1433589	2
1434840	3
1435567	6
1435750	3
1436570	1
1438171	3
1439777	8
1440579	2
1440968	6
1440974	8
1440977	5
1441024	3
1441025	6
1441026	11
1441029	3
1441030	6
1441032	4
1441038	6
1441040	9
1441043	3
1441044	6
1441050	2
1441051	1
1441052	4
1441053	1
1441057	5
1441059	3
1441060	6
1441061	3
1441062	4
1441064	4
1441067	3
1441076	5
1441078	6
1441081	5
1441082	6
1441083	2
1441088	6
1441091	6
1441099	2
1441101	6
1441102	3
1441104	3
1441111	6
1441116	8
1441119	6
1441120	7
1441124	4
1441133	9
1441134	7
1441140	7
1441150	6
1441162	8
1441174	10
1441177	8
1441182	5
1441184	3
1441185	6
1441190	6
1441191	6
1441192	3
1441198	3
1441199	3
1441203	1
1441207	2
1441215	6
1441227	9
1441229	6
1441234	8
1441239	6
1441241	6
1441242	7
1441254	5
1441257	6
1441258	6
1441264	4
1441267	6
1441272	7
1441281	6
1441283	6
1441288	18
1441297	6
1441301	6
1441303	6
1441310	6
1441312	1
1441327	7
1441333	5
1441334	5
1441337	4
1441342	6
1441344	6
1441350	5
1441363	4
1441367	5
1441368	3
1441369	6
1441372	6
1441375	6
1441379	8
1441382	6
1441383	9
1441389	3
1441402	5
1441412	6
1441419	5
1441420	6
1441424	7
1441431	6
1441445	5
1441446	5
1441448	2
1441450	4
1441458	4
1441459	6
1441462	2
1441463	9
1441465	6
1441468	4
1441470	4
1441479	4
1441480	4
1441482	2
1441483	6
1441484	3
1441485	5
1441488	5
1441489	3
1441490	4
1441491	2
1441493	2
1441854	6
1441874	6
1441877	13
1441907	5
1441999	7
1442076	5
1442357	4
1442375	6
1442511	3
1443242	6
1443577	1
1443983	2
1444502	6
1445059	2
1445732	3
1448490	6
1450618	8
1451492	6
1451874	4
1452911	2
1453009	3
1458221	1
1459260	6
1459516	4
1465884	7
1479956	5
1517777	4
1532174	6

Zip file contains solutions files for both runs as well as logfiles.

Re: Minimizing Facilities and Distance to Sites

RobPratt — Sat, 22 May 2021 00:11:08 GMT

OK, I get the same objective values as you, but notice that you cannot tell which facilities are built just by looking at the Flow variables. If you add this statement after each solve, you will see that all 184 facilities are built:

      put (card({i in RDC: Build[i].sol > 0.5}))=;

Also notice that the first objective value matches the sum of all build costs.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Sat, 22 May 2021 02:08:11 GMT

I see so it is only assigning flow to the smaller set of facilities, but still saying to build them all. So I must have something wrong with the general problem formulation. Back to the drawing board.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Sat, 22 May 2021 17:10:45 GMT

I believe this constraint:

con rdc_bin_con {i in RDC}:
			&rdcMINZip3Cap <= sum {<(i),j> in ARCS} assignFlow[i,j] <= &rdcMAXZip3Cap;

was causing the issue. It was effectively never allowing for 0 sites to be assigned to a facility, so I fixed it by breaking it apart and including and multiplying the lower bound by build[i]:

con rdc_serv_max_con {i in RDC}:
		sum {j in ZIP3} assignFlow[i,j] <= &rdcMAXZip3Cap;
con rdc_serv_mmin_con {i in RDC}:
		sum {j in ZIP3} assignFlow[i,j] >= &rdcMINZip3Cap * Build[i];

Still churning, but I believe that is the issue.

Re: Minimizing Facilities and Distance to Sites

RobPratt — Sat, 22 May 2021 18:45:52 GMT

OK, good, you can also strengthen the formulation by multiplying the upper bound by build[i]. If you do that, the assignFlow <= build constraints are no longer necessary, and it might speed things up if you remove them.

Re: Minimizing Facilities and Distance to Sites

DanHouston — Sat, 22 May 2021 18:52:58 GMT

I was wondering if that was necessary since it would clearly be true when nothing was assigned to it. I'll add it in if it will make things easier on the optimizer. Thanks!