Originally posted by: Stidsen

Hi

I have a running branch-and-cut algorithm, using Cplex 11.1,
where I have implemented both cut-callback and branch-callback.

It works nicely, but I have an idea to strengthen my cuts, but
then I need to get information from the branching in my cut-callback.

For this I tried to used the sequence number, i.e. in my branch-callback,
there are three possibilities, two specialized branching routines and
if none of these are applicable, I return control to Cplex to apply
standard branching. For each branch I store the sequence number I give
the branch in my own datastructure. The idea is that I use
CPXgetcallbacknodeinfo to get the current nodes sequence number and then
I can use this number to retrieve the branching information.

However this does not work: In my cut-callback I get a number
which is higher than any number I have entered in my branches.
The problem is probably in the standard-branch ... I dont perform
the standard branch, but when the nodecnt is 2 I assume that
Cplex will generate the next two sequence values, so I have to insert
the two next numbers in my datastructure. But to my surprise
it generates a number which is 3 higher ... When I add the three next
numbers to my datastructure, it works. Problem is that I am
afraid that the size of my datastructure will grow un-controllably,
because only 2 of the three numbers will be deleted ...

I have two questions:

• which sequence numbers does Cplex generate in the standard branch ?
• is there a better way to "inform" the cut-callback procedure about

the branching ?

Best Regards Thomas
, but it sometimes
generates a sequence number witch is 4 higher ????? Now it seems to
work if I generate a number of

even though
the nodecnt is 2 the following cut-callback retrieves a number
witch is 4 higher than the highest
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If I understand the <shudder>C</shudder> API calls correctly, on entry to your branch callback CPLEX will tell you want branch(es) it intends to make. When you do your own branches (via CPXbranchcallbackbranchbds or CPXbranchcallbackbranchconstraints), CPLEX will return the node number of the child node, which I hope is what you are storing in your own data structure. To get the corresponding node numbers when you want to let CPLEX manage branching, I'd suggest calling CPXbranchcallbackbranchbds with the values CPLEX passed into the callback (in effect, doing CPLEX's branches yourself), which gives you the node numbers for those nodes as well.

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

You should not make any assumptions about the sequence number that CPLEX will create for the next nodes. These numbers depend on various data that may change between different runs (for example the number of threads being used).

Like Paul said, you can use the information passed into the callback function in order to create your own branches that look exactly like the branches that CPLEX would have created. This is equivalent to performing the standard CPLEX branching but gives you the sequence number of the newly created nodes.

I did not understand completely how you use the sequence numbers. A potential improvement might be to use per-node user data (the 'userhandle' argument to CPXbranchcallbackbranchbds()). This allows you to attach user data to each node. This data can be queried by CPXgetcallbacknodeinfo() and CPX_CALLBACK_INFO_NODE_USERHANDLE from the callback and is deleted by registering a delete callback via CPXsetdeletenodecallbackfunc(). You may want to read up on these functions to check whether they allow an easier way to implement your algorithm.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Stidsen

Hi Daniel and Paul

Thanks for your prompt replies.

My problem shortly:
I have a branch-callback procedure with 3 different branch approaches:
- two different user-defined branch-callbacks: CPXbranchcallbackbranchconstraints
- in some cases I have to apply standard Cplex branching, and I simply set
*useraction_p=0; and return.

My problem is that I need to inform future cuts (in my cut-callback procedure) about
the branching decisions, this can strengthen the cuts. How can I do this ? As I see
it there are two possibilities:

• make my own data-structure, saving information in the branch-callback with the sequence-number,

and then retrieve the information from the data-structure

• alternatively (and better in my opinion) I attach the branch information to the node:

status=CPXbranchcallbackbranchconstraints(cpm->this_env, cbdata, wherefrom, mynodeest1, rcnt1, nzcnt1, rhs1, sense1, rmatbeg1, cutind1, cutval1, branch_info, &sequence_no1);
Then I want to retrieve the information in the cut-callback:
status = CPXgetcallbacknodeinfo(cpm->this_env,
cbdata,
wherefrom,
0,
CPX_CALLBACK_INFO_NODE_USERHANDLE,
(void*) branch_info);

ALAS it does not work ...

according the the manual:
"
result_p (which is my branch_info)

A generic pointer to a variable of type double or int, representing the value returned by whichinfo. (The column C Type in Table 1 shows the type of various values returned by whichinfo.)
"

