Originally posted by: amindehghanian

Hi,
Could you kindly tell me that "CPXgetcallbacknodeub", "CPXgetcallbacknodelb" give the upper bounds or lower bounds for either variables or objective function or.........?
How I can recognize which variables have been fixed so far in my branch&cut tree within my control callback?

Thanks,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

According to CPLEX, "CPXgetcallbacknodelb" gives the lower bounds for variables of the subproblem at the current node.
But the surprising issue is that, lower bounds for most of binary variables at the root node after some processing are one. It is not at least what I want.
I want to know those variables which have been fixed due to branching?

Thanks,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Just to clarify my question:)
I want to know those binary variables which are fixed at the current node and its offspring?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The methods CPXgetcallbacknodelb() and CPXgetcallbacknodeub() return the local bounds at the current node in the search tree. Thus, these bounds are valid for the current node and all of its descendants.

The methods CPXgetcallbackgloballb() and CPXgetcallbackglobalub() return the global bounds of the variables. Thus, these bounds are valid for the whole problem.

Obviously, if you call CPXgetcallbacknodelb() and CPXgetcallbacknodeub() while you are at the root node, you will get exactly the same results as with CPXgetcallbackgloballb() and CPXgetcallbackglobalub().

It could very well happen that you will see variables that are globally fixed. If you are working on the original model (the CPX_PARAM_MIPCBREDLP is set to CPX_OFF), then this can happen due to presolve fixings. But even if you are working on the presolved model (CPX_PARAM_MIPCBREDLP = CPX_ON), you may see fixed variables, because global bound changes can also happen after presolve. One example for this is reduced cost fixing.

If you want to get all bounds that are locally modified (for example, all variables that are locally fixed but not globally fixed), then you need to call all four methods and compare the node bounds with the global bounds.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

To get a sense from what I am doing, assume that I am doing Benders decomposition in a branch&cut tree.
Depending on those fixed variables, I can generate some cuts which are valid at the current node and its offspring.

This is the problem I have with using CPXgetcallbacknodelb,....
These are my observations:

1.CPLEX solve the separation problem at the root node, and generates some cuts
2. CPLEX still stays at the root node, and generates another cut after solving separation problem
3. This thing happens almost 20 times before CPLEX moves out of the root node

My problem is when I am using CPXgetcallbacknodelb, CPXgetcallbacknodeub to specify the fixed variables at the current node,
fixed variables for the subproblems of the root node as described above, are not non-decreasing.
I mean it is expected that the fixed variables of the second iteration would be super-set of those of the first iteration, and
those of the third iteration would be super-set of those of the second iteration, and so on so forth.
This is not what is happening in CPLEX, though my cuts screw up!

Thanks,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

In a simple word, the feasibility space of subproblem for the second iteration should be subset of that for the first iteration, and
the feasibility space of subproblem for the third iteration should be subset of that for the second iteration, soon so forth...
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

But what you need to have is indeed the case at the root node. During the root node processing, the bounds of the variables can only get tighter. If then the first child of the root node is processed, these bounds will again be tighter than the ones of the root node. But of course, if then the other child of the root node is processed, then the bounds are no longer tighter than the one of the previous node (i.e., the other child of the root node).

May it be that you are confused due to primal heuristics? If a primal heuristic thinks that it found a new feasible solution, then it will also call a callback to let the user check whether this solution is indeed feasible. If you are using the old cut callback API (i.e., older than CPLEX 12.3, or the CPXsetcutcallbackfunc() method in the C API), then CPLEX will call the cut callback here.
If you are using the new cut callback API (i.e., at least CPLEX 12.3, and using the CPXsetusercutcallbackfunc() and/or CPXsetlazyconstraintcallbackfunc() methods in the C API, or using an objective oriented API), then CPLEX will call the lazy constraint callback here (but not the user cut callback).

So, my guess is that your callback is being called for such a heuristic solution. In this case, all integer variables will be fixed to some values (i.e., have fixed bounds). And when the cut callback is then called another time for the regular root node LP relaxation, then you will see again the old bounds with unfixed integer variables.

Is this what is happening to you? As a first test, you could just disable all heuristics.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks!
You are right! When I turned CPX_PARAM_HEURFREQ to -1, everything gets OK.
I am using CPLEX 12.3, CPXsetlazyconstraintcallbackfunc. I also think this is what is happening now:

