Originally posted by: SystemAdmin

[bengu said:]

Hi,

I am working on a MIP model, and when I try to solve it using Cplex, it starts with huge MIP gap (like 800%), then comes down to less than 5%. Why is this happening ?. Is there any parameter (MIP-Emphasis ?)to avoid this ?. For certain model, performance is getting hit to drop from such high MIP gap to reasonable mip gap.

Thanks in advance.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[achterberg said:]

I don't understand the issue. Would you prefer not seeing this very bad solution with 800% gap and wait until a better solution has been found before reporting a first incumbent?

My guess is that the very bad solution comes from a primal heuristic that we apply before solving the root LP (even though this is only displayed in the log after the root LP has been solved). This heuristic is very fast but usually produces very bad solutions. Nevertheless, it is often still useful for a user to see very fast that his model has a feasible solution, since this can be understood as an indication that the model is correct.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[bengu said:]

Hi,

Thanks for the response. For most of the data instances, it starts with 800% gap and the gap falls down to less than 5% quite fast, but for few instances it takes very long time to come down to a gap of less than 10% (hangs around at a gap of 800% range for a longer time). Is there any suitable parameter to be used to bring the gap sooner (may be switch off the heuristics ?).

Thanks in advance.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[TheEngineer said:]

You most certainly do not want to optimize the gap during the optimization process but rather the objective function. A relative gap x describes only that a feasible integer solution proved to be within x percent of the optimal has been found. A high relative gap (800%+) is relative to the first solution found therefore you could try to change the root algorithm to find another starting solution.

As you already pointed out this percentage number differs from problem to problem and is - at least for higher values of the gap - not a valid number to compare solutions.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[bengu said:]

Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[achterberg said:]

My guess is that in all cases the very simple heuristics that we apply at the very beginning are successful in finding a solution, but this is of poor quality (800% gap).

Then, in some cases, the more complicated and powerful heuristics we apply at the root node find good solutions (small gap), but on some problem instances they fail. Thus, what you probably need to do is to crank up the heuristic parameters.

If you have CPLEX 12, one option is to use polishing (also available in CPLEX 10 and 11, but not as convenient). For example (using interactive commands as an example):

set mip polishafter nodes 1
set mip limits nodes 2
mipopt
set mip polishafter nodes 2100000000
set mip limits nodes 2100000000
mipopt

to conduct one round of polishing after the root node has been solved, and then continue the regular solve as usual.

Another alternative is to just try the different MIP emphasis parameters, in your case either


set emphasis mip 1

or

set emphasis mip 4


Then there is the heuristic frequency parameter, which you could, in the extreme case, set to 1:

set mip strategy heuristicfreq 1


You could also try the feasibility pump heuristic:

set mip strategy fpheur 1

or

set mip strategy fpheur 2


Note that all of these settings can have positive or negative effect on your models. If the effect is not undoubtly positive, I would suggest to stick to the default settings. But you also can try the tuning tool to find out preferable parameter settings for your problem class.

#CPLEXOptimizers
#DecisionOptimization