Avoiding unnecessary scanning of solution Space

Problems with modeling
Post Reply
Posts: 3
Joined: 2 years ago

Avoiding unnecessary scanning of solution Space

Post by Adam92 » 2 years ago

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

i "all nodes" /i1*i40/
WH(i) "only potential Warehouse locations" /i1*i10/
K(i) "only customer sites" /i11*i140/


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.

WHKAPA Capacity of a warehouse
d(K) Demand of a customer.
Cfix Opening Costs for a warehouse

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

Posts: 108
Joined: 3 years ago

Re: Avoiding unnecessary scanning of solution Space

Post by cladelpino » 2 years ago

Nice analysis!

I have a warning and a suggestion to make:

The warning: Have in mind that in most cases CPLEX chooses to use its propietary and secret "dynamic search"... It is (AFAIK) "impossible" (unless you stop the solver at every iteration) to really know which nodes are being tested. How did you obtain the data that you mention to understand your search process ? Anyway, my warning is perhaps you could try with classical B&B and the higher display options and then really tinker with the tree.

The suggestion implies the heuristic callback: Perhaps you can create a "good integer solution" by just selecting one of the many warehouses with nonzero relaxed values and fixing the rest at zero. This, of course, disables the "dynamic search".

Good luck!

Post Reply