### Avoiding unnecessary scanning of solution Space

Posted:

**Mon Mar 12, 2018 8:57 am**Hello together,

This is my first Post, so I hope that I chose the right thread

I have the following problem:

I implemented a location routing problem. While checking the .log file I noticed something that could speed up the calculation time immensly if I fixed it.

Let me state an example first:

Let's assume that we have a set S of all nodes consisting of s1*s140 nodes whereas nodes i1*i10 represent potential Warehouses and i11*i140 represent customers to be served. So we have have

Sets

i "all nodes" /i1*i40/

WH(i) "only potential Warehouse locations" /i1*i10/

K(i) "only customer sites" /i11*i140/

alias(i,j)

Binary Variables

z(WH) 1 if warehouse location WH is opened

y(K,WH) 1 if customer site K is assigned to warehouse WH

x(i,j) If node j is immediately headed to after node i.

Parameters

WHKAPA Capacity of a warehouse

d(K) Demand of a customer.

Cfix Opening Costs for a warehouse

dist(i,j)

The objective function minimizes the fixed opening costs and the routing costs.

While setting the capacity of a warehouse large enough to be able to serve all customers and setting high opening costs for each warehouse my assumption was that the optimal solution would consist of one warehouse being opened which serves all customers.

My assumption was right however I noticed that CPLEX takes a very long time to check the solution space for opening way to many Warehouses, first.

The optimality Gap then "jumps" to a near optimal solution when fewer Warehouses are opened (see attached screenshot). So basically a lot of time is spent scanning obviously "bad" solutions. Actually I consciously used examples where the obviously best solution would have to consist of one Warehouse only.

My question to you:

How can I "direc"t CPLEX to checkout solutions consisting of one Warehouse opened first without giving a maximal number of possible opened warehouses within the model (i. e. sum(WH, z(WH)) =l= 1 ; )

I tried Branching prioritys using the .prior suffix and the mipordind = 1 option. Cplex still checked solutions consisting of 10 Warehouses opened so I assume it did not help.

I also tried to set the Warehouse opening costs ridiculously high. However solutions that included opening the maximum number of possible warehouses were still checked and time lost.

Sorry for the long post

I hope I have put all necessary information in

Looking forward for your advice

Kind Regards

Adam

This is my first Post, so I hope that I chose the right thread

I have the following problem:

I implemented a location routing problem. While checking the .log file I noticed something that could speed up the calculation time immensly if I fixed it.

Let me state an example first:

Let's assume that we have a set S of all nodes consisting of s1*s140 nodes whereas nodes i1*i10 represent potential Warehouses and i11*i140 represent customers to be served. So we have have

Sets

i "all nodes" /i1*i40/

WH(i) "only potential Warehouse locations" /i1*i10/

K(i) "only customer sites" /i11*i140/

alias(i,j)

Binary Variables

z(WH) 1 if warehouse location WH is opened

y(K,WH) 1 if customer site K is assigned to warehouse WH

x(i,j) If node j is immediately headed to after node i.

Parameters

WHKAPA Capacity of a warehouse

d(K) Demand of a customer.

Cfix Opening Costs for a warehouse

dist(i,j)

The objective function minimizes the fixed opening costs and the routing costs.

While setting the capacity of a warehouse large enough to be able to serve all customers and setting high opening costs for each warehouse my assumption was that the optimal solution would consist of one warehouse being opened which serves all customers.

My assumption was right however I noticed that CPLEX takes a very long time to check the solution space for opening way to many Warehouses, first.

The optimality Gap then "jumps" to a near optimal solution when fewer Warehouses are opened (see attached screenshot). So basically a lot of time is spent scanning obviously "bad" solutions. Actually I consciously used examples where the obviously best solution would have to consist of one Warehouse only.

My question to you:

How can I "direc"t CPLEX to checkout solutions consisting of one Warehouse opened first without giving a maximal number of possible opened warehouses within the model (i. e. sum(WH, z(WH)) =l= 1 ; )

I tried Branching prioritys using the .prior suffix and the mipordind = 1 option. Cplex still checked solutions consisting of 10 Warehouses opened so I assume it did not help.

I also tried to set the Warehouse opening costs ridiculously high. However solutions that included opening the maximum number of possible warehouses were still checked and time lost.

Sorry for the long post

I hope I have put all necessary information in

Looking forward for your advice

Kind Regards

Adam