Originally posted by: Zacharie_ALES

Hello,

I have a question concerning the integer parameter HeurFreq. If I understand correctly the aim of the heuristics is to find integer solutions. However it seems to change (directly or not) the relaxation of my problem.

I am running cplex on a minimization problem without branching,  without the automatic cuts of cplex and with one of my cut callback. If I turn off the heuristic (parameter HeurFreq to -1) I don't find any integer solution and I get at the end a relaxation of 1900 (this part seems fine). However, if I set the parameter HeurFreq to 0 (the default value), I get at the end an integer solution of 5200 and the same value for the relaxation (so the problem is solved optimally).

I understand why the heuristic enable to find an integer solution. What I don't understand is how it can modify the relaxation. I thought only branching or adding cuts could improve it (and in both cases the exact same cuts were added). Do you have any idea?

Originally posted by: T_O

Any integer feasible solution may allow pruning huge parts of the B&B tree. So maybe, some subtree has lp value 6000. Then it obviously can be cut off.

Thomas

Originally posted by: Zacharie_ALES

Ok, I see. But can cplex still do that when there is no branching?  (I set the node limit to 0)

Originally posted by: T_O

No, but it might do other things at the root node (reduced cost fixing, more aggressive cut generation, ...).

Thomas

Originally posted by: Zacharie_ALES

Thanks for your answers. Since I removed the automatic cuts I guess it's not this part which changes the relaxation. I don't really know how the reduced cost work, can it be disabled?

I changed the MIPDisplay parameter in order to have has many logs as possible and I got the following when the relaxation is improved (the value are not exactly the same as in my first post since I used a smaller instance to do my tests) :

*     0+    0                         4809.0000      1925.5000       98   59.96%
Found incumbent of value 4809.000000 after 0.71 sec. (413.65 ticks)
Reinitializing dual norms . . .

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth

      0     0        cutoff           4809.0000      4809.0000       98    0.00%    

The relaxation is modified just after a new integer solution is found and the improvement may comes from the message:

Reinitializing dual norms . . .

Do you think the relaxation modification occurs during this process? If yes, do you know if I can disable it? (I did not find a corresponding parameter yet)

Originally posted by: T_O

I don't really know what exactly is happening. "Reduced cost fixing" means you can tighten bounds for some reason if you know some integer feasible solution. This was just one idea that I had. It might have completely different reasons.

Reinitializing dual norms just means that something is done in order to speed up the dual simplex method. This should not affect the objective value.

Thomas

Originally posted by: Zacharie_ALES

It seems that the root relaxation was improved thanks to the primal/dual reduction. Turning it off enabled to obtain the effect of my cuts on the relaxation.

Thanks again for the help.