Originally posted by: rocarvaj

Hello!

I'm using a branch callback just to attach some information to the nodes (by using CPXbranchcallbackbranchasCPLEX) and I see that at a certain node CPLEX is branching on a binary variable that is 0.0 in the current LP relaxation. Actually, if I ask for integer feasibility of variables using CPXgetcallbacknodeintfeas, CPLEX tells me that the variable is integer feasible.

Why is CPLEX branching on this variable? Could CPLEX do this or should I triple check my code for something wrong?

Thanks in advance!

Rodolfo

Originally posted by: rocarvaj

I just wanted to add that, if CPLEX does in fact branch using an integer feasible variable (which is strange), I don't understand the following:

If I look at the current LP at the node in which CPLEX is going to branch (I turn off presolve, so the node LP is in terms of the original variables), the variable bounds are fixing it. I see something like "x579 = 0", but If I check the presolve status of the variables using CPXgetprestat I see that the variable is not fixed.

Why do I get this discrepancy?

I'm attaching a short code that runs an instance and stops whenever it finds that CPLEX is going to branch on an integer feasible variable. It then writes the current node LP to disk. I get the behaviour described above with CPLEX 12.5 and aflow40b.mps.gz from MIPLIB. Just in case someone wants to try and replicate this.

Thanks in advance for any thoughts on this.

Rodolfo

Originally posted by: gtoptimizer

Hey, I have two quick points:

1. I agree that it is strange for CPLEX to branch on an integer feasible variable, but it does not seem problematic to me (maybe it is for your particular method?). For a binary variable, one of the children will be identical to its parent (and hence fathomed), while the other child will be different and is added to the list of nodes to process. After all, branching on least/most infeasible variables is just a heuristic, right?
2. My understanding is that CPXgetprestat gives variable mappings from original to presolved and vice versa. I don't think that these mappings are updated as the problem is solved, i.e. x579 is not fixed at 0 because that is the case in the original MIP, and that is what this function in fact returns. I might be mistaken though.

Originally posted by: PierreBonami

Hi,

For the second question, gtoptimizer is correct.

For the first one, I am not sure but maybe this is because you are using CPLEX 12.6.0 or more recent?

We changed the argument of branching callbacks (because we know allow users to branch on continuous variables now). The prototype of a branch callback shoule be now:

int branchcb (CPXCENVptr env,
                void *cbdata,
                int wherefrom,
                void *cbhandle,
                int type,
                int sos,
                int nodecnt,
                int bdcnt,
                const int *nodebeg,
                const int *indices,
                const char *lu,
                const double *nodeest,
                const double *bd,
                int *useraction_p);
 

Notice that nodeest moved and bd became an array of double. Normally we changed the position of nodeest so that compilers would not compile (indeed your code didn't compile on my machine).

Originally posted by: rocarvaj

You're right @gtoptimizer, thanks for pointing that out.

@PierreBonami Actually I'm using CPLEX 12.5. So you mean that branching on an integer feasible variable should not happen in CPLEX? @gtoptimizer is right in the sense that doing that does not make the B&B algorithm incorrect, but it is just very redundant to create a branch like that.

I'm just trying to learn if I should expect this behaviour from CPLEX and code accordingly.

BEst,

Rodolfo

Originally posted by: PierreBonami

Hi,

Branching on integer feasible variables might happen but should be rare (unless you set integer tolerance to 0.0). Sorry for the fuzzy answer...

I tried your code with the latest version of CPLEX (after modifying the arguments of the callback) and it didn't happen on my machine so I can't really tell more for this case.

Best,

Pierre

Originally posted by: rocarvaj

Thanks for your reply, Pierre.

Can I bother you with one more thing? when you ran my code did you put a time limit in the argument? (the code takes as arguments the time limit and the file name of the instance). I'm telling you this because if you don't put a time limit the code doesn't do anything.

I ran the code using CPLEX 12.6.1 and I still see branching on integer feasible variables. Also, I haven't changed the integer tolerance at all.

Thanks,
Rodolfo

Originally posted by: PierreBonami

Hi Rodolfo,

Yes sorry I had missed the additional argument but now I can reproduce what you see and understand what is happening.
The short answer is that it can happen that the branching variable indicated by the callback is fixed so you don't need to triple check your code for this.

The long answer is more subtle but let me try to give a short explanation.

CPLEX is branching on the variable it indicates in the callback and it was not integer
feasible at the time it was picked for branching. The thing is that it also
found out that the variable could be fixed.
In this case CPLEX without callback would perform the fixing and proceed to the
next node (which corresponds to this fixing).
Now what you see in the callback is actually caused by the extra work CPLEX does to
present consistent data to the callback. To do so it needs to resolve
the LP and therefore returns to you a solution that has the branching variable fixed.

I hope this clarifies.

Best,

Pierre

Originally posted by: gangulo

Hi,

I tried the code adapted for CPLEX 12.6.1 and I see branching on variables that are integer feasible. If I remove the exit(0) instruction of the branch callback, I see a bunch of variables for which this happens.

I also looked at the root node just before the child nodes are created, and many variables are already fixed to 0. Can this happen if presolve is turned off? 

Originally posted by: PierreBonami

Hi,

Yes there may be variables that have been fixed after presolve (by cuts, or others). This is independent of presolve being on or off.

Best,

Pierre