Originally posted by: UserCplex

Hello,

 

As CPLEX MIP progresses, I have written a branch callback to save branching decisions made by CPLEX and the BBTree in my own user designed data structure to see how the tree evolves. I want to make sure that the integrity of this data structure is preserved and correct.

The branchcallback has the following key code: (Some questions are in the comments within the code itself.)

 

int CPXPUBLIC LP::mybranchcallback(CPXCENVptr env, void *cbdata, int wherefrom, void *cbhandle, int brtype, int sos, int nodecnt, int bdcnt, const int *nodebeg, const int *indices, const char *lu, const double *bd, const double *nodeest, int *useraction_p) {

 

        //If branching is of SOS type, store nothing in user data structure

        //Q1. If I have no CPXaddsos() or CPXcopysos() anywhere in my code, is it guaranteed that the callback never finds itself at this point in code? 

        //I do have constraints such as x1 + ... + xn = 1, in my problem where the x1s are integer. With default options, does CPLEX convert automatically this constraint into an SOS type constraint          //for some purposes and could this point in the code be reached?

 

        //Depending on nodecnt, whose values may be 0, 1 or 2, create 0, 1 or 2 nodes in my data structure for storage. Store branching tree information.

        //Information about variable and bounds is available in indices and lu arguments of the callback function

    }

}

https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.cplex.help/refcallablelibrary/mipapi/setbranchcallbackfunc.html says:

nodebeg

An array with nodecnt entries. The i-th entry is the index into the arrays indices, lu, and bd of the first bound changed for the ith node.

(Q2)If nodecnt is 2, that is 2 nodes are created from the current node, then should I not be looking at index [0] (the zeroth entry) and index [1] (1st entry)? I guess if 2 nodes are created from a parent node, then one node is the 0th child node and the other is the 1st child node.

bdcnt

An integer that specifies the number of bound changes defined in the arrays indices, lu, and bd that define the CPLEX-selected branch.

 

(Q4)Also, if nodecnt is 2, is it guaranteed that indices[0] and indices[1] always have the same value? That is, CPLEX branches on the same variable in both children.

 

(Q5)The documentation says: "The details of the constraints added for a CPX_TYPE_ANY branch are not available to the user."

This is quite opaque. Is there anything the user can do at all to store some minimal branching information in the user defined data structure in case of this branch? 

 

Thank you.

#CPLEXOptimizers
#DecisionOptimization

Q1: At the moment, I think you can rely on this. But this may of course change in the future and there is no promise.

Q2: The i-th entry is the entry at index i-1. That should clarify things?

Q3, Q4: CPLEX may branch on more than one variable at a time. So for each child more than one bound change may have to be listed.

Q5: I will have to follow up on this.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Daniel,

 

This helps.

As an example, suppose from a parent P, there are two child nodes, N1 and N2.

 

N1 is obtained from P by lowerbounding variable 101 at 4, upperbounding 104 at 3, while N2 is obtained from P by upper bounding 107 at 7, upperbounding 109 at 4 and lowerbounding 110 at 1

 

Then, bdcnt will be 5 while nodecnt will be 2.

nodebeg[0] = 0

nodebeg[1] = 2

indices[0] = 101. lu[0] = L, bd[0] = 4

indices[1] = 104. lu[1] = U, bd[1] = 3

indices[2] = 107. lu[2] = U, bd[2] = 7

indices[3] = 109. lu[3] = U, bd[3] = 4

indices[4] = 110. lu[4] = L, bd[4] = 1

 

Hope this is right and thank you for the help.

#CPLEXOptimizers
#DecisionOptimization

Yes, that looks correct to me.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Daniel,

The code for the branch callback I have written is based off the example provided in admipex1.c

 

If I understand correctly, that file uses this callback to OVERRIDE CPLEX's default branching decision. That is, the branch callback function is called AFTER CPLEX spends its own time and effort in figuring out a variable to branch on.

Is there a way to avoid this overhead? That is, is there a way for the user to "take over" the decision of the branching variable directly under the user's control instead of having CPLEX do it and then the user do it just to override CPLEX's wasteful computations?

I would appreciate if there is file that explains this or else a thread discussion on this topic in this forum.

Thanks.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Daniel,

I am encountering another issue.

Node '0', the root node obtained whose number of 0 (stored in variable cplexnodeno) is obtained at the start of the branch callback via:

 

 

returns a nodecnt of 2, bdcnt of 2 indices[0] = indices[1] of the same variable, let us call it x1, lu[0]='U', lu[1]='L', bd[0] = 0 and bd[1] = 1

