Cplex lazy cut callbacks for "one-tree" Benders decomposition?

GAMS
1

I have been looking at the examples in GAMS’ website and I can see in terms of cuts through Cplex callbacks for mixed-integer programming problems there is a difference between “user cut callbacks” and “heuristic cut callbacks”.

What is the difference between these two type of callbacks? Are they both only used to prone the region that is outside the convex hull, i.e. infeasible points, with “valid cuts”? Or can any of these callbacks be used in a constraint generation framework, or Benders decomposition framework, in such a way that when the algorithm terminates it is ensured that the callback cannot identify more constraints violated?

My purpose is to implement a “one-tree” Benders decomposition where Branch and Bound process is performed at the same time as constraints are generated. The idea of this is to avoid solving a MIP from scratch, then identifying and adding violated constraints, then solving the new MIP from scratch, then identifying and adding violated constraints, etc etc… In order to implement this “one-tree” Benders decomposition I have seen Cplex offers “lazy cut callbacks”, but I haven’t been able to identify if they are available through GAMS, or if the callbacks available through GAMS can do this fine.

Thanks to whomever reads this,

Alvaro

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

2

Hi, Alvaro

You can use “lazy cut callbacks” from Cplex through GAMS and there is at least one example about how to do it (look at http://www.gams.com/docs/bch.htm). I think you can´t do it using Gurobi. The last time I tryied using Gurobi, it was not available.

I’m curious about your proposal. What kind of (maybe stochastic) problem do you want to solve?

Best regards,
Luiz Carlos.


On Thu, Jun 5, 2014 at 5:42 PM, Álvaro Lorca wrote:

I have been looking at the examples in GAMS’ website and I can see in terms of cuts through Cplex callbacks for mixed-integer programming problems there is a difference between “user cut callbacks” and “heuristic cut callbacks”.

What is the difference between these two type of callbacks? Are they both only used to prone the region that is outside the convex hull, i.e. infeasible points, with “valid cuts”? Or can any of these callbacks be used in a constraint generation framework, or Benders decomposition framework, in such a way that when the algorithm terminates it is ensured that the callback cannot identify more constraints violated?

My purpose is to implement a “one-tree” Benders decomposition where Branch and Bound process is performed at the same time as constraints are generated. The idea of this is to avoid solving a MIP from scratch, then identifying and adding violated constraints, then solving the new MIP from scratch, then identifying and adding violated constraints, etc etc… In order to implement this “one-tree” Benders decomposition I have seen Cplex offers “lazy cut callbacks”, but I haven’t been able to identify if they are available through GAMS, or if the callbacks available through GAMS can do this fine.

Thanks to whomever reads this,

Alvaro

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

\

To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

3

Hi Luiz, thanks for your answer.

Yes, I have been reading about GAMS BCH facility (http://www.gams.com/docs/bch.htm) but unfortunately I can only identify through it a way for generating “valid cuts” into the branch and bound procedure, i.e. cuts that can help solving a MIP faster by tightening the LP relaxation of the problem. However, what Cplex offers when you directly call it from Python or C or Java is a feature they call “lazy cuts”, that can be used to make Benders Decomposition for MIPs much faster, and I am starting to think this feature is not available when calling Cplex through GAMS.

Best
Alvaro

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at http://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

4

Reply-to: gamsworld@googlegroups.com


Hi Alvaro, I am trying to do the same process as you explain here in GAMS. Me and my supervisor are trying to implement a Benders decomposition using callbacks in order to avoid rework in the Brunch and Bound MIP solving. Did you manage to solve your problem? If yes, where did you find relevant information? (it seems impossible for me).
I would appreciate so much any kind of help.

Thank you in advance.
Nacho.

El jueves, 5 de junio de 2014, 22:42:10 (UTC+2), Álvaro Lorca escribió:

I have been looking at the examples in GAMS’ website and I can see in terms of cuts through Cplex callbacks for mixed-integer programming problems there is a difference between “user cut callbacks” and “heuristic cut callbacks”.

What is the difference between these two type of callbacks? Are they both only used to prone the region that is outside the convex hull, i.e. infeasible points, with “valid cuts”? Or can any of these callbacks be used in a constraint generation framework, or Benders decomposition framework, in such a way that when the algorithm terminates it is ensured that the callback cannot identify more constraints violated?

My purpose is to implement a “one-tree” Benders decomposition where Branch and Bound process is performed at the same time as constraints are generated. The idea of this is to avoid solving a MIP from scratch, then identifying and adding violated constraints, then solving the new MIP from scratch, then identifying and adding violated constraints, etc etc… In order to implement this “one-tree” Benders decomposition I have seen Cplex offers “lazy cut callbacks”, but I haven’t been able to identify if they are available through GAMS, or if the callbacks available through GAMS can do this fine.

Thanks to whomever reads this,

Alvaro

–
To unsubscribe from this group and stop receiving emails from it, send an email to gamsworld+unsubscribe@googlegroups.com.
To post to this group, send email to gamsworld@googlegroups.com.
Visit this group at https://groups.google.com/group/gamsworld.
For more options, visit https://groups.google.com/d/optout.

5

If you want to mimic lazy cut callback of CPLEX, you have to make sure that cuts are added at only new incumbents, and not fractional nodes. I’ve not been successful to try this yey, however I think the following settings should do the trick (taken from the Oil Pipeline Network Design example of GAMS Model Library):

usercutfirst 0
usercutfreq 0
usercutnewint yes

Hope this would help.