Originally posted by: gangulo

Hi,

I'm facing the following problem with CPLEX 12.4, C API, Linux. I have an incumbent callback that checks a candidate solution given by CPLEX. If it is rejected, it also constructs a feasible solution that is stored somewhere else. What I want to do is to inject the solution that I found with a heuristic callback. However, I found the heuristic not being called as often as I expected, or even not called at all, leading to wrong results. As far as I know, if the current node if feasible and not cut off, then the heuristic should be called, and then the incumbent callback is invoked. Is there any interaction between these two callbacks that may prevent the heuristic being called?

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: gangulo

As an example, consider the following code:

#include <ilcplex/cplex.h>   #include <ctype.h> #include <stdlib.h> #include <string.h> #include <math.h>   

int heuristicCallback     (CPXCENVptr env, 

void *cbdata, 

int wherefrom, 

void *cbhandle, 

double *objval_p, 

double *x, 

int *checkfeas_p, 

int *useraction_p);   

int incumbentCallback (CPXCENVptr env, 

void       *cbdata, 

int        wherefrom, 

void       *cbhandle, 

double     objval, 

double     *x, 

int        *isfeas_p, 

int        *useraction_p);   

int main (

int  argc, 

char *argv[]) 
{ 

int status = 0;   CPXENVptr env = NULL; CPXLPptr  lp = NULL;   env = CPXopenCPLEX (&status);   status = CPXsetintparam (env, CPX_PARAM_SCRIND, CPX_ON);   lp = CPXcreateprob (env, &status, argv[1]);   status = CPXreadcopyprob (env, lp, argv[1], NULL);   status = CPXsetheuristiccallbackfunc (env, heuristicCallback, NULL);   status = CPXsetincumbentcallbackfunc(env, incumbentCallback, NULL);   status = CPXsetintparam(env, CPX_PARAM_REDUCE, CPX_PREREDUCE_PRIMALONLY);   status = CPXmipopt (env, lp);   

return 0; 
}   

int heuristicCallback (CPXCENVptr env, 

void       *cbdata, 

int        wherefrom, 

void       *cbhandle, 

double     *objval_p, 

double     *x, 

int        *checkfeas_p, 

int        *useraction_p) 
{ fprintf (stdout, 
"H\n"); 

return 0; 
}   

int incumbentCallback (CPXCENVptr env, 

void       *cbdata, 

int        wherefrom, 

void       *cbhandle, 

double     objval, 

double     *x, 

int        *isfeas_p, 

int        *useraction_p) 
{ fprintf (stdout, 
"I\n");   *isfeas_p  = 0; *useraction_p = CPX_CALLBACK_SET;   

return 0; 
}

The code reads an lp/mps file and rejects all solutions (note that I have to turn off dual reductions), but I think it should call the heuristic anyway. As an example, try

Minimize obj: 40 x_1 + 60 x_2 + 47 x_3 + 68 x_4 + 60 x_5 Binaries x_1  x_2  x_3  x_4  x_5 End

In the output, I only see I's and no H's, why?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When running this example two things happen:
1. During the root node the incumbent callback is invoked much more often than the heuristic callback. This is expected since CPLEX's heuristics may produce incumbents more frequently than the heuristic callback is invoked.
2. In the tree all nodes are integral. That is, the incumbent callback is invoked for an integral node (wherefrom == CPX_CALLBACK_MIP_INCUMBENT_NODESOLN). If an integral node is rejected by the incumbent callback then CPLEX will not invoke the heuristic callback for that node.
Since all nodes in the tree are integral the heuristic callback is never invoked.
As you can see, there are some special cases in which the incumbent callback is invoked at a node but the heuristic callback is not.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: gangulo

Hi Daniel,

From the user's manual (heuristic callback):

After this routine has been called, CPLEX calls the user callback function at every viable node in the branch & cut tree. (A node is viable if its LP relaxation is feasible and its relaxation objective value is better than that of the best available integer solution.)

From the above lines, the heuristic callback should be called even if the node is integral. I guess that a rejected incumbent makes a different case. Still, it would be quite useful to know the order in which different callbacks are invoked for an integral node. I would really appreciate that.

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Currently (CPLEX 12.5) it works like this, but this is not set in stone so can change in later versions:

1. Switch to new node
2. MIP/info callback
3. If node dual bound >= cutoff, goto 10
4. Solve LP relaxation (solve callback)
5. If feasible but fractional: cut callback
6. If feasible and integral: lazy constraint/cut callback
7. If feasible and integral: incumbent callback
8. If node dual bound < cutoff: branch callback
9. If node dual bound < cutoff: heurisitic callback
10. If tree is not empty: node callback
11. If tree is not empty, goto 1

So, if the LP relaxation at the node is integral, and the solution is accepted in steps 6-7, then the dual bound of the node will be equal to the cutoff value (which is then the objective of the newly found incumbent solution). Thus, neither a branch nor heuristic callback will be invoked, because the node will be pruned.

Tobias
#CPLEXOptimizers
#DecisionOptimization