I take this to mean that from root node, (node number 0), node N1 is created where x1 is Upperbounded at 0, and node N2 is created where x1 is Lowerbounded at 1.

My data structure to store CPLEX's BBTREE is an std::vector<> bbtree

where bbtree[0] refers to root node, while bbtree[1] refers to node N1 referenced above, and in general, bbtree[k] will refer to the node Nk

So far, so good. 

CPLEX then takes up to solve node N1. I am able to verify within this callback via:

 

 

that cplexnodeno is indeed 1.

 

In the branch callback of node N1, I get a nodecnt of 2, bdcnt of 2 indices[0] = indices[1] of the same variable, let us call it x2, lu[0]='L', lu[1]='U', bd[0] = 1 and bd[1] = 0

As before, I take this to mean that from N1, node N3 is created where x2 is Lowerbounded at 1, and node N4 is created where x2 isUpperbounded at 0.

 

Now, CPLEX then takes up solving node '4' where this 4 is the value obtained of cplexnodeno in that branch callback.

 

int cplexnodeno;

 

I would have expected that in this node, x2 is upper bounded to 0, but it is actually lower bounded at 1.

 

Is there a way to resolve this discrepancy?

In other words, can the user rely on any one to one correspondence between which node's branching information is displayed in indices[], lu[] and bd[] data structure first and which node's comes next?

#CPLEXOptimizers
#DecisionOptimization

Trying to answer to your last two posts in one shot:

1. No, there is no way to have CPLEX skip computing its own branching decisions before invoking the branch callback. This is because by design the callback requires the tentative branching decisions as input arguments. If you know that you will never use CPLEX's branching decisions then you can change CPX_PARAM_VARSEL to something that has only small overhead.
2. From the branch callback, you should not attempt to predict the sequence number of the children created. If you need the sequence number of the children then you have to call either CPXbranchcallbackbranchasCPLEX (perform the branch CPLEX would do) or CPXbranchcallbackbranchbds() (perform your own branch). Both functions return the sequence number of the newly created children.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Daniel,

If I understand correctly, using CPXbranchcallbackbranchasCPLEX with the num parameter in increasing order from 0 to nodecnt - 1 should ensure consistency between CPLEX's number and my number.

 

Based on that understanding, below is the code.

Given:

std::vector<MYNODE> bbtree;

The following code so far seems to be working inside my branchcallback.

 

int cplexnodeno;

status = CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_SEQNUM, &cplexnodeno);

            _getch();

        }

    }

 

So far I have not come to the "Problem here..." display.

 

But I will let the forum know if I do.

Thanks.

#CPLEXOptimizers
#DecisionOptimization

Hm, you are still assuming that node sequence number are assigned in a certain order. You should not do this. For example, your current code is bound to blow up as soon as you use more than 1 thread. In fact, you should not attach any meaning to seqnum_p other than that it is an opaque and unique identifier.

It seems odd that your code does not blow up: Consider the root node. It has sequence number 0, its children should have sequence number 1 and 2. Now assume CPLEX starts exploring child 1. Eventually it will be done with that. At that point it will move to child 2 and at that point bbtree.size() will almost certainly not be 2.

I think you would be much better off if you used a std::map<int,MYNODE> instead of a std::vector<MYNODE>. Or just have parent/child pointers in MYNODE so that you don't have to rely on an index in bbtree representing a particular positiion in the tree.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Things are not working as expected.

I encounter a situation where

give seqnum_p of 24, while, the very next call to the function with arguments as

status = CPXbranchcallbackbranchasCPLEX(env, cbdata, wherefrom, 1, NULL, &seqnum_p);//Second call

returns a **lower** seqnum_p of 23.

In this case, I don't understand the statement:

"First, it specifies that the branches to be taken from the current node must be the same as the i-th branch CPLEX has selected. " provided in https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/refcallablelibrary/mipapi/branchcallbackbranchasCPLEX.html

Should not the First call create the first node using data (indices[], lu[] and bd[]) from 

nodebeg[0] to nodebeg[1] - 1 and should not the Second call create the second node using data from

nodebeg[1] to bdcnt-1?

 

#CPLEXOptimizers
#DecisionOptimization

Like I said: don't assume anything about the sequence number. It is just some unique integer that identifies a node. There is no guaranteed ordering or other relation between those sequence numbers.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

This is helpful. I hadn't thought of multithreaded situation. I need to be careful there. I think a solution may still be possible with std::vector<>, but if that does not work I will go with std::map<>

Is it guaranteed that seqnum_p will only return integers without "holes"? That is if 1000 nodes have been created (including root node), then the seqnum_p will only be 0 through 999 and not say, 0 through 998 and then 1000? In this case, I think an std::vector<> should work even with multithreaded. Let me explore that.

