Originally posted by: SystemAdmin

Hi everybody,

Assume after some calculation inside a cut callback you think the lower bound is at least equal to something which is better that the current lower bound.
It seems quite reasonable to pas the objective expression to the callback and then for a minimization problem set
$code$
add(exprObj >= getBestValue() + eps)
$code$

but surprisingly this is ineffective as the lower bound never improves at least with the size of eps.
Does anybody have an idea?

any comment is highly appreciated.

Shahin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I don't know exactly what you mean with "ineffective". Is it
(a) that this just does not help to improve performance, or
(b) that you do not see any effect of your cut?

Are you doing this at the root node, or at local nodes? If at local nodes, are you adding local cuts or global cuts?

If you are adding global cuts at local nodes, it is clear that CPLEX cannot immediately improve the global dual bound (because it does not understand that this cut is parallel to the objective function). It first has to process all nodes that have a current lower bound that is smaller than your "eps" improvement.

But in any case, I am pretty sure that the strategy you are suggesting will not improve performance. I also experimented with this idea. In contrast, it really hurts performance to add cuts that are parallel to the objective function.
The reason is most probably that such a cut adds a significant amount of degeneracy to your model. This means, CPLEX will have to search pretty long on the usually high dimensional face that you have introduced with all points on the face having the same objective value. Consequently, every branching decision that CPLEX makes will look as if completely ineffective (those decisions are mainly evaluated by their impact on the dual bound in the two child nodes). Therefore, all variables will look alike and the branching strategy will not be much better than just randomly selecting a variable.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks for your comment.
"ineffective" means I dont see any effect of this cut. and I also assume "add()" adds the cut as global which is in contrast with "addLocal()" which is local.

actually one place where this problem arises is when you are trapped in iterations of benders producing only feasibility cuts without any bound improvement and you want to get rid of that.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Yes, add() adds global cuts, while addLocal() adds them locally.

And you do not see any effect, even on the current node (in contrast to the global dual bound)?

Does this also happen if you use only 1 thread?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

right, even not in the current node-- as far as I can see.
I am running single thread to avoid the issues with multiple environment etc.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

So you are saying that after you have added the cut in the cut callback, the LP solution violates your cut? When do you observe this? Within the cutcallback after it is called a second time at the node?
How big is the eps in your case, i.e., by how much does the new LP solution violate your cut?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

let say I have the best know node some thing like 4771 then I add a cut and say that the lower bound is at least 10 unit more that but again in the next incumbent when i check the best lower bound is almost the same e.g. 4771.2 or 4773 etc which are still less than the amount I expected to improve.
I just don't understand what I am doing wrong.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

So, you are checking the best lower bound, and not the lower bound of the current node?
In this case, my comment above applies: adding a global cut does not affect the other open nodes immediately. They first need to be processed such that their LP relaxations get solved. So, adding a global cut will not change the lower bound of the other open nodes and consequently, the global lower bound will not change as well.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

not even in the later iterations? I guess if we set the epsilon big enough then a significant improvement must be observed at some point. what I can see is slight improvements which even after 1000 nodes does not reach to the size of epsilon --- the improvement we asked for.

Do you have any suggestions?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

This depends on the size and structure of your search tree. Set the MIP interval parameter to 1 such that you see each node in the log and look at the "Objective" column (which displays the LP bound of the current node). After adding the cut, this should now always be at least of the value that you provided as rhs to the objective cut.

If you want the global bound to increase as fast as possible, you need to switch to pure best first search by setting the "backtrack" parameter to 0.0.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Tobias, Many thanks for your comments.
#CPLEXOptimizers
#DecisionOptimization