2110https://www.ibm.com/developerworks/community/forums/atom/replies?topicUuid=77777777-0000-0000-0000-000014938867Adding objective value cuts Replies2013-02-09T22:07:32.052ZIBM Connections - Discussion Forumurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014939024Re: Adding objective value cuts2013-02-09T22:07:32.052Zrocarvaj2700030P3Vactive2013-02-09T22:07:32.052Z
Thanks for your reply, Paul!<br />
I know that these cuts won't do anything to help the branch-and-bound, but I thought that they could improve the LP relaxations a bit. I'm just experimenting with giving CPLEX different types of information and see what's the effect of doing so.<br />
<br />
It would be nice to know for sure (from the CPLEX guys) if I should turn off dual reductions in this case too (even though these cuts don't cut off any optimal solutions).<br />
<br />
Rodolfo
none, view_forum, view_categoryurn:lsid:ibm.com:forum:77777777-0000-0000-0000-000014939018Re: Adding objective value cuts2013-02-09T21:32:23.757ZSystemAdmin110000D4XKactive2013-02-09T21:32:23.757Z
> <span class="jive-quote-header">rocarvaj wrote:</span><br />
> <br />
> Suppose than during the execution of CPLEX, some oracle gives me valid lower bounds for the problem (minimization problem). So, I would like to give these bounds to CPLEX<br />
<br />
Why? CPLEX could use them to reduce the gap, but it would not affect the branch-and-bound search (no nodes would be pruned as a result of the bounds). Now if you could persuade your oracle to provide valid (and reasonably tight) upper bounds ... :-)<br />
<br />
> using cut callbacks, as objective value cuts: (say \sum_ic_ix_i is the objective function)<br />
> <br />
> \sum_ic_ix_i >= LowerBound<br />
<br />
As others (Tobias Achterberg in particular, I think) have pointed out elsewhere on the forums, having constraints/cuts that are parallel to the objective hyperplane can cause the solver's performance to degrade (by introducing dual degeneracy, I think). So unless there's a potentially significant gain from doing this, I'd be hesitant to use parallel cuts.<br />
> <br />
> My questions are:<br />
> - These cuts potentially cut off feasible integer solutions, which user cuts are not supposed to do. But I know they won't cut off any optimal solution. Should I add them as user cuts?<br />
<br />
In this particular case, I don't seem them cutting off anything, so I suppose it would be harmless. More generally, my impression is that user cuts that cut of non-optimal solutions are okay if there is a lazy constraint callback present (which turns of dual reductions), or if dual reductions are turned off via parameters. They may be okay even without that, but I'm not entirely certain.<br />
<br />
> - I imagine that considering these cuts as lazy cuts won't help me much in terms of improving the LP relaxations, so adding them as lazy cuts would be a bad idea, right?<br />
<br />
I think that is correct ... but, again, I'm not sure they help even when added as user cuts.<br />
<br />
Paul<br />
<br />
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)
none, view_forum, view_category