Originally posted by: rocarvaj

Hello!

I want to identify different types of nodes in the B&B tree:

• Fathomed (by bound)
• Integer
• Infeasible

I want to make sure I'm reading the documentation right. According to the CPXsetbranchcallbackfunc function documentation, if the branch callback is called by CPLEX with the variable nodecnt set to 0, that means that the current node is integer. So does this mean that  if I want to identify nodes fathomed by bound or infeasibility I have to use other callbacks since the branch callback will never be called in those cases?

What would you recommend?

Thanks in advance,

Rodolfo

I think you will have to use node user data with a combination of callbacks:

1. In a branch callback create the branches that CPLEX would create but attach a user data object to each node (function CPXbranchcallbackbranchasCPLEX is a convenient way to do that).
2. In a node select callback just select the node that CPLEX would suggest but change the node's user data to reflect that the node has been selected (functions CPXcallbacksetuserhandle and CPXcallbacksetnodeuserhandle can be used to change a node's user object).
3. In a solve callback just use the default solving strategy but update the node's user object to indicate that the solve callback was invoked. Nodes that are LP infeasible can be detected in the solve callback.
4. In a delete callback check the user object of the node. If the solve callback was not invoked for the node and the node was never selected by the node selection callback then the node was fathomed by bound. If the node was selected but the solve callback was not invoked on it then it was proven infeasible by node presolve. If the solve callback was invoked then you already know whether it was feasible or infeasible.
5. Integer feasible nodes can be detected in the branch callback by testing that CPLEX would not create any branches.

Originally posted by: anahana

Hi guys, hope you don't mind me jumping in.

I'm trying to do something similar, but simpler. I only need to know if a node was fathomed (for whatever reason). I'm using Concert and it seems that it does not provide access to a deleteCallback. Is there another way to do this?

Regards, 

In Concert there is no delete callback. In Concert C++ the data attached to a node must be an instance of IloCplex::MIPCallbackI::NodeData. You need to subclass this and override the destructor. Then you can use the destructor to be notified when a node gets deleted.

In Java you just have the node data implement the IloCplex.MIPCallback.NodeData interface. The delete() method of that interface is invoked when a node gets deleted.

Everything else from the discussion above should be the same in Concert.

Originally posted by: anahana

Thanks, but why override the destructor? Can't I just have it flag some variable each time it is called? That will tell me when node data was removed and hence the node was removed... assuming I understood you correctly. 

Regards,  

Originally posted by: gangulo

Hi Daniel,

I followed your approach and managed to track the fathoming process using tags. I have one question though. In step 3, when the solve callback is invoked, I can solve the node LP manually with dual simplex and check whether the node is infeasible or not. However, I think that when I let CPLEX solve the node LP by its own, it can optimize the process, for example, by imposing a limit on the objective value of the LP (it cannot exceed the current global upper bound of the MIP, otherwise we can prune it.) Thus the manual approach is less efficient, but it lets me check the status of the node LP after optimization. So what I did was to attach an LP pointer as cbhandle, shared by the solve and delete callbacks: it points to the last LP solved by CPLEX and, in combination with the tags, it lets me check the status before deleting the node. Then my question is: how safe is this approach? Actually, I thought it wouldn't work because the delete callback does not let me retrieve a pointer to the LP node being deleted, and what I described above would be a workaround for this.

Thanks!

I did not understand what you are doing with this LP pointer you attach to the nodes but your approach sounds pretty unsafe. Why exactly do you need the LP pointer in the delete callback? Can't you just make all the required queries in the solve callback and increase the number of different tags to reflect what ever you found out in the solve callback?

Originally posted by: gangulo

When the solve callback is invoked, I store a pointer to the current node LP, but I let CPLEX solve it (I do not call dual simplex or any other algorithm.) Then, when the delete callback is invoked, I can query the lpstat of the LP given by the pointer. By doing this I realized that there are many node LPs whose lpstat is 12, that is, the optimization was stopped by an objective limit. I understand that I could skip this if I solved manually the node LP with dual simplex and then queried the lpstat within the solve callback, but it seems to me that solving the node LPs that way would be less efficient than letting CPLEX handle them (I guess CPLEX internally makes some changes to speedup the process, like imposing an objective limit.) Now, if for a given node the solve callback is invoked but not the branch callback, then this node will be fathomed by bound or infeasibility in the next call to the delete callback (there are no other nodes deleted in the interim, right?) In this situation, can I assume that the pointer I store in the solve callback still points to the same node LP when I use it in the delete callback?

What you are doing seems pretty risky to me: Between the solve and the branch callback (or the point at which the node is fathomed) CPLEX may decide to run heuristics which in turn may result in pruning additional nodes from the tree. So you may have interleaving calls to the delete callback.

However, if you store the LP pointer as the node's nodedata (in the solve callback) and read it from there in the delete callback then you should be fine (since nodes that are pruned but are not the current node will have a nodedata of NULL).

In any case, I don't think that this use of the nodelp pointer (storing it across several callbacks) is officially supported, so be prepared that odd things may happen.