Also, given nodecnt = 2:

 

...

status = CPXbranchcallbackbranchasCPLEX(env, cbdata, wherefrom, 1, NULL, &seqnum_p);//Second call

 

Is it guaranteed that the First call creates a node using data (indices[], lu[] and bd[]) from 

nodebeg[0] to nodebeg[1] - 1 and that the Second call creates a node using data from

nodebeg[1] to bdcnt-1?

#CPLEXOptimizers
#DecisionOptimization

The sequence of numbers can have holes and can even run backwards. As I said before: Don't assume anything about these numbers other than that they are unique (and deterministic).

Why do you need the sequence numbers to match these arrays indices? This requirement may point to a flaw in your programming logic. Sequence numbers are created as nodes are created while your array indices are created as nodes are processed. These are two completely different things that imply a completely different ordering of the nodes. So the only way to align these is an explicit map that maps sequence numbers to array indices and/or vice versa.

About CPXbranchcallbackbranchasCPLEX: As the documentation states, calling this with num=k will create the k-th branch and that branch indeed corresponds to the data stored starting at nodebeg[k].

If I were to track the structure of the search tree, I would use some sort of linked tree implementation. Moreover, I would not use those sequence numbers at all. Instead I would attach user data to the nodes that represents nodes in my own tree.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

I have implemented a std::map<int, int> now, where the key is seqnum_p and the value is the index into my std::vector<MYNODE> bbtree datastructure. I will test the code to see if it works alright.

Perhaps there is a miscommunication on my part somewhere; but I only have bbtree.push_back() as nodes are created and not when the nodes are processed. 

 

The piece of code below checks for cplexnodeno to be the root node and creates only the first entry on processing the root node. No push_back() on bbtree is called if cplexnodeno != 0

 

int cplexnodeno;

status = CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_SEQNUM, &cplexnodeno);

 

In any case, the above code is also suspect since I cannot assume cplexnodeno for the root node is indeed 0.

 

So, I have replaced the above if condition with:

 

if (bbtree.size() == 0) {

 

}

 

The other place where bbtree.push_back() is called is further below in the call back function and as many push_back() 's are called as nodecnt. So, there is indeed a one-to-one correspondence between generation of new seqnum_p by cplex and the corresponding bbtree.push_back() in my code.

 

Regarding multithreading cases, I think a lock around the bbtree.push_back() and populating the std::map<int, int> should suffice such as:

 

 

Does this seem ok to you? Or do you think I should worry about locks elsewhere. Elsewhere, all I do is read from this data structure and any population of MYNODE data member of bbtree is not at the same index.

I have to look into user data and how one attaches that to nodes, since that is completely new to me.

Thanks for your inputs.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Hello,

There seems to be a bug in the CPLEX branch callback independent of the issues discussed so far.

With default parameters (integrality infeasibility and variable branching selection option), CPLEX chooses to branch on a binary variable with 0 value.

That the value of this variable is 0 (much lower than the default of 1e-5 anyway) is confirmed in the debug watch window (Visual studio IDE) as well as the "highlight and hover" method as indicated in the image.

"bdcnt" and "indices" are cplex returned arguments automatically in the branch callback.

cutinfo->x is a double* obtained from:

status = CPXgetcallbacknodex(env, cbdata, wherefrom, cutinfo->x, 0, cutinfo->numcols - 1);

cutinfo->numcols is the number of columns in my model and I populate it accurately elsewhere.

I do not know how this can be replicated at your end, but it seems like a bug.

Thanks.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

Following up on the previous post of cplex branching on binary variable with 0 value from node P, cplex creates two nodes, N1 and N2, where in N1, the variable in question, x is upper bounded to 0 and in N2, the variable x is lower bounded to 1.  After P, CPLEX processes N1.

Then, in N1, CPLEX seems to halt prematurely and exit the node.

More specifically, I have a user cut callback, lazy cut callback and branch callback.

Just before exiting branch callback of P, I set breakpoints at the entry of each of the 3 callbacks.

 

After exiting the branch callback of P, the user cut callback of N1 is hit. A user cut is added. The user cut callback is entered into again. But this time, no user cut is generated. CPLEX seems to find its own cut because the user cut callback is entered into again for N1. This time too, no user cut is generated. However now, none of the breakpoints in the callbacks are hit and cplex enters the cut callback of some other node elsewhere in the tree.

 

Just to confirm I am not doing any illegal writes, I ran my executable through valgrind and it does not show any errors.

The problem of cplex branching on variable with value 0 occurs in 12.8 as well as 12.7 on Windows as well as Linux. The path of the tree is different in each case, but there is definitely a branch in each case on a variable of value 0.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

