Topic
  • 2 replies
  • Latest Post - ‏2013-02-09T22:07:32Z by rocarvaj
rocarvaj
rocarvaj
39 Posts

Pinned topic Adding objective value cuts

‏2013-02-08T15:55:22Z |
Hello all,

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 using cut callbacks, as objective value cuts: (say \sum_ic_ix_i is the objective function)

\sum_ic_ix_i >= LowerBound

My questions are:
  • 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?
  • 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?

Any feedback is welcome.

Thanks!
Updated on 2013-02-09T22:07:32Z at 2013-02-09T22:07:32Z by rocarvaj
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: Adding objective value cuts

    ‏2013-02-09T21:32:23Z  
    > rocarvaj wrote:
    >
    > 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

    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 ... :-)

    > using cut callbacks, as objective value cuts: (say \sum_ic_ix_i is the objective function)
    >
    > \sum_ic_ix_i >= LowerBound

    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.
    >
    > My questions are:
    > - 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?

    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.

    > - 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?

    I think that is correct ... but, again, I'm not sure they help even when added as user cuts.

    Paul

    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)
  • rocarvaj
    rocarvaj
    39 Posts

    Re: Adding objective value cuts

    ‏2013-02-09T22:07:32Z  
    > rocarvaj wrote:
    >
    > 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

    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 ... :-)

    > using cut callbacks, as objective value cuts: (say \sum_ic_ix_i is the objective function)
    >
    > \sum_ic_ix_i >= LowerBound

    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.
    >
    > My questions are:
    > - 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?

    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.

    > - 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?

    I think that is correct ... but, again, I'm not sure they help even when added as user cuts.

    Paul

    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)
    Thanks for your reply, Paul!
    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.

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

    Rodolfo