"So, my guess is that your callback is being called for such a heuristic solution. In this case, all integer variables will be fixed to some values (i.e., have fixed bounds). And when the cut callback is then called another time for the regular root node LP relaxation, then you will see again the old bounds with unfixed integer variables"

Unfortunately, turning off the heuristic decreased the performance of my algorithm dramatically.
Is there any other way such that I can know the fixed variables at a specific node while I don't need to turn off the heuristic?

Thanks again,
Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think that there is an easy solution to your problem.

What I understand is that you want to do the following: if the LP relaxation at a node is integral, but violates your lazy constraints (which model the subproblem in your Bender's decomposition), then you want to generate a locally valid lazy constraint to cut off the solution and force CPLEX to continue branching.
On the other hand, if an integral solution is found by a heuristic, and the solution violates your lazy constraints, then you just want to reject the solution without generating a cut.

I think it is as simple as this: just check whether all integer variables are locally fixed (by comparing the nodelb and nodeub vectors). If this is true, then you can assume that you have been called from a heuristic. Reject the solution without producing a cut (I am not sure whether this is possible from the lazy constraint callback; maybe you need to add an incumbent callback as well that peforms this rejection).
If any integer variable has unequal local bounds, then CPLEX presented you a solution to an LP relaxation of a node. Now it is time for generating a lazy constraint.

Note that it may happen (but this is really the exception) that CPLEX dives so deep that it fixes all integer variables by branching, so that this LP solution looks like a heuristic solution. But in this case, you have definitely reached a leaf node of the tree and then it is probably also okay to just reject the solution (thereby cutting off this single leaf node) without generating a lazy constraint.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks a lot Tobias!
I got it done according to what you said, and fortunately it seems it is working fine.

I think there is a tiny issue with what you wrote for the leaf node case.
In my master problem for Benders, I have my binary variables associated with the first stage variables, and I also have one continuous variable standing for the objective function of my sub-problem. I might be in a leaf node which is potentially optimal while the continuous variable is misstated. At this case, we will cut off the optimal solution, right?

For my problem, I somehow got rid of this situation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, you are right. You should couple your approach with a heuristic callback.

Namely, if a solution comes from a leaf node or a heuristic that is feasible but only has a wrong value for the dummy continuous variable that represents the objective, then you should reject the solution but in addition store the solution in some private data structure.
Then, when the heuristic callback is invoked the next time, it should pick up the solution from your private data structure, calculate the correct value for the objective (and the continuous variable) and then install this solution as new incumbent (if it is better than the current incumbent).

This way, you would solve the issue with the leaf nodes and you may also be able to benefit a bit better from CPLEX heuristics.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

That is right, thanks!

Another quick question is that in my lazyconstraintcallback, after some processing I know the values of
some of my binary variables will be fixed (0 or 1) at the current node and its offspring.
One easy but maybe inefficient way to get this job done, is by using CPXcutcallbackaddlocal.
Could you kindly tell me if there is a more efficient way for this sake? Something like CPXchgbds...

Thanks,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You could combine your lazy constraint callback with branch callback and have the branch callback create a single branch for this node that has all the fixings. If you don't have any fixings then just leave the branching to CPLEX at this node.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

... but using CPXcutcallbackaddlocal() should be okay as well. Local cuts with only one variable (i.e., bound changes) on binary or integer variables are automatically translated into local bound changes. So, there is no overhead involved like adding a new row and having to refactorize the LP basis matrix or the like.

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks for your answers!

It seems it is working, but I just want to make sure that.

1. I assume that at the first time we are in some node, solution of the node is not obtained by a primal heuristic, right?

2. Solutions, obtained by a primal heuristic at some node, satisfy the branching constraints which are given so far due to branching at that node, right?

Thanks,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

1. I think this is currently true, but you should not assume this. This may change in future versions of CPLEX.

2. This is certainly not true. Heuristics can find solutions that are not feasible in the current sub tree.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Thanks Tobias!
I also assume that any primal heuristic solution is integer feasible, right?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, this is true.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Going back to my first question!

Though CPXgetcallbacknodelb, CPXgetcallbacknodeub could be used to determine if the current solution is obtained by a primal heuristic.
I just observed one case (very rare) where ub and lb were different from each other for just one variable while the point was obtained by a primal heuristic!

I am wondering if there is another way to check if the current point is obtained by a primal heuristic?

Thanks,

Amin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Sorry Tobias!
That was my bad. It works fine!

Thanks,
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: amindehghanian

Though I am still very curious if there is any other method?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

No, not that I know of.
#CPLEXOptimizers
#DecisionOptimization