Originally posted by: SystemAdmin

Deal all,

typically when one switches the heurfreq to -1 the heuristic must stop, no matter which kind of heuristic.
That is not what is happenning and I still get solutions which are found by heuristic and are not available in cutcallback.
Is there any way to enforce "all" integer solution pass through the cutcallback.
of course there is a possibility to send incumbents by programming tricks but it has alot of overhead as the number of such variables is quite big and the memory is restrictive.
any comment is highly appreciated.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Shahin,

> Shahin G wrote:
> typically when one switches the heurfreq to -1 the heuristic must stop, no matter which kind of heuristic.

There is a separate parameter (RINSheur) that controls the frequency of the RINS heuristic, and another one (LBHeur) that controls the local branching heuristic (but this one is apparently off by default). I'm not sure whether probing can generate an incumbent -- you might need to turn that off as well. AFAIK, there is no single "master switch" to shut off all heuristics.

> That is not what is happenning and I still get solutions which are found by heuristic and are not available in cutcallback.
> Is there any way to enforce "all" integer solution pass through the cutcallback.
> of course there is a possibility to send incumbents by programming tricks but it has alot of overhead as the number of such variables is quite big and the memory is restrictive.

I don't like to turn off the heuristics, since they frequently generate a good solution sooner than straight branch-and-cut would find it. My solution involves a branch callback (as well as the incumbent and cut callbacks). I maintain a queue of new cuts in my program memory. If the incumbent callback (which is called for any incumbent, no matter how found) dislikes an incumbent, it queues one or more cuts and rejects the incumbent. If the cut callback sees a nonempty queue, it adds all the cuts in the queue and purges and purges the queue. If the branch callback sees an empty queue, it lets CPLEX handle branching. If it sees a nonempty queue, that means an incumbent was rejected after the cut callback was done. In that case, the branch callback creates a single child node by adding the cuts in the queue, but does not purge the queue (because those cuts are local to the subtree, and I want the cut callback to add them globally). So the result is an "only child" node that is essentially identical to what the current node would look like if the cut callback had been called there one more time.

I don't typically bother with a node callback, which would be necessary if I wanted CPLEX to process the new node first. I let CPLEX decide whether to work on the new child or defer it until later based on bound.

HTH,
Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul,

thanks for comment.
Your comment is very informative, indeed.
The thing is that in general often it is possible to add cuts produced from the root node in that case oen has to implement the separating routine twice, once in cutcallback and another times in incumbent callback. I was trying to find an efficient way to avoid that.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Shahin G wrote:
> The thing is that in general often it is possible to add cuts produced from the root node in that case oen has to implement the separating routine twice,

By separating routine you mean the logic that generates the cuts, right?

> once in cutcallback and another times in incumbent callback. I was trying to find an efficient way to avoid that.

I don't follow you. If you only generate cuts from incumbents, why is the root any different than any other node. If CPLEX finds an incumbent at the root node, it will call the incumbent callback, which can generate the cuts. When I do Benders decomposition, I never generate cuts in the cut callback, only in the incumbent callback.

If you want to generate cuts from non-integer solutions, then you need to put the cut generation routine someplace else (and the cut callback makes sense). But even then, wouldn't you be coding the cut generator once and just calling it from two different callbacks?

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

>>>"If you only generate cuts from incumbents"
That is the key here. I dont only work with incumbents. the fractionals are also of value for generating cuts.

many thanks, seems like I have to resort to some programming stuff.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Paul,
What do you mean by "dislike" in your text.
All incumbents can be used to generate cuts, isnt it? if so why chose beteen them?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Shahin,

> Shahin G wrote:
> What do you mean by "dislike" in your text.
> All incumbents can be used to generate cuts, isnt it? if so why chose beteen them?

I was thinking in terms of Benders decomposition, and by "dislikes" I meant "rejects". In Benders, you typically generate a cut only if the proposed incumbent is infeasible in the true problem, either because it violates a constraint in the underlying model or it understates the objective value (minimization). So the incumbent callback generates a cut (or multiple cuts) and then rejects the proposed incumbent.

In more general contexts, I suppose you can use an incumbent to generate cuts that strengthen the formulation and still accept the incumbent. Maybe. I can't think of any instances off-hand, but that probably just means I have a narrow perspective.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Shahin,

it is true that setting the heuristic frequency to -1 should turn off all heuristics. If you still see heuristic solutions in CPLEX 12.1 or earlier versions, I think this indicates a bug (at least if you did not explicitly activate some special heuristics like RINS or local branching).

In CPLEX 12.2, however, we added deterministic parallel root node processing. There, we call some algorithms that are not heuristics but potentially stumble across primal feasible solutions. These are then added as if a heuristic found them, and as far as I know, this is not disabled by setting the heuristic frequency to -1.

