Gurobi taking too much time

[lahlou aziz]

Hi,

I am experiencing a huge work-time since yesterday and no improvement were made since a long time.

Could any one explain me why it is taking so much time ?

Just for information, the inputs to my MILP are : a Graph of nodes and links and a set of requests R (each request is a graph of 7 nodes, I am trying to solve a kind of assignment problem adapted to my optimization problem).

Please find attached the log.

Regards,

Aziz

[Daniel Espinoza]

Hi Aziz,

Have you tried to find a good set of tuned parameters using a couple of smaller instances and try those in the harder problems?

Also, the default gap termination criteria may be too conservative for your application, changing it to 0.1% would mean to solve the problem in 12 minutes.

Best,

Daniel

[lahlou aziz]

Hi Daniel, 

To be honest I never tried to set tuned parameters as I am not aware of how to do it.

Could you please point me out to how to set those parameters and especially regarding the default gap termination criteria. I have to admit that I am not familiar with these concepts.

Best,
Aziz

[Daniel Espinoza]

Hi Aziz,

For tuning, here is the documentation:

http://www.gurobi.com/documentation/7.5/refman/parameter_tuning_tool.html

For termination criteria there are a couple of parameters:

http://www.gurobi.com/documentation/7.5/refman/parameters.html

In particular mipgap:

http://www.gurobi.com/documentation/7.5/refman/mipgap2.html#parameter:MIPGap

Essentially a mipgap of zero is asking to prove that you have the best possible solution (within floating point tolerances)

whereas mipgap 1e-3 is saying that you want a solution proven to be the best possible with an error of (up to) 0.1% (within floating point tolerances)

Best,

Daniel

[lahlou aziz]

Hi Daniel,

Thank you so much for these references.

I tested the MIPGAP with a value of 0.1 and it works pretty well as you said in less than 13 minutes !

I will have a look into the tuning parameters and combine them with MIGAP.

Best,

Aziz

[lahlou aziz]

Hi Daniel,

So does the best solution is the optimal one ? I mean I have to find the optimal solution. I need to have some clarifications on this as I am writing a paper so I do not want to make mistakes.

Thanks

Aziz

[Michael Winkler]

Hi Aziz,

at the end of your optimization process you always have a best solution (if any was found). You might say that any incumbent is an optimal solution w.r.t. the current MIP gap. But optimality for the whole problem instance is only proven when the dual and primal bound are identical in the end, i.e., the MIP gap is 0.
So setting MIPGAP=0.1 will provide you with an optimal solution with respect to this MIP gap (or the one stated in the log), but there might exist better solutions and one optimal solution for your problem instance can only be guaranteed to be found if you set MIPGAP=0.

Best,
Michael

[lahlou aziz]

Hi Michael,

Thanks a lot for your explanations and clarifications.

Best,

Aziz