After some trouble, I figured out what is going on. I have reached multiple conclusions about the way cplex works. Of course, these are completely just my conclusions and unless CPLEX folks can confirm this, CAVEAT EMPTOR!

First the issue of branching on integer variables. A thread discussing that issue appears here: https://www.ibm.com/developerworks/community/forums/html/topic?id=cbbb6491-c249-49f2-aa9d-4138682c397b&ps=25

(1)

status = CPXgetcallbacknodex(env, cbdata, wherefrom, cutinfo->x, 0, cutinfo->numcols - 1); within a branch callback at a node P is NOT a reliable indicator of the final LP solution at node P using which CPLEX figures out a fractional variable to branch. 

To figure out the fractional solution that CPLEX actually used to compute the branching variable at a node P, one needs to use a solve callback function and solve the LP there within the callback itself.

(2)

Now, the solve callback function is called multiple times from within a given node. Sometimes, it seems to be called when solving the LP associated with that node. Some other times, it seems to be called during some heuristic routine to obtain a heuristic solution. So, not every solve callback function's solution is going to give the fractional solution that CPLEX uses to branch from node P.

(3)

If we are solving a minimization problem, the solution in the branch callback of a node P obtained using status = CPXgetcallbacknodex(env, cbdata, wherefrom, cutinfo->x, 0, cutinfo->numcols - 1); is *possibly* obtained after fixing the branching variable to the argmin{Z1, Z2} where Z1 is what would be a lower bound on the objective function when the variable is set to 0 and Z2 is what would be a lower bound on the objective function when the variable is set to 1. In such cases, one can expect the starting LP solution in one of P's children to be the same as the branch callback solution of node P.

Next, the issue of CPLEX seemingly exiting a node prematurely without entering the branch callback.

A useful thread is: https://www.ibm.com/developerworks/community/forums/html/topic?id=ac79e5b1-97c6-454b-9614-48f92afe83bb&ps=25

(4)

Using the solve callback and node callback functions, I figured out that if at some point the solve callback LP solution of P is INFEASIBLE or terminated for other reasons, the branch callback need not be called. The node is instantly terminated from further processing. Of course, not every termination without finding the optimal solution in the solve callback of P is reason for terminating further processing of the node or concluding that the LP at that node is infeasible. As indicated in (2), I have encountered this INFEASIBLE situation even within the root node of an MIP that is then subsequently solved to feasibility and optimality.

(5)

Just because a node is given a sequence number obtained via status = CPXbranchcallbackbranchasCPLEX(env, cbdata, wherefrom, nd, NULL, &seqnum_p); within a branch callback does not mean that it will be entered into. A node callback that keeps track of which sequence number of nodes have been visited can confirm this.

#CPLEXOptimizers
#DecisionOptimization

I am unclear why you expected the branch callback to be invoked for every node in the first place? There are indeed many reasons a node can be deleted without branching on it: infeasible, LP relaxation integral, estimated objective value exceeds incumbent solution. So it is expected that the branch callback is not invoked on every node. By the way, the delete callback is invoked when a node is deleted. So if you need something through which every node passes then this may be what you need.

About the values return by CPXgetcallbacknodex() from the branch callback: how did you conclude that these are not the values of the LP relaxation? And how did you conclude that CPLEX did not base its decisions on those values?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: UserCplex

The following observations seem to suggest that.

I am solving a minimization MIP.

At a node P's solve callback, I solve the LP. The objective function is 100, say.

I obtain the variable values associated with this solution within the solve callback with status = CPXsolution(env, nodelp, &lpstat, &cplexobj, cutinfo->x, NULL, NULL, NULL);

cplexobj turns out to be 100, that is. In this solution, I verify that variable x is fractional, say 0.33.

(BTW, the solve callback gets called multiple time within node P, sometimes with different objective function values, sometimes resulting in infesibility, sometimes the objective function is for a heuristic that CPLEX finds at that node, etc., So, your comment on the other thread of "Nodes that are LP infeasible can be detected in the solve callback." is unclear. In any case, the final solve callback objective function value turns out to be 100 in this example).

Immediately then, a branch callback for that same node is entered into and a call to CPXgetcallbacknodex() there returns the value of x variables to be 0.

The objective function in the branch callback is 105.

The branching variable cplex has chosen to branch upon -- something that I can gather from the branch callback is x, whose value is 0 in the branch callback's CPXgetcallbacknodex()

Moreover, Pierre Bonami's post on the other thread I linked to (copied below) also seems to suggest something along the above lines:

 

"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."

 

#CPLEXOptimizers
#DecisionOptimization