If this happens in your case, you can additionally turn off the parallel root node stuff by setting the "mip limits auxrootthreads" parameter to -1. Of course, setting the global threads parameter to 1 should also help but may be a bit too drastic.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Tobias,
Yes, I am still on 12.1 and did not yet moved to 12.2.
I do it. Thanks.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias,

I used single thread in 12.2. The the integer solution is observed in incumbentcallback before being observed by cutcallback.
It does not seem to be heuristic but some thing is happening here!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

There clearly is something else in CPLEX that is producing heuristic solutions that is not turned off by HEURFEQ and potentially takes a very long time.

Consider the following output from CPLEX:

---

CPLEX> read test.lp 
Problem 'test.lp' read.
Read time =    0.14 sec.
CPLEX> read test.prm
Parameter file 'test.prm' read.
CPLEX> opt 
Clique table members: 8479.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time =   36.34 sec.
 
        Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
      0     0      120.0000  1079                    120.0000    17073         
*     0     0      integral     0      120.0000      120.0000    17073    0.00%
Elapsed time = 282.74 sec. (tree size =  0.00 MB, solutions = 1)
 
Solution pool: 1 solution saved.
 
MIP - Integer optimal solution:  Objective =  1.2000000000e+02
Solution time =  282.74 sec.  Iterations = 17073  Nodes = 1
 
CPLEX>

---

Note how CPLEX solves the root node in 36 seconds but then spends about 4 minutes doing something to produce an integer solution (it clearly hangs for a long time between producing the first line for node 0 and the second line for node 0). I have tried to turn off all heuristics, cutting, preprocessing,...
What else is left that I can turn off???

The parameter settings (test.prm) used are:

---

CPLEX Parameter File Version 12.1.1
CPX_PARAM_CLOCKTYPE              1
CPX_PARAM_PREIND                 0
CPX_PARAM_TILIM                  1.80000000000000e+03   
CPX_PARAM_PREPASS                0
CPX_PARAM_PRELINEAR              0
CPX_PARAM_MIPINTERVAL            1
CPX_PARAM_HEURFREQ               -1
CPX_PARAM_PROBE                  -1
CPX_PARAM_FRACCUTS               -1
CPX_PARAM_CUTPASS                -1
CPX_PARAM_RINSHEUR               -1
CPX_PARAM_REPEATPRESOLVE         0
CPX_PARAM_PROBETIME              0.00000000000000e+00   
CPX_PARAM_FPHEUR                 -1
CPX_PARAM_EACHCUTLIM             0
CPX_PARAM_NODELIM                1
CPX_PARAM_THREADS                1
CPX_PARAM_MIPSEARCH              1

---

This is really annoying since I have a much faster heuristic but CPLEX refuses to invoke my heuristic callback until it has finished the mysterious time wasting activity that can be seen here. For larger instances this time between the initial relaxed LP solve to getting control back in a heuristic callback (or at the end of the root node) can blow out to half an hour or more.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I can see one place in the source code where we do not check for CUTPASS but only for all of the individual CUT parameters. This places triggers two different things that may be the reason for the long delay.

Could you please try to disable all of the CUTs individually, i.e.,

CPX_PARAM_CLIQUES -1
CPX_PARAM_COVERS -1
CPX_PARAM_FLOWCOVERS -1
CPX_PARAM_IMPLBD -1
CPX_PARAM_GUBCOVERS -1
CPX_PARAM_FRACCUTS -1
CPX_PARAM_FLOWPATHS -1
CPX_PARAM_MIRCUTS -1
CPX_PARAM_DISJCUTS -1
CPX_PARAM_ZEROHALFCUTS -1
CPX_PARAM_MCFCUTS -1

Additionally, I would be very interested in your "test.lp" file such that I can check in detail which algorithm causes the long delay. Could you please send this to my email address achterberg at de dot ibm dot com?

Thanks,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks. That worked like a charm.

Clique table members: 8479.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time =   35.56 sec.
 
        Nodes                                         Cuts/ 
   Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
      0     0      120.0000  1079                    120.0000    17073         
      0     2      120.0000  1079                    120.0000    17073         
Elapsed time =  38.39 sec. (tree size =  0.00 MB, solutions = 0)
 
 
MIP - Node limit exceeded, no integer solution.
Current MIP best bound =  1.2000000000e+02 (gap is infinite)
Solution time =   38.39 sec.  Iterations = 17073  Nodes = 1 (2)

Not sure why it still creates a clique table but it clearly now works the way I would have expected it to.
#CPLEXOptimizers
#DecisionOptimization