Heuristics for hard MIP model

[manuelfu...@gmail.com]

Good afternoon,

First of all I want to congratule you for such a group. I have solved some questions coming here to read you. I think it is very helpful!

Now that Gurobi has an API for Python3 I am giving it a chance. Up to now, I have been using CPLEX with GAMS (last version of both) for solving a hard MIP problem. The only way I could find to find good solutions is to use the Barrier Method and the Solution Polishing (based on RINS), combined with parallelization (8 threads).

The way: providing an initial solution, then solving the LR with the Barrier Method and then activating the Solution Polishing heuristic after node 1 -from the very begining-. The solutions are acceptable after a couple of hours.

Now I have developed the same model in Python with Gurobi. I have checked it is exactly the same, with the same size, no. of vars and constraints.

I provide Gurobi the same initial solution, with the same objective value.

Then I try to solve it and here it is where the problems comes: I am not able to get reasonable good solutions at all. The objective function remains at around 70%.

The main parameters I am using are the following:

m.params.Threads = 8

m.params.timeLimit = 36000

m.params.Method = 2

m.params.Cuts = -1

m.params.NoRelHeuristic = 1

m.params.Heuristics = 1

m.params.RINS = 1

m.params.ImproveStartNodes = 1

m.params.ImproveStartTime = 1

m.params.MIPFocus = 1

Now I am running the grbtune tool in order to obtain any clues. By the way, do you have any ideas about how to reproduce (or even improve, hopefully) the performance I get with CPLEX?

I have read there is not a "solution polishing" feature in Gurobi due to patents, but I have also read there are a few options that can produce a similar result. Am I missing anything? Because I cannot believe there is such a huge difference!

All opnions are really appreciated.

Thanks,

Manuel.

[Daniel Espinoza]

Hi Manuel,

Maybe the heuristic option will help:

http://www.gurobi.com/documentation/7.5/refman/heuristics.html#parameter:Heuristics

You can also try concurrent optimization 

http://www.gurobi.com/documentation/7.5/refman/concurrentmip.html#parameter:ConcurrentMIP

Now, limiting start nodes and time does not seem like a good Idea for your usage case.

Out of curiosity, can you share the model or a version of it? even better, a set of varying sizes?

Hope that helps a bit,

Best,

Daniel

[manuelfu...@gmail.com]

Thank you for your response, Daniel!

Yes, I am already using the Heuristics parameter.

The ConcurrentMIP is interesting also, but I do not think it fits in this model. As far as I understand, it is intended to look for solutions in parallel, making use of different parameters.

The thing is that I cannot find a solution even using one thread, so this is not going to help much. By the way I am giving it a try!

Regarding the varying sizes, are you asking me for the model size? If so, here you have it, from the log:

Optimize a model with 57438 rows, 356468 columns and 1713500 nonzeros

Variable types: 0 continuous, 356468 integer (356468 binary)

And after the presolve:

Presolved: 37833 rows, 346366 columns, 1149407 nonzeros

Variable types: 0 continuous, 346366 integer (346366 binary)

I am stuck :s

[Daniel Espinoza]

HI Manuel,

I was asking for the models to see if we could learn something from it, you said that CPLEX was able to find solutions relatively quickly? If so, and you could share the models, and some solutions to them, I'll like to take a closer look.

Best,

Daniel