Can you help me ? Where do I go wrong ? When I insert information or when I retrieve information ?
(and yes, when it works I need to create a deletecallback function).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The reference documentation is at least confusing in this regard :-(
Here is a code snippet that should illustrate how you should retrieve the information (assuming your branching information is stored in an instance of struct branchinfo):

struct branchinfo *branch_info = NULL;
 
status = CPXgetcallbacknodeinfo(cpm->this_env, cbdata, wherefrom, 0,
                                CPX_CALLBACK_INFO_NODE_USERHANDLE,
                                (void*)&branch_info);

The type in the table should be 'void *' rather than 'void' and the text should of course not limit result_p to pointers to 'int' or 'double'.
Does the above code solve your problems? If not, what is the error you see?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Stidsen

Hi Daniel

Thanks a lot. This solves most of my problems. Now i can read my
branch information. But there is one small problem left: The standard
branch ...

As mentioned earlier, in some cases (in by branch-callback) i just return
and let Cplex perform standard branch. In that situation I would like Cplex
simply to copy my data to each of the children ... This seems to work in some
cases but not in all (I suspect that Cplex copy the data to one child,
but not to the other) and hence at some point when I try to get the branch
info using CPXgetcallbacknodeinfo, I get a NULL pointer. Is there an elegant
solution to this ? (to make Cplex copy the userinfo to BOTH children ...)

I can see a solution where I "simply" perform Cplex branch in my branch callback
on the branch-variable Cplex found to me (and attach my info then), but this
is a slightly clumsy solution (me writing code to do what Cplex does more elegantly ...).

Best Regards Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think this is either a misinterpretation or a bug.
If you do not create a branch yourself then CPLEX should not attach any user info to the node it creates. In particular, if you don't take any action for the standard branch (and let CPLEX create this branch) then there should be no user object associated with the respective nodes. Are you sure that you get a non-NULL user object for nodes created by CPLEX and not by you?

If you just go with the standard branch and do not create the branches yourself that CPLEX would create then a user data value of NULL always indicates a node that was created by the standard branching rule. The only exception to this is the root node for which you can never register a user object and that will therefore always have a NULL user object (which is kind of consistent with NULL indicating the standard branch).
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Stidsen

Ok, the root-node has null-value of the userhandle that makes sense.

Standard branching (by Cplex) should also lead to null-value of the userhandle.

Hmm, but the standard-branch is often a branch on some previous non-standard
branch methods which generated some information. This information I would like
to add to the children. I seem to need to implement the standard-branching also.

Regarding the bug or misinterpretation ...

Hmm, as far as I can see the standard branch DOES copy my information (a class
with two doubles). I perform one non-standard branch and create 2 children. Then
I perform one standard branch, and create sequence number 3. In my cut-callback
I read sequence number 3 AND the branch information of the parent of node ...
I interpret/guess Cplex copy my data to one node, but not to the other node ...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

If CPLEX copies your user data to a different node, this would be bad (and probably a bug in CPLEX). Are you using a delete callback? If not, you are creating a memory leak.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Unfortunately, I have to confirm that what you are seeing is a bug in CPLEX.
If you register user data for some nodes but not for all (which implicitly happens if you do useraction = CPX_CALLBACK_DEFAULT in the branch callback) then it may happen that the user data is copied from a parent to a child node. This is not supposed to happen, hence this is a bug.
The bug does not occur if you add a non-NULL user data for all nodes (but the root node).

So you have to emulate the standard CPLEX branch by explicitly creating it and adding user data to the newly created nodes.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

It is kind of debatable whether this really is a bug in CPLEX. As far as I can see in our source code, this can only happen if you use node data without having a delete callback. To workaround this problem, just install an (even empty) delete callback.

But I agree that in some situations it is useful to attach user data to nodes that you do not need to delete. For example, you can use the user data handle to store an integer instead of a pointer. Or the user handle could point into a block of data that the user manages himself and that should not be deleted if the node gets pruned.

Therefore, we fixed this issue. The fix will be available in the next release (but not yet in the upcoming fixpack to CPLEX 12.3). But as I said, for now it should be fine to just install an empty delete callback.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Stidsen

Hi Daniel Tobias and Paul

This post just to say that the problem has been resolved and I very much
appreciate the answers (and the quickness with which you gave them).

My solution to my problem has been to perform the branch myself and attach
the info to each branch. This works fine.

I will today post another question, but it is not related to this stream
so I will start another.

Best Regards Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: S.U.N.

Hello,

Is it possible to change the pointer of a node_userhandle within the cutcallback procedure ?
In my branch-and-cut the best variable to branch on is known at the end of the cutcallback if no cuts is found. I would like to assign this information to the node in the cutcallback procedure to avoid having to recompute it again at the start of the branchcallback. (Can be time-consuming)

Having the possibility to change the pointer itself (the address it points to, instead of the content), would allow me to simply create a fixed array (int) VAR where VAR[i]=i, and then assign to the node a pointer to the address of VARvariable_to_branch_on. (Therefore, no need to add new cells during branching and no need to handle the destruction of cells assigned to a deleted node).
So, how can I change the pointer of a node_userhandle from the cutcallback procedure ?
Best regards,

Sandra
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: S.U.N.

Hello,

Is it possible to change the pointer of a node_userhandle within the cutcallback procedure ?
In my branch-and-cut the best variable to branch on is known at the end of the cutcallback if no cuts is found. I would like to assign this information to the node in the cutcallback procedure to avoid having to recompute it again at the start of the branchcallback. (Can be time-consuming)

Having the possibility to change the pointer itself (the address it points to, instead of the content), would allow me to simply create a fixed array "(int) VAR" where "VAR(i)=i", and then assign to the node a pointer to the address of "VAR(variable_to_branch_on)". (Therefore, no need to add new cells during branching and no need to handle the destruction of cells assigned to a deleted node).
So, how can I change the pointer of a node_userhandle from the cutcallback procedure ?
Best regards,

Sandra
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

It is not possible to change that pointer from a cut callback procedure.
The user object for a node is set from the branch callback by means of CPXbranchcallbackbranchbds() and friends and cannot be changed afterwards.
If you don't want to create new objects for each node you could use a global map that maps a node's sequence number to the variable to branch on.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: S.U.N.

I realise that this thread is marked "question answered", therefore I am starting a new one.

Sorry for the double post

Sandra
#CPLEXOptimizers
#DecisionOptimization