Originally posted by: MarekGrzes

Hello,

I am looking into class MyBranch in the above file. I would like to use something similar to prune nodes. Is BranchCallback a good place to do pruning of nodes? In my  case variables are 0-1, and in some cases one or two values should be pruned, i.e., both var=0 and var=1 should be pruned, whereas sometimes one or two of them should be considered.

What I concluded from the analysis of that example, is that if, e.g., var=0 should be pruned, then I can just skip makeBranch with IloCplex.BranchDirection.Down. If both values should be pruned I simply do not execute makeBranch at all. Is that correct?

The above would be good for binary variables only because having multiple values I may not be able to determince whether going IloCplex.BranchDirection.Down will have any valid variable/value pairs on integer variables. Is there any way to prune specific variable/value pairs? That is, let's say that I would like to know that the next assignment done by cplex is a specific variable/value pair, and I want to check that particular pair whether it should be rejected or not (I would like to work on one pait in the callback). This is imprtant for me, because my check is time consuming. Will I need another callback to do that? Having only binary variables, I can use the method that I mentioned above (assuming that it is correct), but I would like to know how it could be done for non-binary integer variables.

In my implementation of BranchCallback I do not want to change the order in which variables and values are ordered be cplex by defaul. The only thing is that I would like to prune some variable/value pairs once they are assigned. This means that I would like cplex to decide which variable is selected, and then I would like to prune some of its values (can I do it in BranchCallback). Perhaps if I could work with variable/value pairs (as I asked in the paragraph above), it would be easier.

Cheers,

Marek

First of all, there is a slight misunderstanding about how branch callbacks work: If you do not call makeBranch() and do not call prune() in your callback, then CPLEX will create its default branches at that node. So just not calling makeBranch() will not automatically prune a node. It will only prune the node if CPLEX would have pruned it anyway. So in order to make sure a node is pruned you should explicitly call prune() or check that CPLEX would prune the node (in which case getNBranches() should return 0).

When CPLEX branches on integer variables then it does not explicitly assign values to those variables. Instead it picks a value v that lies between the lower and upper bound of the variable and creates one branch with constraint <=floor(v) and one branch with constraint >=ceil(v). For binary variable that is the same as assigning 0 to the variable on one branch and 1 on the other. For general integer variables this is something quite different. So you cannot tell CPLEX that it should ignore particular values.

However, you can pick v as you like. and you don't have to restrict yourself to bounds floor(v) and ceil(v). For example, in order to exclude an integer number n from consideration you could create one branch with constraint <=n-1 and one branch with constraint >=n+1. Or, if for example ceil(v)<n-1 then you could create three branches <=floor(v), between ceil(v) and n-1, and >=n+1 (for technical reasons CPLEX does not allow creating more than two branches at a node but there are ways to emulate that, search this Forum if you are interested in them).

Also notice that you can pass constraint to the makeBranch() methods. So if you can somehow formulate the exclusion of values as a linear constraint then you could use that.

For all your considerations I think the branch callback is indeed the right thing to do.

Originally posted by: MarekGrzes

Thanks for your reply. I did not know that prune() has to be executed.

I see now that variable/value pairs cannot be treated explicitly, this would be possible in different search algorithms.

It is useful to know that I can pass extra constraings to the makeBranch() method.

Cheers,

Marek