Originally posted by: LuisdelaTorre

I've implemented an L-Shaped method for two-stage stochastic programming using LazyConstraintCallback, following the Benders Decomposition implementation in the BendersATSP, with some help from previous threads on this forum.

Following BendersATSP, in my master problem I've set parameters in my master problem

cplex.setParam(IloCplex.BooleanParam.PreInd, false);
    cplex.setParam(IloCplex.IntParam.Threads, 1);
    cplex.setParam(IloCplex.IntParam.MIPSearch, IloCplex.MIPSearch.Traditional);

and in my subproblem

subproblemCplex.setParam(IloCplex.IntParam.Reduce, 0); 
      subproblemCplex.setParam(IloCplex.IntParam.RootAlg, IloCplex.Algorithm.Primal);

but I don't fully understand whether I need to set all of these parameters in this way for my problem. Are these parameters I should be setting whenever I use the LazyConstraintCallback to do Benders Decomposition, or whether some of these are specific to the BendersATSP example and I would be better off with default parameters.

Thanks!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

As far as I can see, none of these is required for Benders decomposition in general.

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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LuisdelaTorre

Thanks Paul! When you say Benders in general, do you mean (to take a term from your blog post http://orinanobworld.blogspot.com/2011/10/benders-decomposition-then-and-now.html) the 'classical' or 'modern' approach?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I was thinking in terms of the "modern" approach (callbacks), but I believe my answer is valid for both approaches. I also agree with Thomas's comments regarding the subproblem (with the qualification that not everyone uses a dual ray to handle infeasible subproblems -- sometimes it's enough to add a master cut that excludes the current master solution when the subproblem is infeasible).

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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Paul,

can you give me some ideas how to obtain such a cut. I know the approach using the dual ray and I know that it is quite easy to cut off the solution when the master problem is binary. But it might help me and my colleagues to have some further ideas. Furthermore, do you know whether there is a way to obtain such a cut when the subproblem is (mixed-)integer?

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: LuisdelaTorre

Ok, thanks for the follow-ups. I should say that I only need optimality cuts for my problem, since the original problem has relatively complete recourse.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thomas,

The "no-good" that I use is typically in a problem where the master is all binary variables. This one I think you already know: \sum_{i in Z} x_i + \sum_{i in O} (1-x_i) >= 1, where Z and O are the sets of indices where the solution to be cut off is respectively zero or one.

For problems with general integer variables (but no real variables) in the master, to cut off a single solution, one can introduce two new binary variables and two new constraints for each general integer variable. The binaries effectively say the variable must either exceed its current value by at least one if the first binary is 1, or be at least one smaller than its current value if the second binary is 1. In addition to the new variables and constraints, there is one more constraint, that the sum of all the new binaries must be at least 1.

All that mounts up fairly quickly, so unless the integer variables have very large bounds, it's almost surely better just to do a binary expansion (replacing each general integer variable x with log_2(U_x) binary variables, where U_x is the upper bound of x, and charitably assuming that the lower bound of x is zero).

"No-good" constraints tend not to cut very deeply, so I actually think of them mainly when it is reasonably easy to detect that the subproblem is infeasible but somewhat difficult to determine precisely why.

For what it's worth, another approach I've used (when the master has only binary variables and the subproblem is a linear program) is to find an IIS for the subproblem and then do a "no-good" cut for those members of the IIS that are affected by the master problem solution. That's often better than an "no-good" cut of the entire master solution, but perhaps not as good as a ray cut.

Cheers,
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)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Paul,

thank you for your detailed answer. It might be very helpful.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

In the subproblem, you should at least ensure that CPLEX is able to obtain the dual ray. So you should not use interior point algorithms. Also it might be necessary to disable the presolver so that infeasibility is not detected during presolve.

Best regards,
Thomas
#CPLEXOptimizers
#DecisionOptimization