Originally posted by: GiovanniP

Hello,

I want to share with you some difficulties I am experiencing while using LazyConstraints. Perhaps you can provide me some advice on what to look at.

Background.

I am implementing a Benders Decomposition (L-Shaped Method) for a two-stage stochastic program with integer first stage. Therefore I have a binary master problem and LP subproblems.

Particularly, I am implementing the multi-cut version. This means that my master problem is like that c^Tx+\sum_s p(s)*theta(s). Where s are scenarios. The optimality test returns true if theta(s)>=(objective of the second stage subproblem problem s). Otherwise we add an optimality cut. LazyConstraints callback are called at every integer node to check whether cuts should be added or not.

I am using the Java callable libraries. The problem I describe was much more severe with Cplex 12.5.1, and became somewhat milder with Cplex 12.6.2.

My problem.

Everything looks fine, but I am experiencing the following which I am not sure it is a problem, but I find it strange.

At some integer nodes I get the following:

1. Cplex enters the node, calls the lazyconstraints callback add cuts, reoptimize the node
2. Returns to the same integer node (the master problem having the same objective, and with the same identical solution).
   The optimality test fails for a difference in the order of 1E-11. What I mean is theta(s) - obj(s) = -1E-11 or -1E-12, where obj(s) is the objective of the subproblem number s. See the picture attached for an idea of the difference.
3. Loops in the same node, as described above, for a certain number of iterations, sometimes in the order of dozens.
4. At some point it leaves the node and the algorithm proceeds regularly.

Eventually the algorithm converges, but it takes a lot of time to exit the loop I described. Now, this does not sound correct to me. Optimality cuts should cut off a solution, so it is not possible that the solver comes back again with the same one. However, the implementation of the optimality cuts is correct. My colleagues and I went through the code countless times and we could not find any flaw in the code.

My doubt is that this is a problem of numerical precision. So I post for you the following questions and I am really open for any advice.

1) Is it possible that the optimality test which fails for a difference of 1E-11 is actually satisfied? In other words, would you advice implementing an optimality test of type theta(s)+1E-11>=obj(s)?

2) Is it possible that the lazy constraints added are dumped for any reason, or are not enforced because of issues related to numerical precision?

I look forward to any suggestions. Thanks.

A difference on the order of 1e-10 or 1e-11 is almost assuredly just "noise" (rounding error) and should be considered essentially zero. If you look at the CPLEX tolerance parameters, you'll see that the default value for the feasibility tolerance parameter (IloCplex.Param.Simplex.Tolerances.Feasibility, also known as EpRHS) is 1e-6. Unless you have cranked that down below 1e-11, CPLEX will look at the gap you reported, classify it as essentially zero, and believe that the current incumbent satisfies the optimality cut you generated.

Rather than testing theta(s) >= subproblem value, you should test theta(s) >= subproblem value - epsilon, where epsilon is slightly larger than EpRHS.

Originally posted by: GiovanniP

Thanks for the swift reply. I also agree that is just noise. However, I do not understand why the solver keeps looping at the same node over again, with the same solution.

To rule out the possibility that cuts are not correct, in parallel to that I implemented a vanilla L-shaped method without using LazyConstraints. I solve the (binary) MP from scratch every time, and I add the violated cuts as constraints. This confirms that the optimality cuts are implemented correctly, as they do cut off infeasible solutions. Of course the whole process takes much longer.

So, I really do not understand why lazy constraints sometimes do not cut off infeasible solutions.

Perhaps I should add some details on the implementation. I am adding lazyconstraints in Java through a class which

extends IloCplex.LazyConstraintCallback

This class has a method main() in which I query the solution to MP, solve the subproblems and add cuts through 

add(IloRange);

The problem is experienced both on Windows 7 and on a Linux machine.

I also agree that is just noise. However, I do not understand why the solver keeps looping at the same node over again, with the same solution.

When you add a user cut, CPLEX updates the solution to the node LP and, if the node LP is still feasible, call the user cut callback again. I believe the same is true of a lazy constraint callback, provided that the node LP again produces an integer-feasible solution. So if you add a lazy constraint that does not actually cut off the proposed incumbent, I suspect CPLEX just calls the callback again ... and again ... and again. Since it eventually moves on, perhaps the rounding error eventually changes enough that the proposed incumbent is finally cut off.

I'm not sure if the L-shaped method is guaranteed to provide the same tree traversal, and therefore exactly the same cuts, as the callback approach. The key issue is to figure out why your callback is generating cuts with insignificant amounts of violation (and then correct that).

Originally posted by: GiovanniP

Thanks for the reply, now I think I have fixed the problem. Some integer solutions were not cut off as some of the optimality cuts were not actually added due to an issue of numerical precision.

Particularly, when extracting the solution to the MP (supposedly binary) the method getValue(IloIntVar v) does not return an integer but a double value. Therefore, 1 is sometimes not 1 but something very close to 1. This originated a rounding error. When passing this solution to the subproblem it became infeasible failing to generate the corresponding optimality cut. To sum up, the problem was solved by 1) artificially converting the value returned by getValue into a 0 or 1, and 2) adding an epsilon term in the optimality test as suggested.